Алгоритмы поиска / сортировки, которые жертвуют точностью ради скорости

Question

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

Я думал о нижней границе для сортировки сравнения и думал о том, как получить гигантскийнаборы данных, если сортировка сравнения может просто пропустить некоторые сравнения, угадав, каким будет ответ, тогда целые строки сравнений могут быть пропущены, а высота уменьшена на 1. (например, сортировка a, b, c, d, e, fесли алгоритм мог бы догадаться, что bcd вместе, то вы на самом деле только сортируете a, bcd, e, f) Предположение должно быть умным, эффективным, чтобы оно того стоило, плюс оно должно иметь довольно хорошее соотношение ватина.

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

В любом случае, я уверен, что любой, кто понимает предмет, к настоящему времени поймет, что это в основном спекуляция / фантазия безРеальная сущность, поэтому я прошу помощи в принятии мер в направлении изучения алгоритмов, которые не имеют 100% правильных результатов, особенно в областях поиска / сортировки, но быстрее и в применении этих алгоритмов.

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

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

Answer 1

Я думаю, чтобы многого добиться, вам нужно будет определить некоторые критерии для вашего "почти отсортированного".Если, например, наличие элемента в N точках правильного места было достаточно, вы могли бы сделать что-то вроде быстрой сортировки, но остановиться, когда раздел был до N элементов.Обратите внимание, что это уже распространено, и завершите работу с помощью вставки.Однако, если бы N не было довольно большим, вы, вероятно, не получили бы от этого большого выигрыша.

Что касается поиска, вы, вероятно, ищете то, что обычно называют интерполяционным поиском.Вместо того, чтобы всегда угадывать в середине диапазона, вы используете интерполяцию, чтобы угадать вероятное место для искомого элемента (например, если вы ищете строку, начинающуюся с 'b', вы начинаете с 1/ 13 ^й пути через коллекцию, а не на полпути.

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

Answer 2

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

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

Но почти отсортированные данные могут быть правильно отсортированы очень быстро.Например, сортировка вставки - O (n + d), где n - количество элементов, а d - количество инверсий.

Так что, если вы можете «быстро» почти отсортировать данные, тогда вы можетебыстро + немного "правильно сортируй.Разница между почти сортировкой и правильной сортировкой всегда "немного".

Answer 3

В одном случае я использовал сортировку вставок с максимальным количеством «вставок» на цикл, чтобы приблизительно поддерживать порядок во времени (где гарантирование определенного предела времени вычислений было более важным, чем точность). Но я согласен со Стивом Джессопом: в общем, нет причин дешеветь. И есть такие алгоритмы, как TimSort, которые предназначены для распознавания и использования «простых случаев».