А странички здесь при чём? Результат структуризации — это набор метаданных, а не сами данные.
А там не остаются метаданные разве?
А зачем смотреть? Надо выделять! Работать в режиме кентавра, а не [только] давать ему задачки в стиле "найди то, не знаю что". :)
Ну, в контексте именно бд, интересует какую более эффективную структуру и метаданные сможет выделить бд самостоятельно, чтобы сравнивать с тем что может выделить из тех же данных человек.
А вообще техника "Синдбадовская": первый байт любого элемента данных всегда метаданные.
Было бы интересно посмотреть на примерный формат хранения метаданных кстати, есть что-то такое, что можно показать?
Не надо ничего менять местами! И алгоритм там простейший — НАМНОГО проще этого LL, который при таком "размытом формате" просто нафиг не нужен! :)
Ну, т.е. LL остается, просто лежит внутри самого элемента? Там кстати будет дополнительное копирование, потому что из OS прилетают не строки, а просто буфер байтов. В контексте тех же юникодных строк это особо не важно, т.к. их все равно желательно нормализовать. Да и в случае сортировки наличие данных внутри LL очень хорошо отразится на производительности (потому что часть данных уже будет в кеше после перехода по указателю).
Есть, и основной — это то, что асимптотики недостаточно.
Для оценки алгоритма достаточно.
Эммм… а можно ссылку на источник, где это написано?
Здравый смысл? У сортировки есть две операции:
1) чтение данных. нет смысла читать без сравнения.
2) запись/swap. нельзя заменить один элемент на другой без сравнения, если не говорить о bogosort и подобных алгоритмах.
"The columns "Average" and "Worst" give the time complexity in each case, under the assumption that the length of each key is constant, and that therefore all comparisons, swaps, and other needed operations can proceed in constant time."
И как это противоречит?
Тоже нет. Седжвик: "Bottom-up mergesort uses between ~ ½ N lg N and N lg N compares and at most 6N lg N array accesses to sort an array of length N. [...] Quicksort uses ~ 2N ln N compares (and one-sixth that many exchanges) on the average to sort an array of length N with distinct keys."
Это уже не асимптотика. Эти вещи имеют довольно мало смысла вне контекста реализации. А в случае реализации там уже появляется кэш CPU, branch prediction,
и прочие штуки, которые очень сложно внятно оценть.
Как видно, некоторым этого недостаточно.
Если не достаточно, то нужно оценивать конкретные реализации.
Гм. То есть то, что merge sort вообще медленнее, чем quick sort, вас не смущает?
Он медленее на некоторых реальных кейсах, которые воронка как раз улучшает. Общий случай у merge sort сильно лучше, чем у quick sort.
Что очень много по сравнению с константой
Там тоже константа, если приходит LL вместо массива. Только в реальности, в большинстве случаев сортируют не массив, а вектор.
Который потратит кучу времени на копирование при добавлении новых элементов, плюс будет хранить большой пустой кусок, чтобы
не копировать все данные на каждой вставке.
Даже между merge и quick разница в разы по тем самым константам, а у patience, как говорилось выше — на порядок (до оптимизации).
Если говорить про базовые реализации merge/quick, то у воронки константы в оптимизированных случаях лучше, в случае рандомных данных не намного хуже чем у merge. У quick там вообще квадрат, что делает бессмысленным его использование в большинстве вещей, даже без констант.
Или-или. Если у вас входящие данные — массив, то вам надо потратить еще sizeof(ptr)*N на создание linked list (а если его не создавать, будут меняться другие оценки).
Я про создание LL из массива/вектора и говорю. Если будет LL, то там константное использование места, BUF_SIZE(1024)3ptr (head, tail, len).
… и если вам нужен массив, то вы тратите еще N времени на обратное копирование.
Если мне нужен LL я точно так же потрачу N времени на копирование из массива в LL. Только в реальности вместо массива обычно вектор, и далеко не всегда известно количество элементов (как в той же сортировке строк), более того, данные могут быть еще и разной длины, а соотвественно на этапе вставки мы будем копировать весь вектор при расширении его размера.
Эти "детали реализации" объясняют, почему quick sort, асимптотика которого хуже, чем merge sort, используется чаще.
Где он используется? Тот же timsort это разновидность merge sort, в других адаптивных алгоритмах (тот же pdqsort) квик сорт в худшем случае заменяется на heapsort, чтобы успеть за O(n*log(N)).
Ха! А кто знает, что это именно "окончания"? Возможно, пробелы и будут наиболее частым символом, но кто сказал, что это разделитель? Статистика по сочетаниям символов может что-то поймать, но приставки это, корни или суффиксы — здесь уже не хило бы иметь дополнительные метаданные.
Возможно и пробел, да. Но есть шанс что окончания у одинаковых лемм будут выделенны в один класс. Поэтому и было интересно посмотреть.
Согласен, всё предельно просто. Хотя есть и нюансы. :)
Ну, нюансы в основном в merge самих списков, быстро прикреплять хвосты и все прочее. Плюс, в самом начале можно без изменений часть головы пропустить.
Что-то еще?
Вот! Мой "размытый" формат хранения (точнее, не формат, а технология) годится для любой сортировки (да и не только сортировки), и там никаких linked list и копирований нет вообще.
Там лишние копирования указателей на строку, остальные алгоритмы тоже при сортировке используют просто вектор указателей на строки, не копировать же их.
А как без LL? Можно конечно менять местами указатели в массиве, но там уже сильно усложняется сам алгоритм.
На буквы я никогда не разбивал. Но, в принципе, какая разница? Разбиваем на атомарные элементы — пусть будут буквы.
А можно посмотреть результат (на том же OSM) в виде графа? (например пачка html страниц, как в случае с транспортов).
Так ведь это просто другой формат представления данных — все зависимости те же, что и в исходных данных.
Ну, как минимум должны появится различные зависимости от структуры языка (всякие окончания и прочее).
Я не помню — я Вам код давал? Может, надо?
Неа, к самому алгоритму вопросов особо нет. Счетчики по количеству сравнений хорошие (в минимальной имплементации правда pdqsort быстрее именно на обратных последовательностях).
Да и пишется он за 10 минут, рисование табличек сильно сложнее.
Проблема в том что тот linked list который есть в языке, он во первых DLL, а во вторых аллоцируется по элементам, а не пачкой. Плюс там судя по всему много копирований.
Вот, хотелось бы увидеть граф после реструктуризации, если слова разбить на буквы (если не сложно),
мне кажется там много довольно интересных зависимостей, ну будет видно как работает реструктуризация.
Ну, и нафига нам все эти сложности? Проще воронки и не бывает алгоритма! :)
Я в целом делаю бенчмарк этого всего, потому и сравниваю с pdqsort. Как разберусь со скоростью LL выложу.
Чем? Для практических задач — никакого интереса: в любом случае отсортирует со свистом.
Для практических задач разницы особой нет. Проблема в том что pdqsort готовый, а воронку нужно писать, что я собственно и делаю.
По счётчикам — наверное. По реальному времени — ближе к линейному.
Это если с чтением/записью. Но их тоже можно сильно оптимизировать, тогда уже начнет влиять логарифм.
Ну, я вроде довольно подробно расписал как считал асимптотику. Если есть какие-то конкретные вопросы, готов на них ответить.
O(N log N) каких операций?
Сравнений. Компаративные алгоритмы сортировки оцениваются именно по ним.
Гм. Если бы это было так, оценки производительности алгоритмов не имели бы смысла, однако они вполне работают.
Оценки это N vs N * log(N) vs N^2. "в полтора раза" это константа, которая зависит от реализации.
Что означает, что нельзя смотреть только на число сравнений, не правда ли?
Для алгоритма вполне можно. Для реализации нельзя.
Медленнее чем что?
Медленее pdqsort.
При том, что алгоритмическая сложность расчитывается исходя из стоимости операций с памятью. И если вы хотите оценивать именно сложность алгоритма, а не скорость имплементации, то надо выписывать алгоритм в псевдокоде и считать операции с памятью.
Алгоритмическая сложность компаративной сортировки расчитывается по количеству операций сравнения. Тут вопросов к воронке лично у меня нет.
… вот только его стоимость будет на порядок отличаться от стоимости операций в памяти, и поэтому баланс операций в памяти и операций с диском будет влиять на общую производительность алгоритма.
И? В любом алгоритме сортировке внешняя сортировка это так или иначе слияние k отсортированных списков, других вариантов особо нет.
А еще, например, то, сколько алгоритм потребляет дополнительной памяти, будет влиять на то, какие объемы входных данных могут (или не могут) быть обработаны чисто в памяти, и это, в свою очередь, будет влиять на оцениваемую производительность.
Алгоритм потребляет размер_указателя*N бит дополнительной памяти. Для всех применений, кроме сортировки массива интов это нормально.
Тогда не понятно, чем вам интересна "воронка", если все ее отличие от существующих алгоритмов — "детали реализации".
От каких существующих алгоритмов? От quick sort/merge sort отличие очевидно в количестве операций сравнения.
От pdqsort отличие в простоте реализации, что потенциально может быть сильно быстрее.
Буфер это список/вектор/массив, в который добавляются LL, когда нужен новый. У него ограничение в 1024 элемента. Когда достигли ограничения в 1024 элемента, этот массив сортируется по количеству элементов в каждом списке, дальше списки сливаются начиная с самого меньшего, по 2 за раз. В целом просто вариация стандартного "k-way merge".
The problem can be solved by iteratively merging two of the k arrays using a 2-way merge until only a single array is left. If the arrays are merged in arbitrary order, then the resulting running time is only O(kn). This is suboptimal.
The running time can be improved by iteratively merging the first with the second, the third with the fourth, and so on. As the number of arrays is halved in each iteration, there are only Θ(log k) iteration. In each iteration every element is moved exactly once. The running time per iteration is therefore in Θ(n) as n is the number of elements. The total running time is therefore in Θ(n log k).
We can further improve upon this algorithm, by iteratively merging the two shortest arrays. It is clear that this minimizes the running time and can therefore not be worse than the strategy described in the previous paragraph. The running time is therefore in O(n log k). Fortunately, in border cases the running time can be better. Consider for example the degenerate case, where all but one array contain only one element. The strategy explained in the previous paragraph needs Θ(n log k) running time, while the improved one only needs Θ(n) running time.
Я не понимаю, что за "данный случай". Что за структура, что за данные
Список адресов вида "г. Город, ул. Улица, ..." (например из OSM) представленные в виде направленного графа:
"г"-> "."->" "->"Г"
Если есть время посмотреть что найдет Синбад, могу подготовить данные в любом нужном формате.
что там вообще "вылавливать" требуется…
Что вылавливать не понятно, но интересно какие зависимости выловит.
И какой смысл вообще обращать внимание на заведомо линейные случаи? Они ведь и так характеризуются как "идеальные"! А вот если есть вероятность нарваться на квадрат или хотя бы на логарифм…
А именно они и интересны. В случае абсолютно рандомных данных там будет логарифм практически в любом алгоритме (из тех что реально используют), алгоритмы с возможным
квадратом рассматривать особого смысла нет. Т.е. по большому счету остается:
1) насколько оптимально сортируются подпоследовательности (прямые и обратные)
2) насколько большое отклонение от логарифма в случае рандомных данных.
PS Кстати, что такое "слияние списков" в случае "воронки из одного списка", там разве не просто вставка свежепришедшего элемента в нужное место?
Вставка идет либо в head, либо в tail. Если новый элемент создается в интервале head..tail, то текущий (один) список идет в буфер и создается новый.
Когда буфер переполнился — сливаются наименьшие 3/4 буфера. Это просто небольшая оптимизация, в целом в минимальном случае можно просто сливать их как k списков при переполнении, worst case останется таким же.
Чтобы удостовериться, что ваш теоретический анализ коррелирует с реальной производительностью.
Там очень трививальный анализ. Все упирается в мерж k списков, который O(N*log(N)) в худшем случаев. Мерж по размеру немного оптимизирует ситуацию когда списки разной длинны. Реальная производительность сильно зависит от реализации и ничего не говорит о самом алгоритме.
А то почему-то, хотя теоретически merge sort быстрее quick sort, на деле второй (или его вариации) встречаются чаще. Почему?
Обычный квик сорт (который с O(N^2) для worst-case) вроде никто особо не использует. Используют различные его модификации, тот же pdqsort, который довольно сильно отличается от "дефолтного" quick sort. Дальше уже вопрос сложности самого алгоритма с модификациями. Чем сложнее алгоритм, тем проще в нем допустить ошибку (что уже случалось, с тем же timsort). И соответственно возможные векторы атаки на это все.
… если бы дело было только в числе сравнений, скорость linked list не имела бы никакого значения, правда же?
Любой алгоритм сортировки зависит от скорости структуры в которой хранятся данные. Просто тот LL который есть в stdlib раста медленнный, а вектор быстрый.
Концептуально я не вижу причин почему оно должно быть медленее.
В первую очередь, неплохо бы определиться, о какой модели памяти мы говорим.
Причем тут вообще модель памяти? И как это связанно с сортировкой? Если Вы про внешнюю сортировку, то там в любом случае будет тот же самый мерж k списков.
Его можно немного оптимизировать, но worst case не изменится, к самому алгоритму это не имеет отношения.
Ну то есть в нулевую неплохо бы получить формальное описание алгоритма, но после этого важно понимать, чего нам стоят операции с памятью.
Ну, вот чуть выше по треду описание алгоритма в один список, автор подтвердил что оно именно так:
Работаем с одним списком {head, tail}. Если новый элемент больше tail, то добавляем в tail, если меньше head, то добавляем в head.
Если новый элемент: tail > elm > head (т.е. внутри интервала), то создаем новый список, старый кладем в буффер.
Новый элемент сравниваем только с текущим списком, но никогда не с списками из буфера.
В буфере уже не сохраняется отношение что новый список меньше предыдущего.
Что ощутимо проще чем большинство адаптивных алгоритмов.
И немедленно возникает вопрос: если это "та же самая оптимизация" того же самого merge sort, откуда такая разница в производительности?
Это уже детали реализации, и лично мне не особо интересно. Там слишком много вариантов как сделать в 2-4 раза быстрее/медленее на чтении, плюс банальное использование avx2 в компараторе даст примерно x4.
Это, скажем так, неоднозначное утверждение. Как вы это меряете?
Зачем там что-то мерять? Чтобы оценить количество сравнений достаточно посмотреть на сам алгоритм.
Там ровно 4 случая которые на что-то влияют (остальное их комбинация), для воронки из одного списка это будет:
Сужающаяся воронка (worst case) (5, 10, 4, 9, 3, 8):
тут будет просто слияние N/2 списков, это в худшем случае O(Nlog(N/2))
плюс 1.5N сравнений на вставку, получается O(N(1.5+log(N/2))), что довольно близко к merge sort.
Бенчмарки возможно потом выложу, как разберусь со скоростью LL.
В соседнем посте достаточно тривиальная (ну, после знакомства с timsort) оптимизация merge sort оказалась в где-то полтора раза быстрее.
Я говорил про "дефолтный" merge sort и quick sort. Да, можно оптимизировать любой другой алгоритм для каких-то конкретных случаев.
Собственно, воронка и есть простая оптимизация merge sort, причем по большому счету именно та "тривиальная", реализация чуть другая, но суть абсолютно та же самая.
Это не есть "представление строк" — это как раз тезаурус или что-то в этом духе. Подобная структура достаточно просто может быть реализована в Синдбаде, но кому она нужна?
Было бы интересно посмотреть, какие зависимости вылавливает Синбад в данном случае. Понятно, что в большинстве случае хранить строки в виде графа
довольно дорого, и кроме разве что целей NLP имеет мало смысла.
Да, воронку в один список трудно назвать воронкой, но так получилось, что я сначала придумал именно воронку, в несколько списков, и лишь потом упростил это дело до одного. Кстати, я до сих пор не уверен, что воронка в один список эффективнее динамической настройки размера воронки в зависимости от того, как организованы данные входного потока, но мне просто лень это дело исследовать — то, что есть, работает практически ИДЕАЛЬНО! :)
Теоретически воронка даже в один список выглядит действительно очень красиво. Попробовал протестировать по сравнению с другими алгоритмами, понятное дело что она быстрее quick/merge sort (хотя на полностью рандомных данных merge дает меньше сравнений), но если смотреть на новые алгоритмы, то pdqsort лучше работает в случае если одна или несколько последовательностей отсортированны в обратном порядке (там N, у воронки 2N).
Плюс, воронка сильно упирается в скорость работы LL, на простых реализациях это сильно заметно, не уверен что получится сделать реализацию работающую быстрее чем pdqsort, но попробую.
Тогда это парсер. Разбивка строк на отдельные поля (например, на слова). Всё зависит от статистики. Иерархическая зависимость ловится, но я уже и не помню как. В общем, это называется "анализ каналов". Межгрупповые каналы образуют воронку (не ту, которая в сортире, разумеется, а свою), а из неё выделяются "гребёнки" и "иерархии".
В общем случае это парсер, но мне интересно насколько оно будет эффективно именно для графов (если представить строки как нарпавленные графы: ["у"->"л"->"."->" "->"Л"->"е"->"с"->"н"->"а"->"я"])
Не вижу смысла. Воронка и так работает с изумительной скоростью, и ей всё равно, кодируется ли ё одним байтом или двумя — там вообще может быть и то, и другое одновременно. У меня бывали случаи, когда смешивались в одной базе кодировки WIN, DOS и KOI. А в той же OSM описания более, чем на 50 языках, и тоже одновременно для одного и того же объекта!
Если цель сортировки структуризация и нормализация (т.е. дальше результат обрабатывается программой), то смысла действительно нет, а вот если с результатом сортировки будет работать человек, то он явно захочет чтобы "ё" шло после "е", даже если записано двумя байтами).
Разве что если в воронке несколько списков, но лично я это дело уже отменил.
Так проще/быстрее, но в результате получается уже не совсем "воронка".
Понятия не имею! Мы же только макет могли склепать. Сколько миллиардов вбухано в тот же Оракл? А ведь здесь не какаяы-то сраная реляция — здесь НАМНОГО сложнее!
Жаль. Кстати, количество миллиардов обычно слабо связанно со сложностью концепции, даже со сложностью кода оно не сильно связанно.
Не понял: структуризация адресов, записанных строками? Или это всё-таки реляция?
В идеале именно строк, интересно отловит ли оно "ул. " как метаданные будет ли "ул. " и "бул. " общим префиксом для улиц, а так же удастся ли поймать иерархическую зависимость между городом и улицей (понятно что в разных городах есть одинаковые улицы, но большая часть скорее всего будет разной).
Ха-ха-ха! У меня с точностью о наоборот: сортировка используется для нормализации! Точнее, для структуризации и верификации.
Я про нормализацию данных до сортировки, которая происходит в функции компаратора. Например буква "ё" может быть записана на одним байтом, так и двумя. С не компоративными алгоритмами сортировки можно даже сделать меньше O(N) в некоторых случаях и делать проверку уникательности внутри самой сортировки.
Нет, best case — это уже отсортированный массив. Здесь получается полтора сравнения на элемент.
Да, прошу прощения, пропустил.
Хотя есть нюанс: мы же потом сливаем эти списки. Так хвосты в начале будут заметно больше хвостов последних списков потока, а потому при слиянии начинает играть какую-то роль просто пришлёпывания большего хвоста без сравнений. Хотя это тоже копеки, и как-то влияет разве что на эти дурацкие "циферки".
Вот кстати, именно мерж списков самая сложная и интересная часть алгоритма. Если просто по количеству элементов от большего к меньшему, то оно должно быть быстро, но мне почему-то кажется, что может быть еще более простой и красивый вариант, именно для N списков "воронкой", вообще не думая о количестве элементов в них.
Рандом, сортировка прямая и обраотная, да часто повторяющиеся элементы.
Ну, это самые простые тесты позволяющие проверить что "ловля" подпоследовательностей работает.
Да какие там "два раза"! По сравнению с чтением и записью это вообще копейки! Зачем оптимизировать, если сложность уже и так линейная?
Чтение/запись сильно зависит от диска. Например, если мы линейно читаем файл с NVMe, то уже поиск "\n" простым алгоритмом будет тормозить, нужно использовать векторные инструкции.
Чего он делает?! :)
А разве нет? Он ищет подпоследовательности в данных.
Да нафига Вам стеки? Как Вы с ними работать-то будете? Стек ведь это LIFO, а нам нужен ПРОИЗВОЛЬНЫЙ порядок выбора списков для слияния!
Со стеком будет чуть сложнее, один из них должен быть не совсем стеком (хотя не уверен что это обязательно). А произвольный порядок сохранится, достаточно выбирать из массива не по "id", а по "id % 2"
Нет, это У ВАС DLL, а У НАС ничего такого нет. :)
Да, был не прав. В данном случае нужен только один указатель. Немного смутило наличие head/tail.
А ЗАЧЕМ? Зачем анализировать эту фигню? Переполнится буфер списков — и точно так же смержите, без этих проверок.
Это был пример "когда оптимизация имеет мало смысла".
Ну и получите одно сравнение на восходящей и два на нисходящей (или наоборот, как сравнивать начинаете). В срежднем и будет те самые полтора.
Но можно за одно в обоих случаях. Я не настаиваю на этой оптимизации, это было про "И как же кто-то умудрился получить по N-1 для обоих случаев".
Да, будет чуть сложнее. Да, в общем случае скорее всего нет смысла об этом думать. Но можно.
Расходящаяся как раз полтора, и никаких вставок у меня нет ВААПЩЕ.
Ошибся. Будет так:
Ваш вариант:
Восходящая: N
Нисходящая: 2N
Расходящаяся: 1-2N
Сужающаяся: N*log(N), т.к. нужно найти место в списке куда вставить новый элемент.
С оптимизацией:
Восходящая: N
Нисходящая: N
Расходящаяся: 2N
Сужающаяся: N*log(N)
Т.е. оптимизировался "более интересный" случай в два раза, причем за счет лишнего указателя и при этом менее интересный случай изменился в среднем от 1.5 до 2, что еще лучше.
никаких вставок у меня нет ВААПЩЕ
Вот уж до лампады! :)
А вот на гифке на Вашем сайте они есть. Например, есть такая воронка:
0: 1 2 3 4 5
1: 2 3 4
2. 3
Для вставки в нее "4", мы сравниваем "4" с "1", потом с "5" (первый уровень), потом с "2", потом с "4" (второй уровень) и вставляем.
Выглядит как что-то похожее на "бинарный поиск" и на вид как раз log(N).
Они теоретически стоят. Как и "накладные расходы". :)
Теоретически в компаративных алгоритмах сравнивается исключительно сложность в количестве сравнений элементов, а количество сравнений именно элементов не добавляется. Да, в случае если элемент это u32, то вся работа с указателями будет равноценна сравнению элементов, но это уже детали реализации.
Это да. Но ведь тот чувак привёл цифири, якобы своих "счётчиков"! То есть "соврамши".
Я вообще не смотрел его реализацию, я про "кто-то умудрился получить по N-1". Можно сделать N для обоих случаев.
Это ВАШИ проблемы! Мне нужен был эффективный алгоритм сортировки, и я его получил.
Да нет никаких проблем, я просто указал на дополнительную возможность применения алгоритма.
Один список воронки. Или воронка, состоящая из одного списка.
А вот это интересно. На сколько я понял из статьи, там все равно есть буфер:
Работаем с одним списком {head, tail}. Если новый элемент больше tail, то добавляем в tail, если меньше head, то добавляем в head.
Если новый элемент: tail > elm > head (т.е. внутри интервала), то создаем новый список, старый кладем в буффер.
Новый элемент сравниваем только с текущим списком, но никогда не с списками из буфера.
В буфере уже не сохраняется отношение что новый список меньше предыдущего?
Как-то так?
Вот как там статистика отловила кандидатов в метаданные:
Хм, т.е. в данном случае в метаданных группа полей будет считаться одним значением поля?
воронка размером даже в один список ГАРАНТИРОВАННО поймает любую восходящую или нисходящую подпоследовательность
Вот кстати, тут речь идет про один DLL? Или про один список воронок?
Потому что в одном DLL у нас будет: (1, 2, 3, 4, 5, 6, 7, 8, 9).
Если прилетает "4", то нужно в худшем случае пройти весь список.
Можно конечно хранить список как:
struct {head, tail, head_first, tail_first, head_cnt, tail_cnt} и на основе этого немного сократить обход, но это по большому счету будет та же воронка, только более медленная.
Ну, обычно при вставке данных из внешних источников их приходится так или иначе чистить руками, тут как я понимаю, просто более универсальный подход. А насколько хорошо оно работает именно без пользователя и именно в плане "структуризация для максимально быстрого выполнения запросов"?
всё равно собирала практически то же самое, хоть и разными путями.
А есть какие-то примеры того что получается, например на тех же адресах вида "г. Город, <индекс>, бул. Улица, д. 99ек99, кв. 50", если они записаны в произвольном порядке пользователем (с соответствующими ошибками)?
Так что за "оптимизация"?
Хм, возможно я что-то упускаю, прошу поправить.
Как я вижу сортировку в общем виде:
Мы не можем делать ее меньше чем за O(n*log(n)) в общем случае для компаративных алгоритмов (с другой стороны, очень часто можно нормализовать данные, так чтобы перейти от сравнения неизвестной структуры к сравнению N битных чисел).
В реальных данных очень часто встречаются уже отсортированные подпоследовательности, структуру которых мы можем использовать для сортировки за O(n)-O(n*log(n)).
Варианты подпоследовательностей:
Восходящие (1, 2, 3, ...)
Нисходящие (9, 8, 7, ...)
Расходящаяся воронка: (3, 8, 4, 9, 5, 10, ...), best case для воронки
Сужающаяся воронка: (5, 10, 4, 9, 3, 8), worst case для воронки
В реальных последовательностях встречаются восходящие и нисходящие типы, и именно их мы хотим отловить, для ускорение общего случая.
Расширяющаяся и сужающаяся воронка редко встречаются в реальных данных и нужны в первую очередь для оценки алгоритма сортировки воронкой, т.к. сильно на нее влияют (в отличии от других алгоритмов).
и какая разница за одно или за два сравнения?
В целом с точки зрения оценки алгоритма практически никакого, в реальности может быть в два раза быстрее, если много данных отсортированных в обратном порядке.
Во-вторых что-то там запоминать и что-то анализировать — это те же сравнения, только не затрагивающие счётчики
Ну, алгоритм воронки уже запоминает структуру данных и "анализирует" ее для оптимизиации общего случая, т.к. запоминает подпоследовательности.
В целом, если мы говорим о сортировке строк и сортировке "данных однородной структуры" (в контексте бд), то важно именно количество сравнений строк, а сравнением всяких счетчиков можно пренебречь. К тому же, не обязательно сравнивать счетчики. Мы запоминаем указатель на стек в который последний раз вставляли элементы и идем в него. Если не попали в этот стек, то идем левее/правее, в зависимости от результата сравнения.
Работа с указателями все равно так или иначе будет, поскольку у нас DLL (double linked list).
Вот например, для расходящейся воронки можно сделать оптимизацию с счетчиками и если первый список состоит из двух элементов, то после того как следующий список заполнен, мы их мержим (9, 1, 8, 2) -> ((9, 8), (1, 2)), это действительно оптимизация с лишними сравнениями и мы просто делаем worst case сложнее (отсекая малую часть вариантов), но т.к. в реальных данных наличие подпоследовательностей отсортированных воронкой маловероятно, то и смысла в этом довольно мало.
Вместо полутора сравнений в среднем на пристройку элемента, получите двойку.
А в среднем ли? Я предполагаю что "восходящие" и "нисходящие" последовательности встречаются в реальных данных намного чаще, чем "расходящиеся" и "сходящиеся" воронки.
В Вашем алгоритме:
Восходящая: N
Нисходящая: 2N
Расходящаяся: N
Сужающаяся: N*log(N), т.к. нужно найти место в списке куда вставить новый элемент.
Насколько я помню, log(N) это как раз worst case для вставки в отсортированный список.
С этой "оптимизацией:
Восходящая: N
Нисходящая N
Расходящаяся: 2N
Сужающаяся: N*log(N)
Т.е. тут в два раза оптимизируется интересный случай (нисходящая последовательность), за счет редкого и не интересного.
не говоря уже о том, что все эти проверки чего-то стоят.
Они практически ничего не стоят, соизмеримо с накладными расходами на DLL.
В-третьих, если попадётся расходящаяся воронка (1, -1, 2, -2, ...), то какой толк от этого запоминания?
Никакого. Но мы говорим об оптимизации merge sort под восходящие и нисходящие последовательности? То что
расходящаяся воронка это best case, это же не значит что она важна и все оптимизации направлены именно на нее?
Кстати, ДАЖЕ ТАКОЕ изменение (язык не поворачивается сказать "улучшение") не даст N-1 как на прямой, так и на обратной последовательности.
Даст N-1 на прямой и N на обратной последовательности, что можно округлить оба случая до N, т.к. в случаях когда одно сравнение имеет хоть какое-то значение, сортировка пузырьком будет быстрее.
Господи, спаси и сохрани! :) Здесь тупо идёт поток входных данных и размазывается по спискам воронки. Проще просто НЕ БЫВАЕТ!
Дак и со стеками просто. И памяти меньше (хотя если сортировать строки, это смешно):
Список (DLL) это (head, tail, ptr).
Стек (LL) это (prev, ptr)
Получается x2 вместо x3 сопутствующих данных. Если оптимизировать в том числе под нисходящую последовательность, то будет еще один ptr, один раз для всех списков.
Кстати, воронка очень похожа на skip list, только в обе стороны (что дает плюсы по производительности), мне кажется что ее нужно рассматривать как структуру данных, а не алгоритм сортировки. По идее в ней удобно хранить всякие отсортированные данные с быстрой вставкой.
Вот, я когда-то делал доклад в Греции. Ни одна собака после доклада ни одного вопроса так и не задала. Но когда я вышел в фойе, подошли два японца: "А как ты данные от метаданных отличаешь"? И после моего "вери симпл" и пары рисунков на листочке: "вот этот узел — данные, этот -= метаданные" у них были совершенно квадратные глаза. :)
Это же про: "If this value exceeded a threshold of the statistical importance, the node was considered as metadata, and it receives an arc to node METADATA (9 nodes altogether)."?
Там на сколько я понимаю довольно много "магических констант", типа "1% от базы для метаданных" и всякие разделители?
О! Это круто! И как же кто-то умудрился получить по N-1 для обоих случаев
Прошу прощение, что влезаю, но там возможна простая оптимизация для некоторых случаев:
Если проверять сначала head первого списка, потом tail, потом head второго списка и т.д.,
то мы оптимизируем алгоритм для случая когда данные идут примерно так: [1,9,2,8,3,7,...], что
менее вероятно чем то что данные будут идти как [1,2,3,9,8,7,...]
Тогда можно после вставки элемента запоминать куда именно мы его вставили, и тогда последующие
элементы той же восходящей или нисходящей отсортированной последовательности будут очень быстро
вставлятся, без лишних сравнений.
Чтобы было проще хранить эту позицию, можно представить эту группу linked list'ов как
массив стеков [head1, tail1, head2, tail2, ...], тогда просто запоминаем индекс последнего стека.
Ну, забросьте куда-нибудь, да киньте ссылку в личку. Желательно не более 50 гигов в развёрнутом виде — я пока не знаю, сколько я ещй здесь пробуду.
Пока из того что смотрел, не нашел того что мог бы скинуть.
Не, не, не — алгоритмы структуризации я как-то представляю (да и инструментарий у меня именно под них). Да и информация извлекается, в основном, из самой базы, а не из представлений о ней юзеров или разработчиков. :)
Вот я как раз про них и хотел узнать, если это не сильно далеко от темы заметки?
А там не остаются метаданные разве?
Ну, в контексте именно бд, интересует какую более эффективную структуру и метаданные сможет выделить бд самостоятельно, чтобы сравнивать с тем что может выделить из тех же данных человек.
Было бы интересно посмотреть на примерный формат хранения метаданных кстати, есть что-то такое, что можно показать?
Ну, т.е. LL остается, просто лежит внутри самого элемента? Там кстати будет дополнительное копирование, потому что из OS прилетают не строки, а просто буфер байтов. В контексте тех же юникодных строк это особо не важно, т.к. их все равно желательно нормализовать. Да и в случае сортировки наличие данных внутри LL очень хорошо отразится на производительности (потому что часть данных уже будет в кеше после перехода по указателю).
Для оценки алгоритма достаточно.
Здравый смысл? У сортировки есть две операции:
1) чтение данных. нет смысла читать без сравнения.
2) запись/swap. нельзя заменить один элемент на другой без сравнения, если не говорить о bogosort и подобных алгоритмах.
И как это противоречит?
Это уже не асимптотика. Эти вещи имеют довольно мало смысла вне контекста реализации. А в случае реализации там уже появляется кэш CPU, branch prediction,
и прочие штуки, которые очень сложно внятно оценть.
Если не достаточно, то нужно оценивать конкретные реализации.
Он медленее на некоторых реальных кейсах, которые воронка как раз улучшает. Общий случай у merge sort сильно лучше, чем у quick sort.
Там тоже константа, если приходит LL вместо массива. Только в реальности, в большинстве случаев сортируют не массив, а вектор.
Который потратит кучу времени на копирование при добавлении новых элементов, плюс будет хранить большой пустой кусок, чтобы
не копировать все данные на каждой вставке.
Тем что она сильно проще, имеет поддержку LL, при этом достаточно быстрая.
Тот же timsort на порядок сложнее, и там даже находили баги.
Ну вот воронка делает тоже самое, только не теряет в скорости, и субъективно еще проще.
Если говорить про базовые реализации merge/quick, то у воронки константы в оптимизированных случаях лучше, в случае рандомных данных не намного хуже чем у merge. У quick там вообще квадрат, что делает бессмысленным его использование в большинстве вещей, даже без констант.
Я про создание LL из массива/вектора и говорю. Если будет LL, то там константное использование места, BUF_SIZE(1024)3ptr (head, tail, len).
Если мне нужен LL я точно так же потрачу N времени на копирование из массива в LL. Только в реальности вместо массива обычно вектор, и далеко не всегда известно количество элементов (как в той же сортировке строк), более того, данные могут быть еще и разной длины, а соотвественно на этапе вставки мы будем копировать весь вектор при расширении его размера.
Где он используется? Тот же timsort это разновидность merge sort, в других адаптивных алгоритмах (тот же pdqsort) квик сорт в худшем случае заменяется на heapsort, чтобы успеть за O(n*log(N)).
Результат структуризации же.
Возможно и пробел, да. Но есть шанс что окончания у одинаковых лемм будут выделенны в один класс. Поэтому и было интересно посмотреть.
Ну, нюансы в основном в merge самих списков, быстро прикреплять хвосты и все прочее. Плюс, в самом начале можно без изменений часть головы пропустить.
Что-то еще?
Там лишние копирования указателей на строку, остальные алгоритмы тоже при сортировке используют просто вектор указателей на строки, не копировать же их.
А как без LL? Можно конечно менять местами указатели в массиве, но там уже сильно усложняется сам алгоритм.
А можно посмотреть результат (на том же OSM) в виде графа? (например пачка html страниц, как в случае с транспортов).
Ну, как минимум должны появится различные зависимости от структуры языка (всякие окончания и прочее).
Неа, к самому алгоритму вопросов особо нет. Счетчики по количеству сравнений хорошие (в минимальной имплементации правда pdqsort быстрее именно на обратных последовательностях).
Да и пишется он за 10 минут, рисование табличек сильно сложнее.
Проблема в том что тот linked list который есть в языке, он во первых DLL, а во вторых аллоцируется по элементам, а не пачкой. Плюс там судя по всему много копирований.
Вот, хотелось бы увидеть граф после реструктуризации, если слова разбить на буквы (если не сложно),
мне кажется там много довольно интересных зависимостей, ну будет видно как работает реструктуризация.
Я в целом делаю бенчмарк этого всего, потому и сравниваю с pdqsort. Как разберусь со скоростью LL выложу.
Для практических задач разницы особой нет. Проблема в том что pdqsort готовый, а воронку нужно писать, что я собственно и делаю.
Это если с чтением/записью. Но их тоже можно сильно оптимизировать, тогда уже начнет влиять логарифм.
я не вижу там особо больших констант в общем случае (в сравнении с merge/quick), но это уже больше детали реализации.
размер указателя*N. если критично можно меньше.
их нет
на выходе обычный итератор в виде списка. можно преобразовать в вектор/массив. но это все детали реализации.
Ну, я вроде довольно подробно расписал как считал асимптотику. Если есть какие-то конкретные вопросы, готов на них ответить.
Сравнений. Компаративные алгоритмы сортировки оцениваются именно по ним.
Оценки это N vs N * log(N) vs N^2. "в полтора раза" это константа, которая зависит от реализации.
Для алгоритма вполне можно. Для реализации нельзя.
Медленее pdqsort.
Алгоритмическая сложность компаративной сортировки расчитывается по количеству операций сравнения. Тут вопросов к воронке лично у меня нет.
И? В любом алгоритме сортировке внешняя сортировка это так или иначе слияние k отсортированных списков, других вариантов особо нет.
Алгоритм потребляет размер_указателя*N бит дополнительной памяти. Для всех применений, кроме сортировки массива интов это нормально.
От каких существующих алгоритмов? От quick sort/merge sort отличие очевидно в количестве операций сравнения.
От pdqsort отличие в простоте реализации, что потенциально может быть сильно быстрее.
Буфер это список/вектор/массив, в который добавляются LL, когда нужен новый. У него ограничение в 1024 элемента. Когда достигли ограничения в 1024 элемента, этот массив сортируется по количеству элементов в каждом списке, дальше списки сливаются начиная с самого меньшего, по 2 за раз. В целом просто вариация стандартного "k-way merge".
На всякий случай процитирую вики, вдруг так проще будет:
Список адресов вида "г. Город, ул. Улица, ..." (например из OSM) представленные в виде направленного графа:
"г"-> "."->" "->"Г"
Если есть время посмотреть что найдет Синбад, могу подготовить данные в любом нужном формате.
Что вылавливать не понятно, но интересно какие зависимости выловит.
Pattern-defeating quicksort . Вариация quicksort с асимптотикой близкой к воронке (но сильно сложнее).
А именно они и интересны. В случае абсолютно рандомных данных там будет логарифм практически в любом алгоритме (из тех что реально используют), алгоритмы с возможным
квадратом рассматривать особого смысла нет. Т.е. по большому счету остается:
1) насколько оптимально сортируются подпоследовательности (прямые и обратные)
2) насколько большое отклонение от логарифма в случае рандомных данных.
Вставка идет либо в head, либо в tail. Если новый элемент создается в интервале head..tail, то текущий (один) список идет в буфер и создается новый.
Когда буфер переполнился — сливаются наименьшие 3/4 буфера. Это просто небольшая оптимизация, в целом в минимальном случае можно просто сливать их как k списков при переполнении, worst case останется таким же.
Там очень трививальный анализ. Все упирается в мерж k списков, который O(N*log(N)) в худшем случаев. Мерж по размеру немного оптимизирует ситуацию когда списки разной длинны. Реальная производительность сильно зависит от реализации и ничего не говорит о самом алгоритме.
Обычный квик сорт (который с O(N^2) для worst-case) вроде никто особо не использует. Используют различные его модификации, тот же pdqsort, который довольно сильно отличается от "дефолтного" quick sort. Дальше уже вопрос сложности самого алгоритма с модификациями. Чем сложнее алгоритм, тем проще в нем допустить ошибку (что уже случалось, с тем же timsort). И соответственно возможные векторы атаки на это все.
Любой алгоритм сортировки зависит от скорости структуры в которой хранятся данные. Просто тот LL который есть в stdlib раста медленнный, а вектор быстрый.
Концептуально я не вижу причин почему оно должно быть медленее.
Причем тут вообще модель памяти? И как это связанно с сортировкой? Если Вы про внешнюю сортировку, то там в любом случае будет тот же самый мерж k списков.
Его можно немного оптимизировать, но worst case не изменится, к самому алгоритму это не имеет отношения.
Ну, вот чуть выше по треду описание алгоритма в один список, автор подтвердил что оно именно так:
Что ощутимо проще чем большинство адаптивных алгоритмов.
Это уже детали реализации, и лично мне не особо интересно. Там слишком много вариантов как сделать в 2-4 раза быстрее/медленее на чтении, плюс банальное использование avx2 в компараторе даст примерно x4.
Зачем там что-то мерять? Чтобы оценить количество сравнений достаточно посмотреть на сам алгоритм.
Там ровно 4 случая которые на что-то влияют (остальное их комбинация), для воронки из одного списка это будет:
тут будет просто слияние N/2 списков, это в худшем случае O(Nlog(N/2))
плюс 1.5N сравнений на вставку, получается O(N(1.5+log(N/2))), что довольно близко к merge sort.
Бенчмарки возможно потом выложу, как разберусь со скоростью LL.
Я говорил про "дефолтный" merge sort и quick sort. Да, можно оптимизировать любой другой алгоритм для каких-то конкретных случаев.
Собственно, воронка и есть простая оптимизация merge sort, причем по большому счету именно та "тривиальная", реализация чуть другая, но суть абсолютно та же самая.
Было бы интересно посмотреть, какие зависимости вылавливает Синбад в данном случае. Понятно, что в большинстве случае хранить строки в виде графа
довольно дорого, и кроме разве что целей NLP имеет мало смысла.
Теоретически воронка даже в один список выглядит действительно очень красиво. Попробовал протестировать по сравнению с другими алгоритмами, понятное дело что она быстрее quick/merge sort (хотя на полностью рандомных данных merge дает меньше сравнений), но если смотреть на новые алгоритмы, то pdqsort лучше работает в случае если одна или несколько последовательностей отсортированны в обратном порядке (там N, у воронки 2N).
Плюс, воронка сильно упирается в скорость работы LL, на простых реализациях это сильно заметно, не уверен что получится сделать реализацию работающую быстрее чем pdqsort, но попробую.
В общем случае это парсер, но мне интересно насколько оно будет эффективно именно для графов (если представить строки как нарпавленные графы: ["у"->"л"->"."->" "->"Л"->"е"->"с"->"н"->"а"->"я"])
Если цель сортировки структуризация и нормализация (т.е. дальше результат обрабатывается программой), то смысла действительно нет, а вот если с результатом сортировки будет работать человек, то он явно захочет чтобы "ё" шло после "е", даже если записано двумя байтами).
Так проще/быстрее, но в результате получается уже не совсем "воронка".
Жаль. Кстати, количество миллиардов обычно слабо связанно со сложностью концепции, даже со сложностью кода оно не сильно связанно.
В идеале именно строк, интересно отловит ли оно "ул. " как метаданные будет ли "ул. " и "бул. " общим префиксом для улиц, а так же удастся ли поймать иерархическую зависимость между городом и улицей (понятно что в разных городах есть одинаковые улицы, но большая часть скорее всего будет разной).
Я про нормализацию данных до сортировки, которая происходит в функции компаратора. Например буква "ё" может быть записана на одним байтом, так и двумя. С не компоративными алгоритмами сортировки можно даже сделать меньше O(N) в некоторых случаях и делать проверку уникательности внутри самой сортировки.
Да, прошу прощения, пропустил.
Вот кстати, именно мерж списков самая сложная и интересная часть алгоритма. Если просто по количеству элементов от большего к меньшему, то оно должно быть быстро, но мне почему-то кажется, что может быть еще более простой и красивый вариант, именно для N списков "воронкой", вообще не думая о количестве элементов в них.
Ну, это самые простые тесты позволяющие проверить что "ловля" подпоследовательностей работает.
Чтение/запись сильно зависит от диска. Например, если мы линейно читаем файл с NVMe, то уже поиск "\n" простым алгоритмом будет тормозить, нужно использовать векторные инструкции.
А разве нет? Он ищет подпоследовательности в данных.
Со стеком будет чуть сложнее, один из них должен быть не совсем стеком (хотя не уверен что это обязательно). А произвольный порядок сохранится, достаточно выбирать из массива не по "id", а по "id % 2"
Да, был не прав. В данном случае нужен только один указатель. Немного смутило наличие head/tail.
Это был пример "когда оптимизация имеет мало смысла".
Но можно за одно в обоих случаях. Я не настаиваю на этой оптимизации, это было про "И как же кто-то умудрился получить по N-1 для обоих случаев".
Да, будет чуть сложнее. Да, в общем случае скорее всего нет смысла об этом думать. Но можно.
Ошибся. Будет так:
Восходящая: N
Нисходящая: 2N
Расходящаяся: 1-2N
Сужающаяся: N*log(N), т.к. нужно найти место в списке куда вставить новый элемент.
Восходящая: N
Нисходящая: N
Расходящаяся: 2N
Сужающаяся: N*log(N)
А вот на гифке на Вашем сайте они есть. Например, есть такая воронка:
Для вставки в нее "4", мы сравниваем "4" с "1", потом с "5" (первый уровень), потом с "2", потом с "4" (второй уровень) и вставляем.
Выглядит как что-то похожее на "бинарный поиск" и на вид как раз log(N).
Теоретически в компаративных алгоритмах сравнивается исключительно сложность в количестве сравнений элементов, а количество сравнений именно элементов не добавляется. Да, в случае если элемент это u32, то вся работа с указателями будет равноценна сравнению элементов, но это уже детали реализации.
Я вообще не смотрел его реализацию, я про "кто-то умудрился получить по N-1". Можно сделать N для обоих случаев.
Да нет никаких проблем, я просто указал на дополнительную возможность применения алгоритма.
А вот это интересно. На сколько я понял из статьи, там все равно есть буфер:
Как-то так?
Хм, т.е. в данном случае в метаданных группа полей будет считаться одним значением поля?
Вот кстати, тут речь идет про один DLL? Или про один список воронок?
Потому что в одном DLL у нас будет: (1, 2, 3, 4, 5, 6, 7, 8, 9).
Если прилетает "4", то нужно в худшем случае пройти весь список.
Можно конечно хранить список как:
struct {head, tail, head_first, tail_first, head_cnt, tail_cnt} и на основе этого немного сократить обход, но это по большому счету будет та же воронка, только более медленная.
Ну, обычно при вставке данных из внешних источников их приходится так или иначе чистить руками, тут как я понимаю, просто более универсальный подход. А насколько хорошо оно работает именно без пользователя и именно в плане "структуризация для максимально быстрого выполнения запросов"?
А есть какие-то примеры того что получается, например на тех же адресах вида "г. Город, <индекс>, бул. Улица, д. 99ек99, кв. 50", если они записаны в произвольном порядке пользователем (с соответствующими ошибками)?
Хм, возможно я что-то упускаю, прошу поправить.
Как я вижу сортировку в общем виде:
В целом с точки зрения оценки алгоритма практически никакого, в реальности может быть в два раза быстрее, если много данных отсортированных в обратном порядке.
Ну, алгоритм воронки уже запоминает структуру данных и "анализирует" ее для оптимизиации общего случая, т.к. запоминает подпоследовательности.
В целом, если мы говорим о сортировке строк и сортировке "данных однородной структуры" (в контексте бд), то важно именно количество сравнений строк, а сравнением всяких счетчиков можно пренебречь. К тому же, не обязательно сравнивать счетчики. Мы запоминаем указатель на стек в который последний раз вставляли элементы и идем в него. Если не попали в этот стек, то идем левее/правее, в зависимости от результата сравнения.
Работа с указателями все равно так или иначе будет, поскольку у нас DLL (double linked list).
Вот например, для расходящейся воронки можно сделать оптимизацию с счетчиками и если первый список состоит из двух элементов, то после того как следующий список заполнен, мы их мержим (9, 1, 8, 2) -> ((9, 8), (1, 2)), это действительно оптимизация с лишними сравнениями и мы просто делаем worst case сложнее (отсекая малую часть вариантов), но т.к. в реальных данных наличие подпоследовательностей отсортированных воронкой маловероятно, то и смысла в этом довольно мало.
А в среднем ли? Я предполагаю что "восходящие" и "нисходящие" последовательности встречаются в реальных данных намного чаще, чем "расходящиеся" и "сходящиеся" воронки.
В Вашем алгоритме:
Насколько я помню, log(N) это как раз worst case для вставки в отсортированный список.
С этой "оптимизацией:
Т.е. тут в два раза оптимизируется интересный случай (нисходящая последовательность), за счет редкого и не интересного.
Они практически ничего не стоят, соизмеримо с накладными расходами на DLL.
Никакого. Но мы говорим об оптимизации merge sort под восходящие и нисходящие последовательности? То что
расходящаяся воронка это best case, это же не значит что она важна и все оптимизации направлены именно на нее?
Даст N-1 на прямой и N на обратной последовательности, что можно округлить оба случая до N, т.к. в случаях когда одно сравнение имеет хоть какое-то значение, сортировка пузырьком будет быстрее.
Дак и со стеками просто. И памяти меньше (хотя если сортировать строки, это смешно):
Получается x2 вместо x3 сопутствующих данных. Если оптимизировать в том числе под нисходящую последовательность, то будет еще один ptr, один раз для всех списков.
Кстати, воронка очень похожа на skip list, только в обе стороны (что дает плюсы по производительности), мне кажется что ее нужно рассматривать как структуру данных, а не алгоритм сортировки. По идее в ней удобно хранить всякие отсортированные данные с быстрой вставкой.
Спасибо, читаю.
Это же про: "If this value exceeded a threshold of the statistical importance, the node was considered as metadata, and it receives an arc to node METADATA (9 nodes altogether)."?
Там на сколько я понимаю довольно много "магических констант", типа "1% от базы для метаданных" и всякие разделители?
Прошу прощение, что влезаю, но там возможна простая оптимизация для некоторых случаев:
то мы оптимизируем алгоритм для случая когда данные идут примерно так: [1,9,2,8,3,7,...], что
менее вероятно чем то что данные будут идти как [1,2,3,9,8,7,...]
элементы той же восходящей или нисходящей отсортированной последовательности будут очень быстро
вставлятся, без лишних сравнений.
массив стеков [head1, tail1, head2, tail2, ...], тогда просто запоминаем индекс последнего стека.
Пока из того что смотрел, не нашел того что мог бы скинуть.
Вот я как раз про них и хотел узнать, если это не сильно далеко от темы заметки?