МБ
Size: a a a
2021 January 25
DM
Вот код, который надо оптимизировать
https://jsfiddle.net/Ldtrwvp9/
(смотреть на функцию
Там алгоритм поиска в ширину ищет минимальную дистанцию от заданной вершины до всех остальных во взвешенном графе, а потом находит среди них максимально удаленную вершину
Задача сделать его быстрее, чем он есть сейчас
https://jsfiddle.net/Ldtrwvp9/
(смотреть на функцию
solve, все что идет до нее - просто подготовка данных)Там алгоритм поиска в ширину ищет минимальную дистанцию от заданной вершины до всех остальных во взвешенном графе, а потом находит среди них максимально удаленную вершину
Задача сделать его быстрее, чем он есть сейчас
C
Хех, забавное наблюдение. Если тестировать сначала решение Дениса, а потом моё, разница составляет порядка 20%. Однако, если запускать в обратном порядке, разница уже в 10 раз. В чём причина, не имею ни малейшего понятия.
DM
Потенциал тут либо в том, чтобы написать алгоритм получше моего, либо хотя бы какие-то места существующего переписать более быстрым образом
Вот сейчас поступило предложение for .. of на for заменить с выигрышем около 5мкс
Вот сейчас поступило предложение for .. of на for заменить с выигрышем около 5мкс
C
C
DM
Chris
Хех, забавное наблюдение. Если тестировать сначала решение Дениса, а потом моё, разница составляет порядка 20%. Однако, если запускать в обратном порядке, разница уже в 10 раз. В чём причина, не имею ни малейшего понятия.
В 10 раз что? Твое в 10 раз быстрее моего? За 3мкс решает?
МБ
В js тернарный оператор не быстрее if/else?
МБ
Или он есть вообще?
DM
Кто знает, проверь )
DM
На самом деле производительность js протестировать задача нетривиальная из-за JIT
C
Конкретные микросекунды уже от оборудования зависят и раз на раз не приходятся, но на втором скрине avg у меня 32 мкс, у тебя 215. Это какое-то очень странное поведение, такого быть в принципе не должно.
DM
То, что вы запустили 1 раз по скорости не равно запустить 10 раз и поделить на 10
DM
Думаю это какие-то флуктуации у тебя на машине
C
То, что вы запустили 1 раз по скорости не равно запустить 10 раз и поделить на 10
Естественно.
МБ
Так разное железо разный ответ
DM
Ну у него железо-то одинаковое )
DM
Просто запускал в разном порядке
j
Вот код, который надо оптимизировать
https://jsfiddle.net/Ldtrwvp9/
(смотреть на функцию
Там алгоритм поиска в ширину ищет минимальную дистанцию от заданной вершины до всех остальных во взвешенном графе, а потом находит среди них максимально удаленную вершину
Задача сделать его быстрее, чем он есть сейчас
https://jsfiddle.net/Ldtrwvp9/
(смотреть на функцию
solve, все что идет до нее - просто подготовка данных)Там алгоритм поиска в ширину ищет минимальную дистанцию от заданной вершины до всех остальных во взвешенном графе, а потом находит среди них максимально удаленную вершину
Задача сделать его быстрее, чем он есть сейчас
Вот здесь ещё
for (let link of node.links)DM
Задача тут внести улучшение (либо полностью переписать решение)