Дейкстра почти за линейное время (для неориентированного графа)?

Похоже, что с алгоритмами на графах примерно такая же проблема как и в сортировках, нужно определить паттерн данных - пример

Проверка на достижимость в направленном графе?

Вообще можно было бы попробовать бин поиском (по timeIn dfs) по вершинам, в которые можно по перекрёстным рёбрам добраться(как 4-й шаг в том алгоритме): скакать по вершинам, используя timeIn вершины to, и при каждом переходе в перекрёстную вершину, проверять timeIn у to > или <, чем, timeIn перекрёстной вершины, ну то есть выше или ниже она дереве обхода dfs

Хотя такое, наверное не сделать, лучше чем за n*logn памяти, а это многовато

Проверка на достижимость в направленном графе?

да, я не учёл наличие красных рёбер (из картинки выше), нужно как-то это тоже проверять, боюсь, что таким образом приду как раз к тем двум алгоритмам из той статьи - Thorup's Algorithm и Kameda's Algorithm

Сценарии применения Splay Tree?

Wataru, ну я как раз и спросил, что мб как раз с сильно неравномерными распределениями сплей дерево как раз лучшее, что есть, мб даже лучше статического массива при отсутствии модификации

Сценарии применения Splay Tree?

Wataru, вот, кстати, что в самом верху топика про сплей деревья в вики написано:

For random access patterns drawn from a non-uniform random distribution, their amortized time can be faster than logarithmic, proportional to the entropy of the access pattern. For many patterns of non-random operations, also, splay trees can take better than logarithmic time, without requiring advance knowledge of the pattern.

Сценарии применения Splay Tree?

Wataru,

Если в качестве диапазоно взять ключи, то у вас будет запрос по ключам.

не уверен, что это получится, если вставить новый элемент, то в отличие от обычного дерева отрезков, где нейтральный элемент заменится на новый и пересчитаются предки, то тут как минимум придётся делать дерево но узлах, а не массиве и кажется, что оно сильно поехать может если не в конец вставить, а в середину

Вы там говорили, что данные не меняются, так что возможно какой-нибудь сортированный массив с одним бинпоиском может быть даже быстрее любой другой структуры данных.

вот как раз не уверен, например, если там лежит 1кк элементов, при этом 99% запросов это какие-то 1000 элементов, то для них будет в сплей дереве глубина в 2 раза меньше, чем до остальных (должна быть), а в отсортированном массиве для всех элементов будет примерно logn скачков в рандомное место памяти, ну то есть, например, в сплей дереве будет для 1кк в среднем 11 скачков на запрос, а в отсортированном массиве 20 скачков

Сценарии применения Splay Tree?

Wataru, ну типа есть хеш-таблица, где можно делать запросы только на равенство, есть дерево поиска, где можно делать запросы по неравенству(самих целевых значений узлов дерева), а в дерево отрезков, где можно делать запросы по непрерывному диапазону узлов (отрезку), и вычислять какую-то функцию для этого подмножества, но в дереве отрезков запрос именно можно сказать по 2-му параметру узлов - порядковому номеру, которые вместе образуют диапазон, а не целевому значению узла, как в обычном дереве отрезков, так что это немного не то, про что я говорил

Сценарии применения Splay Tree?

Wataru, да не, я под range запросами имел в виду неравентсво, а не интервал )

Сценарии применения Splay Tree?

mayton2019, ну вот в вик ,например, написано, что это дерево поиска, значит на нём порядок есть
ну и все эти зиги а заги это же повороты, значит порядок элементов сохраняется, не понимаю почему это должно не работать

на всякий случай уточню: range запрос имелось в виду запрос на неравеснство (>, <, >=, <=)

Сценарии применения Splay Tree?

mayton2019, имелось в виду, что на find'ы будут приходить range запросы, а не запросы на равенство (поэтому хеш таблица не подойдёт)
например, autocomplete

Когда целесообразно использовать именно такую реализацию DSU?

вот, кстати, нашёл задачу, где dsu не асимптотически, но быстрее. чем dfs, ну и даже сам код лаконичнее и яснее

конечно не очень хороший бенчмарк, но leetcode для dsu выдаёт в среднем 150 милисекунд, а для dfs 190 милисекунд, там для dfs, в частности, нужно ещё в список смежности превратить исходный массив, нужна мапа (медленная) для vertex To component, сет для used ну и сам код намного длинее выходит

вынесу этот коммент наружу топика, чтобы если кому понадобилось - сразу увидел

Когда целесообразно использовать именно такую реализацию DSU?

в общем, спасибо за ответ )
вроде примерно устаканилось в голове )

Когда целесообразно использовать именно такую реализацию DSU?

Ну так это у вас DSU тарьяна и есть. Вы же процитировали описание "тривиальной" альтернативы. Список элементов в множестве нужен будет для перекраски, чтобы не проходиться по всем n элементам, а только по элементам множества. Иначе объединение будет O(n) а не O(log n) и DSU окажется еще лучше.

да точно, я просто в голове держал задачи, где можно было просто запомнить список "текущего" множества, чтобы за n не проходится по массиву, это как раз те задачи, которые dfs'ом решаются

Я бы в этой задаче тоже dfs использовал. Но, может, кому-то dsu первым в голову придет. Кому-то dsu может показаться проще dfs. Проще писать, проще осмыслить, короче код.

лично в моём понимании как раз dsu и должен давать ощутимый выигрыш, когда прилетают рандомные union'ы и добавляются новые элементы через makeSet :)

Когда целесообразно использовать именно такую реализацию DSU?

Итак, имеем O(Log*n) vs O(1) за проверку и O(log*n) vs O(log n) за объединения.

ну и я подчеркнул, если объекдинения вида: проход dfs'ом по каждому элементу и добавление в текущее множество ровно по одному элементу, то от disjoint set'а одно название, а вот как раз обоснованное применение его видится (с ранговой эвристикой и сжатием путей), как раз когда не по одному элементу добавляется, а когда часто вызывается union() у множеств внушительных размеров, а также часто вызывается makeSet(x), то есть исходный размер всех элементов тоже растёт

Когда целесообразно использовать именно такую реализацию DSU?

DSU выполняет две операции: проверить, принадлежат ли 2 элемента одному множеству; объеденить множества двух данных элементов. Обе за O(log*n) ассимтотически. Это не логарифм, а суперлогарифм, или обратная функция Аккермана. Это - сколько нужно двоек сложить в степенную башню, чтобы набрать n. Она растет так медленно, что ее можно считать константой на практике (она достигнет 4 только при n=2^65536 - вы столько числел не сохраните во всех датацентрах мира).

я в "n^2 * A()" под A() и имел в виду обр. аккермана

Я бы в качестве альтернативной, "тривиальной" реализации рассматривал массив пометок + списки в массиве:
для каждого элемента храним номер его множества, а для каждого номера храним список всех его элементов в списках (так же, как и в DSU, в одном массиве ссылок на следующий элемент).

те реализации, которые я видел, на вики, например, обычно не имели списка всех элементов одного множества, вот, например, та, которую для leetcode/codeforces использую DisjointSetUnion

Эта структура компактна по памяти и более быстра, чем ваши хеш таблицы. Тут можно за O(1) проверить, что два числа в одном множестве и за O(log n) объеденить два множества (амортизированно, если перекрашиваем меньшее множество).

если по какой-то причине не удалось сжать координаты (id элементов множеств), то придётся хеш таблицы использовать, а не плотные массивы

собственно я и задал вопрос, потому что ради интереса, посмотрев решения литкода на некоторые задачи, тегированные как union-find, люди зачем-то использовали disjoint set, там где можно было обойтись обычным dfs'ом, и на этой почве как раз и возник вопрос :)
вот ещё пример, большинство решений через disjoint set, но непонятно зачем, если можно сделать, например, так

Можно ли так доказывать правильность алгоритмов?

Михаил Ливач, ну тут 2 максимальных последовательности из 1-го элемента

Можно ли так доказывать правильность алгоритмов?

vadimr, я не стал уточнять в вопросе, но речь шла о доказательстве "для себя", а не для публикации куда-либо
Хотя, например, когда я читал публикацию какого-то уважаемого вуза про Robin Hood hashing, они тоже не вводили ни лямбда-исчисление, ни абстрактную машину

Можно ли так доказывать правильность алгоритмов?

vadimr, вы говорили про упорядоченность в контексте абстрактной выч. машины, а до этого я говорил про то, что вводить асбтрактную машину это избыточно )

Можно ли так доказывать правильность алгоритмов?

vadimr, я думаю, в конкретно в этой статье, и так достаточно формальное доказательство, более формально (например, через машину Тьюринга) было бы избыточно для понимания работы дейкстры

Можно ли так доказывать правильность алгоритмов?

vadimr, ИТМО это не википедия Википедия :)