Алгоритмы ближней сортировки - когда использовать?

Question

Время от времени я просматриваю веб-сайты и ищу интересные алгоритмы и структуры данных, чтобы положить их в мою хитрость. Год назад я наткнулся на структуру данных Soft Heap и узнал о почти сортировке.

Идея, лежащая в основе этого, заключается в том, что можно преодолеть барьер O (n log n) для сортировок на основе сравнения, если вы согласны с тем фактом, что алгоритм сортировки немного обманывает. Вы получаете почти отсортированный список, но вам также придется мириться с некоторыми ошибками.

Я поиграл с алгоритмами в тестовой среде, но так и не нашел их применения.

Итак, вопрос: кто-нибудь когда-либо использовал сортировку на практике? Если да, то в каких приложениях? Можете ли вы придумать вариант использования, в котором правильная сортировка - это правильная сортировка?

Answer 1

Это полная догадка, но, учитывая присущий субъективности критерий "релевантности" при сортировке результатов поиска, я рискну предположить, что на самом деле не имеет значения, правильно ли они отсортированы. То же самое можно сказать и о рекомендациях. Если вы можете как-то договориться, что любая другая часть вашего алгоритма для этих вещей - O (n), тогда вы можете попытаться избежать сортировки.

Имейте в виду также, что в худшем случае ваши "почти отсортированные" данные не встречают одну возможную интуитивную идею "почти отсортированного", заключающуюся в том, что они имеют только небольшое количество инверсий. Причина этого заключается лишь в том, что если ваши данные имеют только O (n) инверсий, то вы можете закончить сортировку за O (n) время, используя сортировку вставкой или коктейльную сортировку (то есть двустороннюю пузырьковую сортировку). Отсюда следует, что вы не можете достичь этой точки из полностью не отсортированного за O (n) времени (используя сравнения). Таким образом, вы ищете приложения, в которых большинство подмножеств данных отсортировано, а остаток разбросан, не для приложений, требующих, чтобы каждый элемент находился близко к своей правильной позиции.

Answer 2

Существует множество «жадных» эвристик, в которых вы периодически выбираете минимум набора. Жадная эвристика не идеальна, поэтому даже если вы выберете минимум, вы не гарантированно получите лучший окончательный ответ. Фактически, метаэвристический GRASP , вы преднамеренно вносите случайную ошибку, чтобы получить несколько окончательных решений и выбрать лучшее. В этом случае внесение некоторой ошибки в процедуру сортировки в обмен на скорость будет хорошим компромиссом.

Answer 3

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

Запрос к базе данных на декларативном языке, таком как SQL, должен быть переведен в пошаговую программу, называемую «план выполнения». Один SQL-запрос обычно можно преобразовать в несколько таких планов выполнения, которые все дают одинаковый результат, но могут иметь очень различную производительность. Оптимизатор запросов должен найти самый быстрый или хотя бы достаточно быстрый.

Оптимизаторы запросов на основе стоимости имеют «функцию стоимости», которую они используют для оценки времени выполнения данного плана. Исчерпывающие оптимизаторы просматривают все возможные планы (для некоторого значения «все возможные») и выбирают самый быстрый. Для сложных запросов количество возможных планов может быть чрезмерно большим, что приводит к чрезмерно долгому времени оптимизации (даже прежде чем вы начнете поиск в базе данных!), Поэтому существуют также неисчерпывающие оптимизаторы. Они только смотрят на некоторые планы, возможно, со случайным элементом в выборе, какие из них. Это работает, так как обычно существует большое количество «хороших» планов, и, возможно, не так важно найти абсолютно лучший план - вероятно, лучше выбрать 5-секундный план вместо оптимального 2-секундного плана. , если для поиска 2-секундного плана требуется несколько минут оптимизации.

Некоторые алгоритмы оптимизации используют отсортированную очередь «многообещающих» (частичных) планов. Если это не имеет значения, если вы найдете абсолютно лучший план, возможно, вы могли бы использовать почти отсортированную очередь?

Другая идея (и я до сих пор только размышляю) - это планировщик для процессов или потоков в системе с разделением времени, где это может не иметь значения, если определенный процесс или поток получает свой временной интервал на несколько миллисекунд позже, чем если бы строго отсортировано по приоритету.

Answer 4

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

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

Answer 5

везде

1. Вы должны реагировать быстро,
2. Вы не обещаете точного поведения клиенту,
3. но внутри вас есть некоторые правила

Вы можете использовать это. Как насчет «не такой строгой» очереди приоритетов на основе правил? Где это будет полезно? Возможно планирование потока / процесса / ресурса. В планировании потоков / процессов вы на самом деле не обещаете, что один поток будет идти первым, вторым или последним, но обычно вы хотите дать всем шанс. Возможно, вы захотите применить свободное правило, чтобы оно было приоритетным, приоритетным, бла бла ..

Примером графика ресурсов может быть реагирование на доставку пиццы или доставку коробок с книгами людям и т. Д. Вы не можете использовать его там, где ожидается детерминированный результат, но в реальной жизни есть много примеров, когда вещи не настолько детерминированы / предсказуемы.

Answer 6

O (n log n) уже довольно быстро. Я не думаю, что кто-то когда-либо начнет , используя алгоритм почти сортировки. Вы начнете с кода, который просто выполняет полную сортировку (поскольку ваш язык программирования, скорее всего, предоставляет функцию sort, а не функцию nearsort), и когда вы эмпирически обнаружили, что сортировка занимает слишком много времени, вы начните задавать вопрос, должны ли ваши данные действительно быть полностью отсортированы, и подумайте об использовании почти сортировки.

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