Алгоритмы сортировки рядом - когда использовать?

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

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

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

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

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

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

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

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

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

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

В любом месте

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

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

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

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

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