|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
13.02.2010 12:35
|
|
|
Ну вот, кстати, о сортировках и их реализациях. Недавно проспорил другу пивасик, не смог написать qsort, который работает быстрее вставок на случайном массиве длины 100. Хотя оптимизации он мне разрешил юзать разные, например, короткие массивы (до 8ми) я сортировал его же функцией 
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
В треде спрашивается про алгоритм, а не про его реализацию. В результате сравнения реализаций алгоритма можно получить разве что стандартную таблицу значений - параметры входных данных - параметры выходных данных. И какие же выводы это позволит сделать в отношении алгоритмов?
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
13.02.2010 13:26
|
|
|
Ну алгоритмы же мы тоже опишем. И оптимизации.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
В ответ на:
Ну вот, кстати, о сортировках и их реализациях. Недавно проспорил другу пивасик, не смог написать qsort, который работает быстрее вставок на случайном массиве длины 100. Хотя оптимизации он мне разрешил юзать разные, например, короткие массивы (до 8ми) я сортировал его же функцией
Это как раз то, о чем я и говорил. Случайная реализация алгоритма не позволяет судить о самих алгоритмах. То, что предлагается меряться скоростью - это чистой воды задротство.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
13.02.2010 13:28
|
|
|
Ты неправ. Это не задротство, а напротив, некоторая программистская мудрость. Вот как в соседнем треде обсуждают про printf vs stringstreams, так и здесь: если массив маленький, то писать асимптотически пиздатый qsort не надо.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
В ответ на:
Сначала ты предлагаешь разбивать на сильно связные компоненты и выдаешь это за решение, хотя никто не говорил, что эти компоненты большие и это сильно упростит задачу.
Во-первых, поскольку сложность операции линейная, это задачу точно не усложнит. А значит, это целесообразно. Во-вторых, это сразу позволяет свести задачу для произвольного графа к задаче для ациклического графа. Ну а в-третьих, пока еще никто в данном треде не предложил лучшего алгоритма.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
В данном случае (несколько миллионов вершин) играет роль именно асимптотическая сложность задачи.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
13.02.2010 13:34
|
|
|
Ну неправда это. Никогда не влияет 'только асимптотическая сложность'. Нету у нас бесконечностей, нету. Асимптотика - это просто подсказка, как не считая все точно прикинуть время работы.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
13.02.2010 13:35
|
|
|
Если алгоритм линейный, то разбиение на компоненты связности может замедлить работу в полтора-два раза. В зависимости от линейности двух частей алгоритма.
Ладно, я начинаю думать и писать, ты бы тоже написал, полезно будет.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
13.02.2010 13:36
|
|
|
Quote:
Во-вторых, это сразу позволяет свести задачу для произвольного графа к задаче для ациклического графа
Это аргумент (пока индуктивный). Все остальное - нет.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
Первое и третье утверждения относятся вот к чему:
В ответ на:
Сначала ты предлагаешь разбивать на сильно связные компоненты и выдаешь это за решение, хотя никто не говорил, что эти компоненты большие и это сильно упростит задачу.
Решение было приведено ранее, вопрос в том, насколько оно хорошее. А разбиение на компоненты лишь потенциально может усложнить задачу в 2 раза, и только в том случае, если кто-то предложит линейный алгоритм, не использующий это разбиение. А этого пока никто не сделал.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
В ответ на:
Ладно, я начинаю думать и писать, ты бы тоже написал, полезно будет.
Предлагаю подумать, какова была бы сложность решения задачи, если изначально было бы известно, что граф ациклический. Ясно, что сложность решения для произвольного графа не меньше сложности решения для ациклического. А тут, мне кажется, все плохо. Не получается придумать линейный алгоритм, а только квадратичный. Если вершин у нас порядка 10^6, то операций будет порядка 10^12.
|
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: FMX]
13.02.2010 13:52
|
|
|
Quote:
Не получается придумать линейный алгоритм, а только квадратичный.
Квадратичный алгоритм можно написать без заморочек: для каждой вершины делаем полный обход графа, выставляя флажки, и все.
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
|
В общем случае решать неинтересно и лениво (но я попробую все равно, пусть будет).
Все-таки ты пояснишь, что там с двудольностью, циклами? Скажи уже все, что о нем знаешь наверняка.
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
Да, но такой алгоритм квадратичен всегда (сложность - "тета от N"), где N - число вершин.
А заморочки позволяют его сделать квадратичным лишь в самых плохих случаях.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
|
Это ты сказал V * (V + E), это чуть хуже, чем просто квадратично.
|
|
|
unkulunkulu
|
|
unkulunkulunkulu
|
|
|
|
|
|
|
Рег.: 12.11.2006
|
|
Сообщений: 18453
|
|
Из: 13000
|
|
Рейтинг: 11759
|
|
|
А, ну кстати там, насколько я понимаю V почти равно E, даже не в два раза отличие. вот это странно.
Или там у тебя номера вершин как-то сильно раскиданы?
|
|
|
FMX
|
|
Математег
|
|
|
|
|
|
|
Рег.: 29.05.2006
|
|
Сообщений: 3744
|
|
|
|
Рейтинг: 1502
|
|
|
Например, можно считать, что сложность алгоритма O(E + V*N), где N - максимальное число "родителей" вершины ациклического графа. Например, если N = log V, то квадратичности может и не быть. В случае с ромбами, N будет порядка V (для листовых вершин), и суммарная сложность O(E + V^2).
|
|
DarkGray
|
|
Carpal Tunnel
|
|
|
|
|
|
|
Рег.: 30.09.2002
|
|
Сообщений: 31410
|
|
|
|
Рейтинг: 8951
|
|
|
в чем кстати смысл ребер в самих себя?
|
|
|
Grey_DeMonstr
|
|
Software Fiend
|
|
|
|
|
|
|
Рег.: 04.04.2005
|
|
Сообщений: 5517
|
|
Из: .
|
|
Рейтинг: 2400
|
|
Re: Подскажите хороший алгоритм...
[re: DarkGray]
13.02.2010 17:45
|
|
|
Quote:
в чем кстати смысл ребер в самих себя?
А такие есть? Вообще-то не должно быть. Граф совершенно точно двудольный. Про циклы четной длины - мой косяк, конечно же. Циклы могут быть. V примерно равно E, тоже правда.
|
У меня все работает. Что я делаю неправильно?
Сага об XYZ |
|
Список
Плоский
Дерево
