Войти
ПрограммированиеФорумОбщее

Сортировка однонаправленного списка за O(N log N) без рекурсии (2 стр)

Страницы: 1 2 3 4 5 Следующая »
#15
(Правка: 7:22) 7:22, 11 июля 2019

Suslik
> а, ну в смысле проитерироваться отсортированно. добавил.
У меня такое ощущение, что тебе нужен bitonic sort на одном большом списке. Вместо сортировки кучи мелких списоков и какого-то мержа. Не?

#16
(Правка: 7:27) 7:24, 11 июля 2019

Ghost2
> Ну, это каждый должен для себя выяснить, когда начинает копаться в алгоритмах сортировки ;)
каждый посчитал своим, блин, священным долгом прийти и на это указать. когда суть-то была не в том, что insert sort быстрее merge sort для мелких списков (это и так понятно), а в том, что быстрее до 60 элементов (много) и быстрее bubble sort (хотя алгоритмы похожие).

MrShoor
> У меня такое ощущение, что тебе нужен bitonic sort на одном большом списке.
> Вместо сортировки кучи мелких списоков и какого-то мержа. Не?
как я уже сказал, мелкие отсортированные списки даны и их менять нельзя. они в readonly памяти. по ним можно только итерироваться. так вот нужно проитерироваться по ним, без выделения памяти для общего большого списка.

#17
(Правка: 7:30) 7:30, 11 июля 2019

Suslik
> мелкие отсортированные списки даны
Как они даны, если ты их изначально сортируешь? Что мешает построить рядом индексы и сделать bitonic для индексов? А потом итерируйся по индексам сколько угодно.

#18
7:32, 11 июля 2019

Suslik
> так вот нужно проитерироваться по ним, без
> выделения памяти для общего большого списка.
Странные ограничения. Помоему искуственные ограничения.

#19
(Правка: 7:38) 7:34, 11 июля 2019

MrShoor
> Как они даны, если ты их изначально сортируешь? Что мешает построить рядом
> индексы и сделать bitonic для индексов?
представь, что есть тысяча списков. мы их отсортировали. суммарное количество элементов в них — допустим, миллон. то есть, грубо говоря, несколько мегабайт памяти. хочется уметь выбирать из этой тысячи списков каждый кадр миллион случайных групп по N=5..10 списков и проитерироваться по ним всем в отсортированном порядке внутри каждой группы. группы могут как угодно пересекаться, каждый список потенциально принадлежит многим группам. памяти для хранения каждой группы не хватит, да и не нужно это, так как нужно только проитерироваться и что-то сделать. каждая группа обрабатывается в своём треде на GPU, поэтому памяти у неё, считай, O(N).

#20
7:44, 11 июля 2019

Suslik

> каждый посчитал своим, блин, священным долгом прийти и на это указать
Извини, мне очень жаль.

> а в том, что быстрее до 60 элементов (много) и быстрее bubble sort (хотя алгоритмы похожие).
Да, такое вот большое "O" - все нужно проверять.

#21
(Правка: 7:49) 7:48, 11 июля 2019

вот нашёл обсуждение проблемы итерирования по отсортированным спискам: https://stackoverflow.com/questions/46900859/given-k-sorted-lists… rted-iterator
там советуют строить хип над головами списков. это даст сложность O(MN log N), что мне, вроде как, нравится, но слишком уж громоздкий шейдер получится, да и строить хип вокруг 10 списков — оверкилл. мне кажется, можно проще. что если отсортировать головы списков через insertion sort (O(N) памяти), потом брать минимальный элемент, итерировать и перевставлять обратно в список голов?

#22
7:50, 11 июля 2019

Suslik
> и перевставлять обратно в список голов?

Ну вот эта перевставка и начнёт выходить на сложность M^2. У них наверное хип как раз подавляет её до M*log(M).

#23
(Правка: 7:54) 7:52, 11 июля 2019

=A=L=X=
> Ну вот эта перевставка и начнёт выходить на сложность M^2
да, так и есть. но, у insertion sort, как показали опыты выше, результирующая сложность O(N^2) меньше, чем у более продвинутых методов вроде хипа с O(N log N) и константа при квадрате меньше, чем если каждый раз минимум искать (аналог пузыря). для небольших групп списков (5-10).

#24
7:57, 11 июля 2019

Suslik

Ну ты выше писал про тысячу списков. Если 5-10, то надо просто тестировать.

#25
(Правка: 7:59) 7:58, 11 июля 2019

=A=L=X=
списков-то тысяча. групп миллион. но в каждой группе — по 5-10 списков из той тысячи. так вот итерироваться нужно внутри каждой группы отдельно, по одной группе на тред шейдера.

#26
8:12, 11 июля 2019

Suslik

Так а если списков всего 5-10, то может ну его нафиг вообще сортировки и просто банально искать меньшее каждый раз влоб?

#27
8:14, 11 июля 2019

=A=L=X=
> Так а если списков всего 5-10, то может ну его нафиг вообще сортировки и просто банально искать меньшее каждый раз влоб?
искать минимум — гарантированно N операций. поддерживать отсортированный список insertion sort'ом — вроде бы, N/2 операций в среднем, если считать, что элементы равномерно распределены.

#28
(Правка: 8:52) 8:49, 11 июля 2019

Suslik
Моё влобное решение:

float GetPointsData(int idx) {
  if (idx == -1) return MAX_VALUE;
  return points[idx].data;
}

int heads[N];
SortHeads(heads); //сортируем головы по data полю

while (heads[0] != -1) {
  process(points[heads[0]].data); //обрабатываем минимальную data
  heads[0] = points[heads[0]].next; //апдейтим голову

  for (int i = 0; i < N-1; i++) { //поддерживаем инвариант по минимальной data
    if (GetPointsData(heads[i]) > GetPointsData(heads[i+1])) {
      int tmp = heads[i+1];
      heads[i+1] = heads[i];
      heads[i] = tmp;      
    } else {
      break; //выходим из цикла раньше, если можно
    }
  }
}
Worst case M*N^2 при потреблении памяти N, но т.к. есть ранний выход из цикла с поддержкой инварианта то средний случай мне кажется будет намного лучше, чем M*N^2
#29
(Правка: 9:23) 9:22, 11 июля 2019

Suslik
> если использовать insertion sort вместо первых этапов работы merge sort'а
Ну вообщето так и делают всегда. Плюсом если элементов будет мало - автоматически заюзается более быстрый вариант, поэтому твой мердж сорт начнет заруливать и в низах с малым числом элементов

Страницы: 1 2 3 4 5 Следующая »
ПрограммированиеФорумОбщее