Есть элементы, которые ссылаются друг на друга, например:
e1, e2 — не ссылаются ни на кого
e3 — ссылается на e1 и e5
e4 — ссылается на e1, e3 и e5
e5 — ссылается на e1
Нужно упорядочить элементы таким образом, чтобы для каждого из них те элементы, на которые он ссылается, стояли до него.
Для приведенного выше случая это [e1,e2,e5,e3,e4], или [e2,e1,e5,e3,e4], или [e1,e5,e2,e3,e4] и т.п.
Как это сделать максимально быстро? И попутно выяснить нет ли циклических зависимостей.
Решение "в лоб" дало мне что-то около O(N^4)
Решал так:
переменные: Вход (массив), Выход (последовательность)
пока во Входе есть элементы
для каждого из элементов во Входе
если для элемента есть в Выходе все, на кого он ссылается (выясняется двойным вложенным циклом по Выходу и ссылкам от элемента)
переместить элемент из Входа на Выход
если ни один элемент не переместили - у нас циклическая зависимость
Здравствуйте, sraider, Вы писали:
S>Есть элементы, которые ссылаются друг на друга, например:
S>e1, e2 — не ссылаются ни на кого S>e3 — ссылается на e1 и e5 S>e4 — ссылается на e1, e3 и e5 S>e5 — ссылается на e1
S>Нужно упорядочить элементы таким образом, чтобы для каждого из них те элементы, на которые он ссылается, стояли до него. S>Для приведенного выше случая это [e1,e2,e5,e3,e4], или [e2,e1,e5,e3,e4], или [e1,e5,e2,e3,e4] и т.п.
S>Как это сделать максимально быстро? И попутно выяснить нет ли циклических зависимостей. S>Решение "в лоб" дало мне что-то около O(N^4)
S>Решал так: S>
переменные: Вход (массив), Выход (последовательность)
S>пока во Входе есть элементы
S> для каждого из элементов во Входе
S> если для элемента есть в Выходе все, на кого он ссылается (выясняется двойным вложенным циклом по Выходу и ссылкам от элемента)
S> переместить элемент из Входа на Выход
S> если ни один элемент не переместили - у нас циклическая зависимость
Это называется "топологическая сортировка". У кнута в первом томе есть.
Алгоритм ты вроде правильно написал, но O(N^4) это грубо...
Кажется неправильно выбрано представление графа. Если использовать матрицу смежности, то O(N^3) получается в худшем случае.
Re[2]: Упорядочить элементы по определенному правилу
Тупанул.. У тебя получается топологическая сортировка наоборот
Короче перепиши алгоритм так, чтобы все элементы стояли перед теми, на которые они ссылаются.
Кстати при преализации графа списками смежных вершин алгоритм можно рализовать с эффективностью O(|E|+|V|), где |E|-количество вершин, |V|-количество дуг. Как сделать — не знаю, в книжке посмотрел.
Re[2]: Упорядочить элементы по определенному правилу
G>Это называется "топологическая сортировка". У кнута в первом томе есть. G>Алгоритм ты вроде правильно написал, но O(N^4) это грубо... G>Кажется неправильно выбрано представление графа. Если использовать матрицу смежности, то O(N^3) получается в худшем случае.
Топологическая сортировка — видимо то, что нужно. Буду изучать.
Re[3]: Упорядочить элементы по определенному правилу
G>Кстати при преализации графа списками смежных вершин алгоритм можно рализовать с эффективностью O(|E|+|V|), где |E|-количество вершин, |V|-количество дуг. Как сделать — не знаю, в книжке посмотрел.
Дык у Кнута всё аккуратно и расписано — глава 2.2.3 (русское издание 2000-го года):
"время выполнения можно приблизительно оценить с помощью формулы c1*m + c2*n, где
m — число введенных отношений, n — количество объектов, а c1 и c2 — константы".
Там и алгоритм, и программа, и рисуночки красивые
Re[4]: Упорядочить элементы по определенному правилу
G>>Кстати при преализации графа списками смежных вершин алгоритм можно рализовать с эффективностью O(|E|+|V|), где |E|-количество вершин, |V|-количество дуг. Как сделать — не знаю, в книжке посмотрел.
a18>Дык у Кнута всё аккуратно и расписано — глава 2.2.3 (русское издание 2000-го года): a18>"время выполнения можно приблизительно оценить с помощью формулы c1*m + c2*n, где a18>m — число введенных отношений, n — количество объектов, а c1 и c2 — константы". a18>Там и алгоритм, и программа, и рисуночки красивые
Кстати, там где пишут O(|E|+|V|) — не учитывают многих нюансов. Например, там учтенную дугу извлекают из графа — значит надо 1) иметь копию дуг графа (если не хотим изменить первоначальный) — это плюс еще O(|V|), 2) сама операция извлечения дуги может дать дополнительные O(|V|) если дуги хранятся последовательно. Протестировал такой алгоритм в реальных условиях, он мне дал худший результат, чем мое решение "в лоб"! Самым эффективным (на моих исходных данных) оказался алгоритм с использованием обхода графа в глубину — http://acm.mipt.ru/twiki/bin/view/Algorithms/TopologicalSort
Re[5]: Упорядочить элементы по определенному правилу
S>Кстати, там где пишут O(|E|+|V|) — не учитывают многих нюансов. Например, там учтенную дугу извлекают из графа — значит надо 1) иметь копию дуг графа (если не хотим изменить первоначальный) — это плюс еще O(|V|), 2) сама операция извлечения дуги может дать дополнительные O(|V|) если дуги хранятся последовательно. Протестировал такой алгоритм в реальных условиях, он мне дал худший результат, чем мое решение "в лоб"! Самым эффективным (на моих исходных данных) оказался алгоритм с использованием обхода графа в глубину — http://acm.mipt.ru/twiki/bin/view/Algorithms/TopologicalSort
Согласен, многое зависит от организации исходных данных.
У меня как-то сортировка "пузырьком" оказалась на порядок быстрее квиксорта — из-за специфики входных данных
Здравствуйте, a18, Вы писали:
a18>У меня как-то сортировка "пузырьком" оказалась на порядок быстрее квиксорта — из-за специфики входных данных :)
А это (offtopic) баян дремучий. Использовал бы introsort, который съезжает на сортировку вставками, и не было бы такой проблемы (insertion sort хорошо (или, вернее, одинаково плохо) работает на любых данных).
До последнего не верил в пирамиду Лебедева.
Re[7]: Упорядочить элементы по определенному правилу
a18>>У меня как-то сортировка "пузырьком" оказалась на порядок быстрее квиксорта — из-за специфики входных данных
RO>А это (offtopic) баян дремучий. Использовал бы introsort, который съезжает на сортировку вставками, и не было бы такой проблемы (insertion sort хорошо (или, вернее, одинаково плохо) работает на любых данных).
Кстати, чисто из любопытства, а introsort является устойчивой сортировкой? (т.е. сохраняется ли порядок элементов с одинаковыми значениями ключа)? А то один раз такое срочно понадобилось — пришлось какие-то медленные велосипеды изобретать.
Re: Упорядочить элементы по определенному правилу
От:
Аноним
Дата:
08.11.07 11:28
Оценка:
Nujna pomosh' v sortirovke NAoborot!
kto znaet kak 'eto sdelat' v Excele? greenpin@mail.ru
Здравствуйте, sraider, Вы писали:
S>Есть элементы, которые ссылаются друг на друга, например:
S>e1, e2 — не ссылаются ни на кого S>e3 — ссылается на e1 и e5 S>e4 — ссылается на e1, e3 и e5 S>e5 — ссылается на e1
S>Нужно упорядочить элементы таким образом, чтобы для каждого из них те элементы, на которые он ссылается, стояли до него. S>Для приведенного выше случая это [e1,e2,e5,e3,e4], или [e2,e1,e5,e3,e4], или [e1,e5,e2,e3,e4] и т.п.
S>Как это сделать максимально быстро? И попутно выяснить нет ли циклических зависимостей. S>Решение "в лоб" дало мне что-то около O(N^4)
S>Решал так: S>
переменные: Вход (массив), Выход (последовательность)
S>пока во Входе есть элементы
S> для каждого из элементов во Входе
S> если для элемента есть в Выходе все, на кого он ссылается (выясняется двойным вложенным циклом по Выходу и ссылкам от элемента)
S> переместить элемент из Входа на Выход
S> если ни один элемент не переместили - у нас циклическая зависимость