Magneto903, Еще варинат есть использовать heap - должно быть сильно быстрее.
Дейкстра работает за O(n^2+m) потому что вам надо n раз искать вершину с минимальным расстоянием ну и вы по каждому ребру ровно один раз посмотрите, улучшает ли оно расстояние до другого конца.
Если минимум искать через хип, то будет O((n+m)log n) операций, что сильно лучше для вашего случая (m < n^2), потому что хип умеет выдавать минимум и изменять значение за log n.
Вы же, кажетcя, ссылку давали на этот сборник алгоритмов.
Там есть heap. Вам надо хранить в хипе пары {расстояние, номер вершины} до всех пока не visited вершин, у которых есть расстояние. Изначально heap пустой совсем.
Вам надо переписать shortestDistanceNode просто брать минимум из minHeap. При изминении distances в цикле по node вам надо добавлять в minHeap новый объект {расстояние, номер вершины}. Именно в таком порядке, чтобы минимальный элемент содержал минимальное расстояние. Ну или функции сравнения переписать.
Но тут ньюанс - в хипе может быть куча копий вершины, ведь вы будете добавлять новую копию каждый раз, когда обновите расстояние. Поэтому еще надо цикл по child пропускать, если вершина из heap уже в visited.
Или вам придется этот minHeap немного переписать, чтобы проддерживать map из номеров вершин в их позиции в хипе. И при каждом изменении массива heapContainer обовлять этот map. Тогда в методе remove не надо будет выполнять линейный поиск через find.
Потом при изменении distance в основном цикле вы должны будете удалить вершину child[0] из хипа перед добовлением ее копии с новым расстоянием.
Magneto903, Нет не надо матрицы смежности, оставьте списки инцидентности. Пусть у вас будет массив списков объектов {конец ребра, цена}. Раньше у вас там был словарь из строк-имен вершин. Но раз мы поменяли на числа, то можно это заменить массивом, который будет быстрее.
Вообще, по идее, если вместо Map использовать массивы ("[]"? Array?) должно еще быстрее быть.
Еще цикл в начале, который проходится по детям startNode - он лишний.
По поводу функции восстановления пути: надо distances[startNode] = 0 делать перед циклом по node. Иначе алгоритм находит путь в эту вершину через какую-то другую. Путь, который начинается в startNode же. В итоге получается цикл, в котором вы и висните.
Magneto903, попробуйте один хеш завести чтобы по вашим вершинам получать эти graphVertex. Сдается мне, что вы когда новую вершину с тем же именем создаете эта библиотека тоже новую вершину создает а не переиспользует старую.
Magneto903, Выглядит правильно.
Видимо, js-боль. Не знаю, попробуйте вместо хэш таблиц использовать тупо массивы. Сделайте, чтобы у вас вершины нумеровались тупо числами от 0 до сколько-их-там. Структуру соседей сделайте массивом-массивов, а не хешами всякими.
Еще, в цикле не надо проверять ```if (child === startNode) {``` можно просто в начале startNode запихать в visited. Это тоже сколько-то ускорит.
Magneto903, Да, в первой реалзации очевидная проблема с visited.
В этой новой реалезации нет того же бага, но все-равно ассимптотика тоже корявая из-за того, что там одна и та же вершина может быть в очереди сколько угодно раз. Да еще и куча выделений памяти и этот массив очереди может сильно вырасти. А главное, операция добавления в очередь там работает за линию, это не куча же а тоже массив. Поэтому в лучшем случае он будет работать в несколько раз медленее, ведь ребер больше чем вершин.
Вообще js явно страдает от отсутствия вменяемых стандартных структур данных.
xmoonlight, Особенность этого варинта в безразмерности. Т.е. если вы растянете все числа так, что любое расстояние между соседними больше года или сожмете все точки в одну микросекунду, разбиение на кластеры будет точно таким же.
Если в вашей задаче это не вяжется, можно вместо просто после сортировки отсечь по какой-то выбранной вами константе.
Никита, Если массив упорядочен по убыванию, то каждая пара чисел даст инверсию. Всего пар n(n-1)/2. В int помещается 2^31. Решаем уравнение n(n-1)/2=2^31. Или n(n-1)=2^32. Для больших чисел можно грубо прикинуть просто взяв корень, получим, что n~2^16=65536. На самом деле ответ где-то между 65536 и 65537, т.е. я на 1 ошибся - для переполнения нужно 65537 упорядоченных по убыванию чисел.
У вас в задаче может быть 100 тысяч чисел, что больше 65 тысяч, поэтому на максимальном тесте ваше решение переполнит счетчик инверсий и выдадет неправильный ответ.
Поменяйте number_of_inversitions на 64-битный тип и должно заработать.
xmoonlight, Можно жадно - не надо даже дихотомии и динамики. Отсортируйте все соседние расстояния и сливайте эти 2 соседних числа в один кластер, считая метрику.
В вашем примере сначала объединим 9.5 и 10 (разность 0.5), потом 8 и 8.7 (0.7), потом 8.7 и 9.5 (0.8), потом 5 и 6 (1). При слиянии смотрите отношение текущего расстояния и следующего и минимум его тут 1/2.
Можно даже не сливать по пути, а просто найти все разности, отсортировать, найти пару с максимальным отношением и запомнить большее. Потом все точки, с расстоянием меньше этого числа - объединить в один кластер за еще один проход.
xmoonlight, максимальное расстояние между соседними берется по всем кластерам. Да, в {8, 8.7, 9.5, 10} расстояние 0.8, но есть же еще {5, 6}. Идея в этой метрике - мы смотрим как близко точки бывают в одном кластере и как близко бывают точке вне кластеров. Эти 2 множества должны быть хорошо разделены - в кластрерах точки рядышком, а сами кластеры далеко друг от друга.
Требование иметь хотя бы 2 точки в кластерах не влияет на подсчет метрики, и его нужно включить в алгоритм. Например, во время динамики вы не смотрите на варианты, когда последний кластер состоит из одной точки - и все.
Например в {1, 3, 5, 6, 8, 8.7, 9.5, 10, 12}, если разбить на {1, 3, 5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние в кластере между соседними будет 2 (5-3), а расстояние между кластерами - тоже 2 (8-6 или 12-10). Итого метрика - 2/2=1.
Если разбить {1}, {3}, {5, 6}, {8, 8.7, 9.5, 10}, {12}, то максимальное расстояние между соседними будет 1 (это для каждой точки берем минимум по всем в том же кластере, а потом из этого всего берем максимум). А минимальное расстояние между кластерами будет 2 (тупо минимум по всем парам из разных кластеров). Итого метрика 1/2 лучше. Но тут если количество кластеров не ограничено, то можно вообще каждую точку отдельным кластером сделать и будет 0.
xmoonlight, Нет, непонятно. Может эти числа - это числовое обозначение цвета тома словаря, в котором это слово описывается. То, что зеленый выпал на 11, а красный на 12, и они как бы рядом - просто повезло.
Или вы делаете фильтр мата и эти числа - это какая-то мера матерности слова. В этом случае вам нужно именно 2 кластера.
Еще раз - без физического смысла величины и цели кластеризации - вопросы о корректности и оптимальности кластеризации не имеют смысла.
Magneto903, Нет, достаточно простой двоичной кучи. с Фиббоначиевой там получше ассимптотика чуть чуть, но это имеет смысл делать только если у вас очень много ребер. В вашем же графе это не нужно.
Осталось реализацию дейкстры исправить не с массивом visited самих номеров вершин и линейным поиском в нем, а массив из N пометок 0/1.
Там уже сложность операций в множителе 10 заложена. Попробуйте инкрементировать переменную.
Ну и, 400ms значит, что вы 40% времени будете тратить на эти поиски. Если построение графа в оставшиеся 60% влезает, то вы все успеваете.
Magneto903, javascript - боль. Ну блин, там в дейкстре надо 160 раз пройтись по всем вершинам и выбрать минимум, переписать пару значений в массивах и пройтись по всем ребрам суммарно по одному разу. У вас там что, цикл до 160*160*60*10=15m целую секунду выполнятся будет?
Поищите другую реализацию, без всяких объектов, преобразования к строкам.
Хотя, у меня вообще подозрение, что операция ```visited.includes(node)``` выполняется за линию в shortestDistanceNode. Что там за ```let visited = []``` в которую делается ```visited.push(node)```? это же массив, да? Если вместо этого использовать тупо массив из 160 булов и там помечать обойденность вершины, то будет работать в ~160 раз быстрее. Или на Set заменить хотябы.
Adamos, Вам следует изменить свой ответ, чтобы явно указать. что это будет приближение, а не оптимальный ответ. Не все заглядывают в комменты и ваш ответ в таком виде ошибочен.
