Есть подозрение, что сделан простой DFS с проверкой на циклы, так?
Это неправильно. Теряется одна из киллфич: все элементы без взаимных зависимостей должны быть расположены рядом.
Киллфича нужна для кучи интересных сценариев наподобие автоматического распараллеливания обработки.
Например, вот такой вот граф
при обходе с любого узла должен сортироваться вот так:
a1 b1 c1 d1 e1
c2 e2
e3
(внутри каждого столбца порядок элементов произвольный)
Ну и элементы надо отдавать массивами (каждый слой — отдельный массив), а не простой последовательностью.
Здравствуйте, AndrewVK, Вы писали:
AVK>Ну так поправь.
На мне пока перфтесты + после них диапазоны добить. Если никто не займётся за это время — не вопрос
У меня реализация есть, она корректная, но кондово-дубовая, на словариках и хэшсетах, по перфомансу подозреваю в ней полный мрак.
S>Есть подозрение, что сделан простой DFS с проверкой на циклы, так? S>Это неправильно. Теряется одна из киллфич: все элементы без взаимных зависимостей должны быть расположены рядом.
DFS тут не канает, очевидно. BFS будет работать.
S>Киллфича нужна для кучи интересных сценариев наподобие автоматического распараллеливания обработки. S>Например, вот такой вот граф S>
S>при обходе с любого узла должен сортироваться вот так: S>
S> a1 b1 c1 d1 e1
S> c2 e2
S> e3
S>
(внутри каждого столбца порядок элементов произвольный)
Что-то не то у тебя с картинками. Если у тебя e1, e2 и e3 — это источники, то они все в первую партию должны попасть.
S>https://habrahabr.ru/post/66766/
Ну, там вообще все примитивно. Даже никакие BFS/DFS не нужны. Просто строиться матрица смежности и на каждом шаге выделяются столбцы, содержащие одни нули. Соответствующие строки элиминируются. Для ускорения еще и сумму по столбцам отдельной строкой можно держать и вычитать из нее выкинутые строки.
Другое дело, что такое представление при слабой связности графа будет много лишней памяти жрать на хранение нулей.
Здравствуйте, Lexey, Вы писали:
S>>Есть подозрение, что сделан простой DFS с проверкой на циклы, так? S>>Это неправильно. Теряется одна из киллфич: все элементы без взаимных зависимостей должны быть расположены рядом.
L>DFS тут не канает, очевидно. BFS будет работать.
Ну вот сколько помню, простого обхода недостаточно. В самом тупом, но гарантированно рабочем алгоритме Кана нужна сортировка узлов по количеству исходящих дуг, убирание узлов с степенью 0 + goto в начало. Остался узел с ненулевой степенью — цикл.
Надо бы найти более изящное решение, если нет — его сделать и не мучаться.
L>Что-то не то у тебя с картинками. Если у тебя e1, e2 и e3 — это источники, то они все в первую партию должны попасть.
не, стрелки — зависит от. Т.е. у a1 нет зависимостей, b1, с2 и e3 зависят от a1 и тыды.
Здравствуйте, Sinix, Вы писали:
S>Ну вот сколько помню, простого обхода недостаточно.
А я и не говорил, что он совсем простой. Без повторных итераций тут никак, скорее всего.
S>В самом тупом, но гарантированно рабочем алгоритме Кана нужна сортировка узлов по количеству исходящих дуг, убирание узлов с степенью 0 + goto в начало. Остался узел с ненулевой степенью — цикл.
Входящих может быть? На вскидку, если не стороить матрицу соответствия, то можно так:
1) Все ноды загоняем в общий список.
2) Для каждой ноды строим сэт нод, от которых она зависит и сэт, зависящих от нее.
3) Выбираем все ноды, у которых нет зависимостей
4) В цикле:
4.1) Пихаем ноды без зависимостей в результат. Уменьшаем счетчик необработанных нод
4.2) Проходим по всем нодам, которые зависят от нод без зависимостей, и удаляем у них зависимости. Если получается новая нода без зависимостей, то пихаем ее в список на следующую итерацию цикла.
4.3) Проверяем количество нод без зависимостей в новом списке. Если оно нулевое, то завершаемся либо успешно, если счетчик необработанных нод нулевой, либо кидаем исключение о наличии цикла.
4.4) goto 4.1
S>Надо бы найти более изящное решение, если нет — его сделать и не мучаться.
L>>Что-то не то у тебя с картинками. Если у тебя e1, e2 и e3 — это источники, то они все в первую партию должны попасть. S>не, стрелки — зависит от. Т.е. у a1 нет зависимостей, b1, с2 и e3 зависят от a1 и тыды.
А... Просто в графах стрелками показывают направления возможных переходов между вершинами. А у тебя обратный смысл.
L>А... Просто в графах стрелками показывают направления возможных переходов между вершинами. А у тебя обратный смысл.
Ага, привык рисовать зависимости, постоянно самого в ступор вгоняет, когда надо обычный граф нарисовать
Здравствуйте, Lexey, Вы писали:
L>А... Просто в графах стрелками показывают направления возможных переходов между вершинами. А у тебя обратный смысл.
Вот поэтому важно не переходить на математическую терминологию графов, узлов и дуг, а формулировать API в терминах зависимостей. Тот алгоритм, что на хабре, судя по всему как раз по причине путанницы в этом и не работает.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
AVK>Я попытался реализовать тот алгоритм по божески — оно зацикливается на тестах. Подробности в последнем коммите.
Заметил, что начальный массив там формируется не из LinkedNodes, а из LinkedDownNodes. Заполнения его в статье нет, а ссылка на полный пример давно протухла. Видимо, это связи в обратную сторону.
А так хотелось в алгоритм не вникать
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Вобщем, вроде починил, но образовалась одна проблемка — алгоритм выдает задом наперед данные, т.е. от более зависимых к менее зависимым. Нужно либо требовать изначально не список зависимостей, а наоборот, список зависимых. Но это неудобно. Либо тем или иным способом развернуть внутри, но это дополнительный расход памяти. Как правильно сделать — я ХЗ.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Вобщем, сделал групповой топосорт. Нужно:
1) Отревьювить код
2) Подумать на предмет перформанса свежим взглядом
3) Определиться что делать с текущим TopoSort — оставить как есть, или сделать на базе новой реализации.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Вот поэтому важно не переходить на математическую терминологию графов, узлов и дуг, а формулировать API в терминах зависимостей. Тот алгоритм, что на хабре, судя по всему как раз по причине путанницы в этом и не работает.
ИМХО, нужно алгоритм реализовывать именно в терминах графов, чтобы он был универсальным.
На вход — список ребер в виде чего-нибудь типа ValueTuple<TNode, TNode> (или завести под это свою структуру Edge<TNode>), на выходе — список списков нод. А в терминах зависимостей можно сделать адаптер, зовущий универсальную реализиацию.
L>ИМХО, нужно алгоритм реализовывать именно в терминах графов, чтобы он был универсальным.
Мы не делаем универсальные всемогуторы, это не наш бизнес. Мы пишем код, который должен работать "на кончиках пальцев", т.е. решать проблемы пользователей без изучения документации и без доработки напильником.
Иначе смысла никакого в библиотеке хелперов нет.
Есть желание забубенить что-то более фундаментальное и универсальное — надо бы это в отдельный проект вытащить.
А то у нас получается оливье с селёдкой какое-то. По отдельности всё отлично, но общий вкус испорчен получается.
L>На вход — список ребер в виде чего-нибудь типа ValueTuple<TNode, TNode> (или завести под это свою структуру Edge<TNode>), на выходе — список списков нод. А в терминах зависимостей можно сделать адаптер, зовущий универсальную реализиацию.
Это хорошо только для матан-библиотек, когда прогнуть клиента под кривой API не предоставляет никаких проблем. Не нравится — пусть ищет альтернативы
Для качественного публичного кода надо начинать с реального сценария + с реальной задачи.
Иначе неизменно получается сфероконь, который для использования надо костылями обложить. Ну и зачем он такой нужен?
Здравствуйте, Lexey, Вы писали:
L>ИМХО, нужно алгоритм реализовывать именно в терминах графов, чтобы он был универсальным.
Не нужно. Во-первых, как я уже писал, это приведет к непониманию людей, с теорией графов незнакомых.
Но это полбеды. Вторая проблема заключена в перформансе. Для разных ситуаций оптимально разное представление графов (я тут тему уже заводит про это). А для разных представений реализация алгоритма может соущественно отличаться и по памяти, и по производительности. К примеру, для сабжевого алгоритма, если у нас в графе есть ссылки на соседние узлы, то все резко упрощается.
Поэтому, когда у тебя в программе есть большие и сложные графы, то нужна специализированная библиотека алгоритмов или вообще ручная их реализация для конкретного случая.
А TopoSort предназначен для вполне конкретного юзкейса — разделению неких элементов по зависимостям. В этом случае примерный вид графа понятен, да и вообще обычно перформанс не особо критичен, так как граф маленький обычно.
L>На вход — список ребер в виде чего-нибудь типа ValueTuple<TNode, TNode> (или завести под это свою структуру Edge<TNode>), на выходе — список списков нод.
Ну вот отличный пример как делать не надо в данном случае. С почти 100% вероятностью в типовом юзкейсе придется преобразовывать структуру в такой список.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, Sinix, Вы писали:
S>Мы не делаем универсальные всемогуторы, это не наш бизнес. Мы пишем код, который должен работать "на кончиках пальцев", т.е. решать проблемы пользователей без изучения документации и без доработки напильником. S>Иначе смысла никакого в библиотеке хелперов нет.
Это не универсальный всемогутор. Это как раз реализация одного из принципов из твоего любимого FDG: наличие продвинутого API для продвинутых и легкого API, сделанного поверх него, для остальных. Иначе может получиться как в известной фразе "Если программа написана так, чтобы ей могли пользоваться даже дураки, то только дураки и будут ей пользоваться".
S>Есть желание забубенить что-то более фундаментальное и универсальное — надо бы это в отдельный проект вытащить. S>А то у нас получается оливье с селёдкой какое-то. По отдельности всё отлично, но общий вкус испорчен получается.
Ну, по хорошему, если пилить алгоритмы на графах (к которым относится топосорт), то нужно их пилить с нормальной базой для графов.
S>Это хорошо только для матан-библиотек, когда прогнуть клиента под кривой API не предоставляет никаких проблем. Не нравится — пусть ищет альтернативы S>Для качественного публичного кода надо начинать с реального сценария + с реальной задачи.
Даже если у тебя реальная задача — построить порядок компиляции исходников, то выбрать для нее модель данных ты волен сам.
И представление связей "это зависит от того" ничем не лучше "после этого можно пытаться делать то". Это 2 стороны одной и той же медали.
S>Иначе неизменно получается сфероконь, который для использования надо костылями обложить. Ну и зачем он такой нужен?
Не получается. Получается универсальная вещь, которую можно использовать и как в простых вариантах (через готовый адаптер), так и в более сложных. Иначе в более сложных придется искать другую либу, после чего наша станет лишней.
Здравствуйте, Lexey, Вы писали:
L>Не получается. Получается универсальная вещь, которую можно использовать и как в простых вариантах (через готовый адаптер), так и в более сложных. Иначе в более сложных придется искать другую либу, после чего наша станет лишней.
Ну если ты хочешь и можешь сделать универсальный алгоритм, и адаптер для него, не создающий оверхеда по памяти — велкам. Но адаптер в данном случае первичен, а универсальный алгоритм — вторичен.
... << RSDN@Home 1.0.0 alpha 5 rev. 0 on Windows 8 6.2.9200.0>>
Здравствуйте, AndrewVK, Вы писали:
AVK>Не нужно. Во-первых, как я уже писал, это приведет к непониманию людей, с теорией графов незнакомых.
Для таких людей как раз будет адаптер в "простом" стиле.
AVK>Но это полбеды. Вторая проблема заключена в перформансе. Для разных ситуаций оптимально разное представление графов (я тут тему уже заводит про это). А для разных представений реализация алгоритма может соущественно отличаться и по памяти, и по производительности. К примеру, для сабжевого алгоритма, если у нас в графе есть ссылки на соседние узлы, то все резко упрощается.
Cейчас, получив на вход обратные связи вида "M зависит от N1, N2, ...", ты все равно строишь прямые и работаешь с ними. Единственная польза от связей "M зависит от N..." — это количество Ni для M.
С тем же успехом можно получать прямые связи и считать количество обратных.
Если хочется избежать двойной работы по переворачиванию связей при использовании адаптера, то можно сделать внутреннюю реализацию, которая получает и прямые связи в оптимальном виде и счетчики обратных, а публичные API выставлять адаптерами к ней.
Так и перфоманс будет цел и возможности для реализации разных API останутся.
AVK>А TopoSort предназначен для вполне конкретного юзкейса — разделению неких элементов по зависимостям. В этом случае примерный вид графа понятен, да и вообще обычно перформанс не особо критичен, так как граф маленький обычно.
Тем более, зачем тогда заморачиваться борьбой за O(число ребер) при возможном перевороте направления связей? Равно как и зачем заставлять юзера использовать только одно представление, если ему можно дать 2, позволив выбрать то, которое будет ему удобнее.
AVK>Ну вот отличный пример как делать не надо в данном случае. С почти 100% вероятностью в типовом юзкейсе придется преобразовывать структуру в такой список.
С почти 100% вероятностью в типовом юзкейсе будет или такое или обратное представление. Только способ храниения связей может отличаться. Если так хочется побороться за то, чтобы не делать лишних преобразований (хотя это копейки в условиях типичных задач, которые ты сам описал), то можно получать связи через аналог твоего dependsOnGetter. Только вместо него будет dependantsGetter.
Здравствуйте, AndrewVK, Вы писали:
AVK>Ну если ты хочешь и можешь сделать универсальный алгоритм, и адаптер для него, не создающий оверхеда по памяти — велкам. Но адаптер в данном случае первичен, а универсальный алгоритм — вторичен.
ОК. Давайте тогда устаканим первичный вариант, а потом я подумаю, как из него можно вытащить общую часть, чтобы можно было и альтернативные API добавлять.
