Форум на Исходниках.RU https://forum.sources.ru Форум на Исходниках.RU Форум на Исходниках.RU https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770537 Tue, 29 May 2018 18:40:42 +0000 Некоторые уточнения про терпеливую сортировку https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770537 Цитата FasterHarder @
Придется делать динамический, но без расширения, иначе снова падает производительность.
Производительность падает не сильно, если при заполнении массив увеличивать не по арифметической прогрессии, а по геометрической.
Цитата FasterHarder @
что понимать под "брать стек из вершины пирамиды"
перечитай ещё раз описание пирамидальной сортировки. Вторую часть, где выбирается первый элемента, и пирамида пересыпается.
Цитата FasterHarder @
3. берем элемент из вершины МИНИМАЛЬНОЙ пирамиды и засовываем в соот-щий элемент исходного массива.
Это всегда первый элемент массива, в котором построена пирамида.
Цитата FasterHarder @
скорость у нее ТОПовая, разумеется, но кодировать не очень просто
Вовсе не топовая. Хотя и построение стеков (с использованием двоичного поиска) и выборка отсортированных записей с использованием дерева Флойда имеют сложность O(N log N), тем не менее коэффициент у алгоритма получается заметно больше, чем у быстрой, к примеру сортировки, причём последняя ещё и обходится памятью O(log N) для стека, а этот алгоритм требует O(N). При наличии такой памяти (даже вполовину меньше) практичнее воспользоваться каким-нибудь вариантом сортировки слиянием, который в таком случае часто оказывается быстрее даже лучших реализаций быстрой сортировки.

Добавлено
Цитата OpenGL @
даже самый банальный quicksort будет быстее из-за того, что он весьма локальный по отношению к кешу.
Он будет быстрее, даже если вовсе отключить кэш (естественно у обоих алгоритмов).]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770517 Tue, 29 May 2018 12:15:09 +0000 Некоторые уточнения про терпеливую сортировку https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770517 Цитата FasterHarder @
хотя скорость у нее ТОПовая

Была бы топовой - было бы больше информации о ней. Думаю, что даже самый банальный quicksort будет быстее из-за того, что он весьма локальный по отношению к кешу.]]> OpenGL Алгоритмы https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770514 Tue, 29 May 2018 11:56:05 +0000 Некоторые уточнения про терпеливую сортировку https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770514 Цитата amk @
В описании написано про массив стеков, а ты почему-то используешь список.

это лишь пример! просто в одном из описаний говорилось про СПИСОК СТЕКОВ! Если будет список - не будет двоичного поиска для вставки очередного элемента в нужный стек ----> резко ухудшаются показатели алгоритма сортировки! Поэтому только одномерный массив, но он будет не статическим, т к кол-во элементов, которые нужно отсортировать заранее неизвестно. Придется делать динамический, но без расширения, иначе снова падает производительность. Придется сразу выделить памяти столько, чтобы вместились все элементы исходного массива, т к теоретически возможно, что кол-во стеков будет = кол-ву элементов, это будет в том случае, если элементы исходного массива уже упорядочены по возрастанию.

Цитата amk @
Для выборки берётся стек из вершины пирамиды.

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

Грубо говоря, визуально может выглядеть так как-нить:
__________________________________.jpg (, : 1164)

Цитата amk @
Там же написано - подпоследовательности. В подпоследовательности элементы совсем не обязательно должны выбираться подряд.

а вот я не знаю, имеется ввиду смежные элементы должны быть или допустимы разрывы...ну, наверное, ты прав, что могут быть разрывы....
Цитата amk @
Сортировка, кстати, нестабильная

нуууу, да, только неустойчивая вроде...

Цитата amk @
Кстати, самый плохой случай для алгоритма - уже отсортированная последовательность, тогда для каждой записи создаётся новый стек, и при выдаче приходится максимально пересыпать сортирующую пирамиду. С пирамидой, впрочем можно справиться, если использовать какую-нибудь другую реализацию приоритетной очереди.

согласен полностью

Только сдается мне, что терпеливая сортировка крайне непопулярна в принципе, т к ее описаний практически нету полноценных, хотя скорость у нее ТОПовая, разумеется, но кодировать не очень просто :whistle:

Добавлено
Подытожим коротко все это:
1. формируем одномерный массив, состоящий из стеков (для этого нужно 1 раз полностью просканировать исходный массив)
2. получаем пирамиду, привязывая к ней стеки, причем просеивать ничего не нужно, т к элементы, стоящие на вершинах стека сами по себе образуются возрастающую последовательность
3. берем элемент из вершины МИНИМАЛЬНОЙ пирамиды и засовываем в соот-щий элемент исходного массива.
4. перестраиваем пирамиду
5. когда в пирамиде не осталось элементов, то в исходном массиве элементы идут по возрастанию. Типа все!

*можно при большом желании еще получить саму НВП, но для этого придется чуток усложнить структуры данных либо использовать вспомогат.память...]]> FasterHarder Алгоритмы https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770314 Sat, 26 May 2018 22:22:15 +0000 Некоторые уточнения про терпеливую сортировку https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770314 Цитата FasterHarder @
для терпеливой сортировки потребуется одномерный массив СТЕКОВ (хотя структуры можно брать и др. типа невыровненного массива как в C#).
Одномерный массив описывается динамическим односвязным списком (ЛОС).

Цитата FasterHarder @
В описании говорят, что находит стек, куда нужно вставлять текущее число массива, надо при помощи ДВОИЧНОГО ПОИСКА(дихотомия). Все бы ничего, но ведь мы используем СПИСОК,а у его элементов НЕТ встроенного индексатора!
В описании написано про массив стеков, а ты почему-то используешь список. Стеков заводится не так много, так что ты не много потеряешь, если занесёшь указатели на них в массив (вектор). Это тем более имеет смысл, так как стеки в таком массиве всё время остаются упорядоченными по возрастанию своих вершин, и добавление в стек нового элемента этот порядок не нарушает. Да и новый стек если и добавляется, то только в конец массива.
Цитата FasterHarder @
непонятно, на каком этапе сортировки нужно строить эту пирамиду?
На этапе слияния содержимого стеков. Создаётся приоритетная очередь стеков. При создании даже не надо делать перестройку пирамиды, стеки уже идут в нужном порядке. Для выборки берётся стек из вершины пирамиды. Если после извлечения данных стек не пуст, значение в вершине заменяется и пирамида пересыпается. Если пуст, в вершину перемещается вершина из конца и пирамида тоже пересыпается.
Цитата FasterHarder @
в исходном массиве нет ни одной цепочки НВП длиной 3
Там же написано - подпоследовательности. В подпоследовательности элементы совсем не обязательно должны выбираться подряд. R примеру, в последовательности 1 4 2 3, тоже создающей три стека, НВП отмечена цветом.
В твоей последовательности несколько таких подпоследовательностей, например: 8 90 16 89 12 -8 55 34

Сортировка, кстати, нестабильная - меняет порядок равных элементов. После сортировки они оказываются в порядке, обратом исходному.

Алгоритм хорош в том смысле, что тратит мало времени при вводе очередной порции данных, и так же немного тратит на выбор очередной записи в отсортированном порядке. И почти не имеет лага между вводом несортированных данных и выводом сортированных. Похожее поведение имеет алгоритм пирамидальной сортировки, но у него явно константы больше. С другой стороны, для организации приоритетной очереди он, похоже, не подходит - после выдачи части записей, перед вставкой новых наверняка потребуется переупорядочивание стеков. Хотя возможно, это переупорядочивание будет не так сильно тормозить алгоритм.

Добавлено
Кстати, самый плохой случай для алгоритма - уже отсортированная последовательность, тогда для каждой записи создаётся новый стек, и при выдаче приходится максимально пересыпать сортирующую пирамиду. С пирамидой, впрочем можно справиться, если использовать какую-нибудь другую реализацию приоритетной очереди.]]> amk Алгоритмы https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770299 Sat, 26 May 2018 14:44:51 +0000 Некоторые уточнения про терпеливую сортировку https://forum.sources.ru/index.php?showtopic=412828&view=findpost&p=3770299 Есть некоторые уточняющие вопросы относительно терпеливой сортировки, хотя основная идея там понятна...
Скрытый текст
вообще по точному запросу "терпеливая сортировка" гугл выдает 31 ответ, всего 31 ответ, Карл!
по запросу "сортировка терпеливая" вообще 7.
К примеру, по запросу "быстрая сортировка" ответов 35 400, а, например, по запросу "пирамидальная сортировка" 8 410 результатов.
Т е я делаю вывод, что информации про ТЕРПЕЛИВУЮ сортировки нет, тупо ее около нуля...


Как я понимаю, для терпеливой сортировки потребуется одномерный массив СТЕКОВ (хотя структуры можно брать и др. типа невыровненного массива как в C#).
Одномерный массив описывается динамическим односвязным списком (ЛОС).
Пример описания такой структуры данных на языке Паскаль/Дельфи:
    type
        TPtrStack = ^TStack;
        TStack = record     // описание стека для хранения стопки целых чисел
    // сортируем целые числа, хотя можно взять ЛЮБОЙ тип данных, в том числе и составной    
            inf: integer;  
            link: TPtrStack;    // указатель на след.элемент стека (типа ниже)
        end;
        TPtrList = ^TList;
        TList = record      // ЛОС для связи стеков целых чисел
            stack : TStack;     // в качестве информ.поля выступает стек целых чисел
            next: TPtrList;     // указатель на след.элемент списка стеков
        end;
    begin
    end.


Пример: нужно отсортировать patience sorting следующие данные
8 90 16 89 12 -8 55 34
До обработки ЛОС пуст, т е ЛОС = NIL. В нет нет ни одного стека/стопки.
обработка 1-го элемента: 8
ЛОС
1 стек: 8
------------------------------
обработка 2-го элемента: 90
ЛОС
1 стек: 8
2 стек: 90
------------------------------
обработка 3-го элемента: 16
ЛОС
1 стек: 8
2 стек: 90 16
------------------------------
обработка 4-го элемента: 89
ЛОС
1 стек: 8
2 стек: 90 16
3 стек: 89
------------------------------
обработка 5-го элемента: 12
ЛОС
1 стек: 8
2 стек: 90 16 12
3 стек: 89
------------------------------
обработка 6-го элемента: -8
ЛОС
1 стек: 8 -8
2 стек: 90 16 12
3 стек: 89
------------------------------
обработка 7-го элемента: 55
ЛОС
1 стек: 8 -8
2 стек: 90 16 12
3 стек: 89 55
------------------------------
обработка 8-го (последнего) элемента: 34
ЛОС
1 стек: 8 -8
2 стек: 90 16 12
3 стек: 89 55 34
=====================================
Т е в данном случае для обработки 8 элементов потребовалось задействовать 3 стека.
Правило вставки простое: просматриваются стеки от №1 вниз и, если текущее число меньше числа на вершине текущего стека, то добавляем текущее число в вершину этого стека.
Также нужно заметить, что элементы, стоящие на вершинах стека идут на возрастание.
ТАК ВОТ! В описании говорят, что находит стек, куда нужно вставлять текущее число массива, надо при помощи ДВОИЧНОГО ПОИСКА(дихотомия). Все бы ничего, но ведь мы используем СПИСОК,а у его элементов НЕТ встроенного индексатора!
Поэтому приходится искать нужный стек только полным сканированием всех стеков, начиная от №1 и дальше??
Если бы вместо списка использовался массив, тогда да, можно было бы воспользоваться дихотомией. Или в данном случае использование ЛОС неоправданно и нужно использовать динамический массив, элементы которого TStack
    var
        list: array of TStack;

и в программе просто расширять его, когда добавляется новый стек для чисел.
На этом 1-й этап терпеливой сортировки закончен.
==========================================================
Сейчас нужно "вынимать" минимальный элемент среди всех вершинных элементов и записывать в результирующий массив.
Я могу это легко сделать, если постоянно обходить все вершинные элементы и находить среди них минимальный. Но это будет крайне неэффективно вроде.
В описании говорят, что мол надо задействовать бинарную кучу (пирамиду) для поиска минимальных.
Но мне непонятно, на каком этапе сортировки нужно строить эту пирамиду?

И последнее, говорится, что количество стеков/стопок показывает длину наибольшей возрастающей подпоследовательности в исходном массиве.
У меня в примере 3 стопки, но в исходном массиве нет ни одной цепочки НВП длиной 3.. странно...

В целом интересный алгоритм, но его нужно кодировать с применением правильных структур данных
спс. за внимание!]]> FasterHarder Алгоритмы