Наши проекты:
Журнал · Discuz!ML · Wiki · DRKB · Помощь проекту |
||
ПРАВИЛА | FAQ | Помощь | Поиск | Участники | Календарь | Избранное | RSS |
[3.146.221.52] |
|
Сообщ.
#1
,
|
|
|
Всем хай! Сходу к делу!
Есть некоторые уточняющие вопросы относительно терпеливой сортировки, хотя основная идея там понятна... Скрытый текст вообще по точному запросу "терпеливая сортировка" гугл выдает 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.. странно... В целом интересный алгоритм, но его нужно кодировать с применением правильных структур данных спс. за внимание! |
Сообщ.
#2
,
|
|
|
Цитата FasterHarder @ для терпеливой сортировки потребуется одномерный массив СТЕКОВ (хотя структуры можно брать и др. типа невыровненного массива как в C#). Одномерный массив описывается динамическим односвязным списком (ЛОС). Цитата FasterHarder @ В описании написано про массив стеков, а ты почему-то используешь список. Стеков заводится не так много, так что ты не много потеряешь, если занесёшь указатели на них в массив (вектор). Это тем более имеет смысл, так как стеки в таком массиве всё время остаются упорядоченными по возрастанию своих вершин, и добавление в стек нового элемента этот порядок не нарушает. Да и новый стек если и добавляется, то только в конец массива.В описании говорят, что находит стек, куда нужно вставлять текущее число массива, надо при помощи ДВОИЧНОГО ПОИСКА(дихотомия). Все бы ничего, но ведь мы используем СПИСОК,а у его элементов НЕТ встроенного индексатора! Цитата FasterHarder @ На этапе слияния содержимого стеков. Создаётся приоритетная очередь стеков. При создании даже не надо делать перестройку пирамиды, стеки уже идут в нужном порядке. Для выборки берётся стек из вершины пирамиды. Если после извлечения данных стек не пуст, значение в вершине заменяется и пирамида пересыпается. Если пуст, в вершину перемещается вершина из конца и пирамида тоже пересыпается.непонятно, на каком этапе сортировки нужно строить эту пирамиду? Цитата FasterHarder @ Там же написано - подпоследовательности. В подпоследовательности элементы совсем не обязательно должны выбираться подряд. R примеру, в последовательности 1 4 2 3, тоже создающей три стека, НВП отмечена цветом.в исходном массиве нет ни одной цепочки НВП длиной 3 В твоей последовательности несколько таких подпоследовательностей, например: 8 90 16 89 12 -8 55 34 Сортировка, кстати, нестабильная - меняет порядок равных элементов. После сортировки они оказываются в порядке, обратом исходному. Алгоритм хорош в том смысле, что тратит мало времени при вводе очередной порции данных, и так же немного тратит на выбор очередной записи в отсортированном порядке. И почти не имеет лага между вводом несортированных данных и выводом сортированных. Похожее поведение имеет алгоритм пирамидальной сортировки, но у него явно константы больше. С другой стороны, для организации приоритетной очереди он, похоже, не подходит - после выдачи части записей, перед вставкой новых наверняка потребуется переупорядочивание стеков. Хотя возможно, это переупорядочивание будет не так сильно тормозить алгоритм. Добавлено Кстати, самый плохой случай для алгоритма - уже отсортированная последовательность, тогда для каждой записи создаётся новый стек, и при выдаче приходится максимально пересыпать сортирующую пирамиду. С пирамидой, впрочем можно справиться, если использовать какую-нибудь другую реализацию приоритетной очереди. |
Сообщ.
#3
,
|
|
|
Цитата amk @ В описании написано про массив стеков, а ты почему-то используешь список. это лишь пример! просто в одном из описаний говорилось про СПИСОК СТЕКОВ! Если будет список - не будет двоичного поиска для вставки очередного элемента в нужный стек ----> резко ухудшаются показатели алгоритма сортировки! Поэтому только одномерный массив, но он будет не статическим, т к кол-во элементов, которые нужно отсортировать заранее неизвестно. Придется делать динамический, но без расширения, иначе снова падает производительность. Придется сразу выделить памяти столько, чтобы вместились все элементы исходного массива, т к теоретически возможно, что кол-во стеков будет = кол-ву элементов, это будет в том случае, если элементы исходного массива уже упорядочены по возрастанию. Цитата amk @ Для выборки берётся стек из вершины пирамиды. ну, как бэ, что понимать под "брать стек из вершины пирамиды", т к сам по себе стек как таковой не нужен, нужны элементы на его вершинах. Вообще, получается, что разные структуры данных будут ссылаться на одни и те же элементы. Грубо говоря, визуально может выглядеть так как-нить: Прикреплённая картинка
Цитата amk @ Там же написано - подпоследовательности. В подпоследовательности элементы совсем не обязательно должны выбираться подряд. а вот я не знаю, имеется ввиду смежные элементы должны быть или допустимы разрывы...ну, наверное, ты прав, что могут быть разрывы.... Цитата amk @ Сортировка, кстати, нестабильная нуууу, да, только неустойчивая вроде... Цитата amk @ Кстати, самый плохой случай для алгоритма - уже отсортированная последовательность, тогда для каждой записи создаётся новый стек, и при выдаче приходится максимально пересыпать сортирующую пирамиду. С пирамидой, впрочем можно справиться, если использовать какую-нибудь другую реализацию приоритетной очереди. согласен полностью Только сдается мне, что терпеливая сортировка крайне непопулярна в принципе, т к ее описаний практически нету полноценных, хотя скорость у нее ТОПовая, разумеется, но кодировать не очень просто Добавлено Подытожим коротко все это: 1. формируем одномерный массив, состоящий из стеков (для этого нужно 1 раз полностью просканировать исходный массив) 2. получаем пирамиду, привязывая к ней стеки, причем просеивать ничего не нужно, т к элементы, стоящие на вершинах стека сами по себе образуются возрастающую последовательность 3. берем элемент из вершины МИНИМАЛЬНОЙ пирамиды и засовываем в соот-щий элемент исходного массива. 4. перестраиваем пирамиду 5. когда в пирамиде не осталось элементов, то в исходном массиве элементы идут по возрастанию. Типа все! *можно при большом желании еще получить саму НВП, но для этого придется чуток усложнить структуры данных либо использовать вспомогат.память... |
Сообщ.
#4
,
|
|
|
Цитата FasterHarder @ хотя скорость у нее ТОПовая Была бы топовой - было бы больше информации о ней. Думаю, что даже самый банальный quicksort будет быстее из-за того, что он весьма локальный по отношению к кешу. |
Сообщ.
#5
,
|
|
|
Цитата FasterHarder @ Производительность падает не сильно, если при заполнении массив увеличивать не по арифметической прогрессии, а по геометрической.Придется делать динамический, но без расширения, иначе снова падает производительность. Цитата FasterHarder @ перечитай ещё раз описание пирамидальной сортировки. Вторую часть, где выбирается первый элемента, и пирамида пересыпается.что понимать под "брать стек из вершины пирамиды" Цитата FasterHarder @ Это всегда первый элемент массива, в котором построена пирамида.3. берем элемент из вершины МИНИМАЛЬНОЙ пирамиды и засовываем в соот-щий элемент исходного массива. Цитата FasterHarder @ Вовсе не топовая. Хотя и построение стеков (с использованием двоичного поиска) и выборка отсортированных записей с использованием дерева Флойда имеют сложность O(N log N), тем не менее коэффициент у алгоритма получается заметно больше, чем у быстрой, к примеру сортировки, причём последняя ещё и обходится памятью O(log N) для стека, а этот алгоритм требует O(N). При наличии такой памяти (даже вполовину меньше) практичнее воспользоваться каким-нибудь вариантом сортировки слиянием, который в таком случае часто оказывается быстрее даже лучших реализаций быстрой сортировки. скорость у нее ТОПовая, разумеется, но кодировать не очень просто Добавлено Цитата OpenGL @ Он будет быстрее, даже если вовсе отключить кэш (естественно у обоих алгоритмов). даже самый банальный quicksort будет быстее из-за того, что он весьма локальный по отношению к кешу. |