Упорядочить элементы по определенному правилу
От: sraider http://dvinogradov.blogspot.com
Дата: 30.08.07 17:51
Оценка:
Есть элементы, которые ссылаются друг на друга, например:

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)

Решал так:
переменные: Вход (массив), Выход (последовательность)

пока во Входе есть элементы
    для каждого из элементов во Входе
        если для элемента есть в Выходе все, на кого он ссылается (выясняется двойным вложенным циклом по Выходу и ссылкам от элемента)
            переместить элемент из Входа на Выход
    если ни один элемент не переместили - у нас циклическая зависимость
Re: Упорядочить элементы по определенному правилу
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 30.08.07 19:06
Оценка: 1 (1) +1
Здравствуйте, 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]: Упорядочить элементы по определенному правилу
От: gandjustas Россия http://blog.gandjustas.ru/
Дата: 30.08.07 19:12
Оценка:
Здравствуйте, gandjustas, Вы писали:

Тупанул.. У тебя получается топологическая сортировка наоборот
Короче перепиши алгоритм так, чтобы все элементы стояли перед теми, на которые они ссылаются.


Кстати при преализации графа списками смежных вершин алгоритм можно рализовать с эффективностью O(|E|+|V|), где |E|-количество вершин, |V|-количество дуг. Как сделать — не знаю, в книжке посмотрел.
Re[2]: Упорядочить элементы по определенному правилу
От: sraider http://dvinogradov.blogspot.com
Дата: 30.08.07 20:03
Оценка:
G>Это называется "топологическая сортировка". У кнута в первом томе есть.
G>Алгоритм ты вроде правильно написал, но O(N^4) это грубо...
G>Кажется неправильно выбрано представление графа. Если использовать матрицу смежности, то O(N^3) получается в худшем случае.

Топологическая сортировка — видимо то, что нужно. Буду изучать.
Re[3]: Упорядочить элементы по определенному правилу
От: a18 Россия  
Дата: 31.08.07 07:59
Оценка:
G>Кстати при преализации графа списками смежных вершин алгоритм можно рализовать с эффективностью O(|E|+|V|), где |E|-количество вершин, |V|-количество дуг. Как сделать — не знаю, в книжке посмотрел.

Дык у Кнута всё аккуратно и расписано — глава 2.2.3 (русское издание 2000-го года):
"время выполнения можно приблизительно оценить с помощью формулы c1*m + c2*n, где
m — число введенных отношений, n — количество объектов, а c1 и c2 — константы".
Там и алгоритм, и программа, и рисуночки красивые
Re[4]: Упорядочить элементы по определенному правилу
От: sraider http://dvinogradov.blogspot.com
Дата: 31.08.07 13:11
Оценка:
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]: Упорядочить элементы по определенному правилу
От: a18 Россия  
Дата: 31.08.07 15:46
Оценка:
S>Кстати, там где пишут O(|E|+|V|) — не учитывают многих нюансов. Например, там учтенную дугу извлекают из графа — значит надо 1) иметь копию дуг графа (если не хотим изменить первоначальный) — это плюс еще O(|V|), 2) сама операция извлечения дуги может дать дополнительные O(|V|) если дуги хранятся последовательно. Протестировал такой алгоритм в реальных условиях, он мне дал худший результат, чем мое решение "в лоб"! Самым эффективным (на моих исходных данных) оказался алгоритм с использованием обхода графа в глубину — http://acm.mipt.ru/twiki/bin/view/Algorithms/TopologicalSort

Согласен, многое зависит от организации исходных данных.
У меня как-то сортировка "пузырьком" оказалась на порядок быстрее квиксорта — из-за специфики входных данных

По сортировке — вот ещё ссылка, на всякий случай:
http://en.wikipedia.org/wiki/Topological_sorting
Re[6]: Упорядочить элементы по определенному правилу
От: Roman Odaisky Украина  
Дата: 02.09.07 07:33
Оценка:
Здравствуйте, a18, Вы писали:

a18>У меня как-то сортировка "пузырьком" оказалась на порядок быстрее квиксорта — из-за специфики входных данных :)


А это (offtopic) баян дремучий. Использовал бы introsort, который съезжает на сортировку вставками, и не было бы такой проблемы (insertion sort хорошо (или, вернее, одинаково плохо) работает на любых данных).
До последнего не верил в пирамиду Лебедева.
Re[7]: Упорядочить элементы по определенному правилу
От: a18 Россия  
Дата: 02.09.07 21:03
Оценка:
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>    если ни один элемент не переместили - у нас циклическая зависимость
 
Подождите ...
Wait...
Пока на собственное сообщение не было ответов, его можно удалить.