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

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

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

Suslik
> раз уж тут все собрались, то спрошу в этом треде, не создавая нового. требуется найти или придумать алгоритм, суть в следующем. имеется N отсортированных списков, каждый пусть будет по M элементов. требуется проитерироваться в порядке сортировки по всем NM элементов быстрее, чем за MN^2, используя не более чем O(N) памяти. сами списки менять (сливать, например), запрещено, нужно именно проитерироваться по результату их слияния без сохранения этого результата
У тя сложность M*N^2 потому что на каждой из M*N шагов выбираешь min из N, сделай Heap для N минимумов, при взятии top с Heap - заменяешь его следующим эл-том в соотв-м списке и корректируешь Heap за log(N), итого сложность M*N*log(N)

#31
(Правка: 13:28) 13:21, 11 июля 2019

Раз уж тут все собрались, то вброшу алгоритм, который может кому-то пригодится:

Часто в задачах с графами встречается подзадача - разбить граф, заданный набором ребер (парами вершин), на связные компоненты.

Простое решение: для каждой вершины введем поля next и id (номер компонента). В начале N связных списков (компонентов) по одной вершине и N структур компонентов (head, tail, size).
В цикле по ребрам, если вершины с разными id (из  разных компонентов) - объединяем компоненты, дописывая меньший в хвост большего и меняя id его элементов.
Сложность работы O(N)

#32
13:48, 11 июля 2019

Suslik
> там советуют строить хип над головами списков. это даст сложность O(MN log N), что мне, вроде как, нравится, но слишком уж громоздкий шейдер получится
Разве громоздкий? По моему, относительно простой, к тому же хорошо параллелится.
А если количество списков — константа, то можно и branchless-версию запилить

#33
13:57, 11 июля 2019

Aslan
> Простое решение
Запустить обход из каждой вершины?

#34
14:09, 11 июля 2019

1 frag / 2 deaths
> Запустить обход из каждой вершины?
рекурсия + сначала заполнить для каждой список соседей
мое решение короче

#35
(Правка: 14:18) 14:16, 11 июля 2019

Aslan
> Сложность работы O(N)
ничё там не O(N), так как в общем случае вершины могут выстраиваться в цепочку при объединении и когда сливаешь две компоненты связности, сложность слияния может вырасти до O(M), M — кол-во вершин, в результате увеличивая сложность алгоритма до O(NM). правильная версия алгоритма реализуется на disjoint set union, который начинается так же, как твой велосипед, но реализует несколько более хитрых идей, которые уменьшают сложность до O(M log* N), где log* — это итерированный логарифм, само существование которого представляет определённый интерес.

}:+()___ [Smile]
> Разве громоздкий? По моему, относительно простой, к тому же хорошо
> параллелится.
попробую

#36
15:05, 11 июля 2019

Suslik
Достаточно при слиянии смотреть, кто больше, а кто меньше, и переименовывать иды только в меньшем.

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

Suslik
Время объединения двух компонент связности = размер меньшей, на столько возрастает большая, сумма всех этих приращений <=N

#38
17:15, 11 июля 2019

Aslan
> сделай Heap для N минимумов, при взятии top с Heap - заменяешь его следующим
> эл-том в соотв-м списке и корректируешь Heap за log(N), итого сложность
> M*N*log(N)
Для описанного сусликом случая хип будет медленным. У него там 5-10 элементов в этом списке будет. Просеивание кучи после каждой итерации на таком маленьком массиве не самый лучший вариант.

#39
(Правка: 21:36) 21:35, 11 июля 2019

Suslik
Вот набросал пример с поддерживанием голов на куче:

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

void siftDown(int* heads, int idx) {
  while (true) {
    int leftIdx = 2*idx + 1;
    if (leftIdx >= N) return;
    int rightIdx = 2*idx + 2;
    int minChild;
    if (rightIdx < N) {
      minChild = ( GetPointsData(heads[leftIdx]) > GetPointsData(heads[rightIdx]) ) ? leftIdx : rightIdx;
    } else {
      minChild = leftIdx;
    }

    if (GetPointsData(heads[idx]) >= GetPointsData(heads[minChild])) return;
    int tmp = heads[idx];
    heads[idx] = heads[minChild];
    heads[minChild] = tmp;
    idx = minChild;
  }
}

void heapify(int* heads) {
  for (int i = N%2 - 1; i < 0; i--) {
    siftDown(heads, i);
  }
}

int heads[N];
heapify(heads); //строим кучу

while (heads[0] != -1) {
  process(points[heads[0]].data); //обрабатываем минимальную data
  heads[0] = points[heads[0]].next; //апдейтим голову
  siftDown(heads, 0); //поддерживаем инвариант кучи по data
}
Но он для 5-10 элементов будет 100% медленнее, чем тот вариант, который я приводил тут:
https://gamedev.ru/code/forum/?id=245502&page=2&m=5008830#m28
Хотя алгоритмическая сложность да, стала M*N*Log(N)
#40
(Правка: 22:01) 21:45, 11 июля 2019

MrShoor
int tmp = heads[idx];
    heads[idx] = heads[minChild];
    heads[minChild] = tmp;
    idx = minChild;

Лишние записи в память, запомни верхний элемент и в цикле копируй вверх нижние, в конце присвой нижнему

void ShiftDown(int* heads, int idx) {
    int el=heads[idx];
    while(true) {
        int idx2=2*idx+1;
        if(idx2>=N) break;
        idx2+=(idx2+1<N && GetPointsData(heads[idx2+1])<GetPointsData(heads[idx2]));
        if(GetPointsData(heads[idx])<=GetPointsData(heads[idx2])) break;
        heads[idx]=heads[idx2];
        idx=idx2;
    }
    heads[idx]=el;
}
#41
21:47, 11 июля 2019

MrShoor
> Но он для 5-10 элементов будет 100% медленнее
Если округлить N до (2^n-1), то код станет гораздо проще.

#42
21:58, 11 июля 2019

Aslan
> Лишние записи в память, запомни верхний элемент и в цикле копируй вверх нижние,
> в конце присвой нижнему
Не вижу лишних записей в память, и не понимаю что ты предлагаешь сделать. Можешь кодом показать?

}:+()___ [Smile]
> Если округлить N до (2^n-1), то код станет гораздо проще.
Да, но будет всё так же безнадежно медленнее кода из #28 поста.

#43
22:02, 11 июля 2019

MrShoor
Добавил код в предыдущий пост

#44
22:54, 11 июля 2019

Aslan
> Добавил код в предыдущий пост
Да, теперь понял что ты имел ввиду. Да, так будет лучше.
p.s. Единственно - ты помоему знак не в ту сторону тут поставил:

if(GetPointsData(heads[idx])<=GetPointsData(heads[idx2])) break;
Страницы: 1 2 3 4 Следующая »
ПрограммированиеФорумОбщее