Какие методы сортировки я могу использовать, когда сравнивать элементы дорого?

Проблема

У меня есть приложение, в котором я хочу отсортировать массив a элементов a ₀, a ₁,..., a _{n-1к югу > . У меня есть функция сравнения cmp (i, j), которая сравнивает элементы a _i и _j и swap-функцию swap (i, j), которая меняет элементы a _i и _j массива. В приложении выполнение функции cmp (i, j) может быть чрезвычайно дорогостоящим до такой степени, когда одно выполнение cmp (i, j) занимает больше времени, чем любые другие шаги в сортировке (кроме других cmp (i, j ) звонит, конечно) вместе. Вы можете думать о cmp (i, j) как о довольно длительной операции ввода-вывода.}

Пожалуйста, примите во внимание этот вопрос, что нет способа быстрее сделать cmp (i, j). Предположим, что все оптимизации, которые могли бы сделать cmp (i, j) быстрее уже выполненными.

Вопросы

Есть ли алгоритм сортировки, который минимизирует количество вызовов cmp (i, j)?
В моем приложении возможно написать предикат дорогой (i, j), который является истинным, если вызов cmp (i, j) займет много времени. дорогой (i, j) дешево и дорого (i, j) &; дорогой (j, k) → дорогой (i, k) в основном выполняется в моем текущем приложении. Однако это не гарантируется.

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

Пример

Это пример, который не совсем не похож на приложение, которое у меня есть.

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

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

Реализация дорогостоящего (i, j) в этом случае - это просто проверка того, равны ли хеши. Если это так, необходимо дорогое глубокое сравнение.

Ответ 1

Я постараюсь ответить на каждый вопрос как можно лучше.

Есть ли алгоритм сортировки, который минимизирует количество вызовов cmp (i, j)?

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

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

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

Я бы хотел, чтобы указатели содержали материал по этой теме.

Проверьте их:

По-видимому, Дональд Кнут, искусство программирования, Том 3 имеет раздел по этой теме, но у меня нет копии.
Wikipedia, конечно, имеет некоторое представление об этом.
Сортировка массива с минимальным количеством сравнений
Как определить минимальное количество свопов для сортировки списка на месте?
Ограничения методов сортировки на основе сравнения

Ответ 2

Теоретическое минимальное количество сравнений, необходимых для сортировки массива из n элементов в среднем, это lg (n!), что примерно n lg n - n. Нет никакого способа сделать это лучше среднего, если вы используете сравнения для упорядочения элементов.

Из стандартных алгоритмов сортировки на основе сравнения O (n log n), mergesort делает самое низкое количество сравнений (примерно n lg n, по сравнению с примерно 1,44 n lg n для быстрой сортировки и около n lg n + 2n для heapsort), поэтому он может быть хорошим алгоритмом для использования в качестве отправной точки. Обычно слияние происходит медленнее, чем у heapsort и quicksort, но, как правило, в предположении, что сравнение выполняется быстро.

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

Есть еще несколько доступных вариантов. Если вы знаете, что данные уже в основном отсортированы, вы можете использовать сортировку вставки или стандартную вариацию heapsort, чтобы попытаться ускорить сортировку. В качестве альтернативы вы можете использовать mergesort, но использовать оптимальную сеть сортировки в качестве базового случая, когда n мало. Это может свести к минимуму сравнение, чтобы дать вам заметное повышение производительности.

Надеюсь, это поможет!

Ответ 3

Метод, называемый Schwartzian transform, может быть использован для уменьшения любой проблемы сортировки до сортировки целых чисел. Это требует, чтобы вы применяли функцию f к каждому из ваших входных элементов, где f(x) < f(y) тогда и только тогда, когда x < y.

(Ответ на Python-ориентированный ответ, когда я думал, что вопрос был помечен [python])

Если вы можете определить функцию f такую, что f(x) < f(y) тогда и только тогда, когда x < y, вы можете сортировать с помощью

sort(L, key=f)

Python гарантирует, что key вызывается не более одного раза для каждого элемента итерабельного, который вы сортируете. Это обеспечивает поддержку преобразования Шварца.

Python 3 не поддерживает указание функции cmp, только параметр key. Эта страница позволяет легко преобразовать любую функцию cmp в функцию key.

Ответ 4

Существует ли алгоритм сортировки, который минимизирует количество вызовов cmp (i, j)?

Редактировать: Ах, извините. Существуют алгоритмы, которые минимизируют количество сравнений (ниже), но не то, что я знаю для определенных элементов.

Будет ли существование дорогостоящего (i, j) допустимого алгоритма, который пытается избежать дорогостоящих операций сравнения? Если да, можете ли вы указать мне на такой алгоритм?

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

Я бы хотел, чтобы указатели содержали материал по этой теме.

В Оптимальном и E ffi cient в месте слияния

Стабильное минимальное слияние хранилищ с помощью симметричных сравнений

Оптимальное стабильное слияние (кажется, это O (n log ² n) хотя

Практическое использование Mergesort на месте

Если вы реализуете любой из них, размещение их здесь может быть полезно и для других!:)

Ответ 5

Существует ли алгоритм сортировки, который минимизирует количество вызовов cmp (i, j)?

Алгоритм вставки слияния, описанный в книге Д. Кнута "Искусство компьютерного программирования", том 3, глава 5.3.1, использует меньше сравнений, чем другие алгоритмы на основе сравнения. Но все же ему нужны сравнения O (N log N).

Будет ли существование дорогостоящего (i, j) допустимого алгоритма, который пытается избежать дорогостоящих операций сравнения? Если да, можете ли вы указать мне на такой алгоритм?

Я думаю, что некоторые из существующих алгоритмов сортировки могут быть изменены, чтобы учитывать предикат expensive(i,j). Возьмем самый простой из них - сортировка вставки. Один из его вариантов, названный в Википедии как двоичная сортировка вставки, использует только сравнения O (N log N).

Он использует двоичный поиск для определения правильного местоположения для вставки новых элементов. Мы могли бы применять предикат expensive(i,j) после каждого этапа бинарного поиска, чтобы определить, дешево ли сравнивать вставленный элемент с "средним" элементом, найденным на этапе двоичного поиска. Если это дорого, мы могли бы попробовать "средний" элемент соседей, потом их соседей и т.д. Если бы не было никаких дешевых сравнений, мы просто возвращаемся к "среднему" элементу и выполняем дорогостоящее сравнение.

Существует несколько возможных оптимизаций. Если предикат и/или дешевые сравнения не так дешевы, мы можем вернуться к "среднему" элементу раньше, чем все другие возможности. Кроме того, если операции перемещения не могут считаться очень дешевыми, мы могли бы использовать некоторую структуру данных статистики заказа (например, Indexable skiplist) уменьшают стоимость вставки до O ( N log N).

Для модифицированного сортировки вставки требуется время O (N log N) для перемещения данных, вычисления предикатов O (N ²) и дешевые сравнения и дорогостоящие сравнения O (N log N) в худшем случае. Но, скорее всего, будут только предикаты O (N log N) и дешевые сравнения и O (1) дорогостоящие сравнения.

Рассмотрим множество возможных файлов. В этом приложении целью является поиск дубликатов файлов среди них.

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

Ответ 6

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

Если вы хотите ускорить процедуру, вы можете добавить некоторые метаданные, чтобы ускорить вычисление (не может быть более точным, если вы тоже).

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

Вы можете искать все упомянутые алгоритмы в википедии.

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

EDIT

Мне потребовалось некоторое время, чтобы подумать об этом, и я придумал слегка настроенное решение, которое, я думаю, сделает минимально возможное количество дорогостоящих сравнений, но полностью игнорирует общее количество сравнения. Он сделает не более (n-m) * log (k) дорогостоящие сравнения, где

n - размер входного вектора
m - количество отдельных компонентов, которые легко сравнивать друг с другом
k - максимальное количество элементов, которые трудно сравнивать и имеют последовательные ранги.

Здесь - описание алгоритма. Не стоит ничего говорить о том, что он будет работать намного хуже, чем простой тип слияния, если m не большой, а k мало. Общее время пробега - O [n ^ 4 + E (nm) log (k)], где E - стоимость дорогого сравнения (я предположил E → n, чтобы он не был уничтожен из асимптотического обозначения. Вероятно, что n ^ 4 может быть дополнительно уменьшено, по крайней мере, в среднем случае.

EDIT

В файле, который я опубликовал, содержатся некоторые ошибки. При попытке это я также исправил их (я упустил псевдокод для функции insert_sorted, но идея была верна. Я сделал программу Java, которая сортирует вектор целых чисел, с задержками, добавленными, как вы описали. Даже если бы я был настроен скептически, лучше, чем mergesort, если задержка значительна (я использовал задержку 1s снова для целочисленного сравнения, которое обычно занимает наносекунды)

Ответ 7

Большинство алгоритмов сортировки пытаются минимизировать количество сравнений при сортировке.

Мой совет: Выберите быстрый вид в качестве базового алгоритма и запомните результаты сравнений на случай, если вам снова удастся сравнить те же проблемы. Это должно помочь вам в O (N ^ 2) худшем случае быстрого сортировки. Имейте в виду, что это заставит вас использовать память O (N ^ 2).

Теперь, если вы действительно предприимчивы, вы можете попробовать ускорить сортировку Dual-Pivot.

Ответ 8

Что-то, о чем следует помнить, заключается в том, что если вы постоянно сортируете список с новыми дополнениями, и сравнение между двумя элементами гарантированно никогда не изменится, вы можете memoize операцию сравнения, которая приведет к увеличению производительности. В большинстве случаев это, к сожалению, неприменимо.

Ответ 9

Мы можем рассмотреть вашу проблему в другом направлении. Кажется, ваша проблема связана с IO, тогда вы можете использовать преимущества параллельных алгоритмов сортировки. На самом деле вы можете запускать много потоков для сравнения по файлам, а затем сортировать их по одному из наиболее известных параллельных алгоритмов, таких как Пример алгоритма сортировки.