Рядом с алгоритмами сортировки – когда использовать?

Question

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

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

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

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

Answer 1

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

Answer 2

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

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

Answer 3

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

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

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

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

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

Answer 4

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

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

Answer 5

В любом месте

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

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

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

Answer 6

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

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