Алгоритмы сортировки для данных известного статистического распределения?

Ответ 1

Если данные, которые вы сортируете, имеют известное распределение, я бы использовал алгоритм Bucket Sort. Вы могли бы добавить к нему дополнительную логику, чтобы вы вычислили размер и/или позиции различных ведер, основанных на свойствах распределения (например: для гаусса, у вас может быть ведро каждый (сигма/к) от среднего, где сигма является стандартным отклонением распределения).

Благодаря известному распределению и модификации стандартного алгоритма сортировки Bucket таким образом вы, вероятно, получите Histogram Sortсильным > алгоритмом или чем-то близким к нему. Конечно, ваш алгоритм будет вычислить быстрее, чем алгоритм сортировки гистограмм, потому что, вероятно, не будет необходимости делать первый проход (описанный в ссылке), поскольку вы уже знаете распределение.

Изменить:, учитывая ваши новые критерии вашего вопроса (хотя мой предыдущий ответ относительно ссылок на гистограмму для ссылки на респектабельный NIST и содержит информацию о производительности), здесь представлена ​​статья журнала экспертной оценки из Международной конференции по параллельной обработке:

Адаптивный разделитель данных для сортировки с использованием распределения вероятностей

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

Ответ 2

Похоже, вы можете прочитать Self-Improving Algorithms: они достигают оптимального ожидаемого времени выполнения для произвольных входных распределений.

Мы приводим такие самосовершенствовающиеся алгоритмы для двух проблем: (i) сортировка последовательность чисел и (ii) вычисление триангуляция Делоне плоского точечный набор. Оба алгоритма оптимальная ожидаемая предельная сложность. Алгоритмы начинаются с обучения фазы, в течение которой они собирают информация о вводе распределения, а затем стационарный режим, в котором устанавливаются алгоритмы к их оптимизированным воплощениям.

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

Ответ 3

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

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

Вставка всех элементов в хеш-таблицу, а извлечение их по порядку будет O (n), когда хеш является совершенным (при условии, что стоимость вычисления хеш-функции равна O (1), а операции структуры данных хэш-функции - O (1)).

Я бы использовал массив кубов фибоначчи для реализации хеш-таблицы.

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

Ответ 4

Алгоритмы сортировки компьютеров можно разделить на две категории, сортировка на основе сортировки и сортировка без сравнения. Для сравнения сортировка, время сортировки в наилучшей производительности Ω (nlogn), а в худшем случае - время сортировки может увеличиваться до O (n2). В последние годы, некоторые усовершенствованные алгоритмы были предложены для ускорить сортировку на основе сравнения, такую ​​как расширенная быстрый сортировка в соответствии с характеристиками распределения данных , Однако среднее время сортировки для этих алгоритмы - это просто Ω (nlog2n) и только в лучшем случае может ли он достигнуть O (n). В отличие от сортировки на основе сравнения, сортировка без сравнения, такая как сортировка счетчиков, сортировка ковша и сортировка по основанию зависят в основном от ключа и расчет адресов. Когда значения клавиш конечный от 1 до m, вычислительный сложность сортировки без сравнения O (M + N). В частности, когда m = O (n), время сортировки может достигать O (n). Однако, когда m = n2, n3,...., верхняя граница линейного времени сортировки не может быть получена. Среди сортировки без сравнения сортировка ковша распределяет группу записей с похожими ключами в соответствующий "ведро", то другой алгоритм сортировки применяется к записям в каждом ковше. С ковшом сортировка, разбиение записей на m ведра меньше занимая много времени, в то время как только несколько записей будут содержащихся в каждом ковше, так что "сортировка очистки" алгоритм может быть применен очень быстро. Следовательно, сортировка ковша имеет потенциал для асимптотического сохранения время сортировки по сравнению с алгоритмами Ω (nlogn). Очевидно, как равномерно распределять все записи в ведра играют важную роль в сортировке ковша. Следовательно, вам нужен метод построения хэш-функции согласно распределению данных, которое используется для равномерно распределить n записей в n ковшей на основе ключ каждой записи. Следовательно, время сортировки предлагаемый алгоритм сортировки ковша достигнет O (n) при любых обстоятельствах.

проверьте этот документ: http://ieeexplore.ieee.org/xpls/abs_all.jsp?arnumber=5170434&tag=1

Ответ 5

Сортировка ковша даст вам линейный алгоритм сортировки по времени, если вы можете вычислить CDF каждой точки в O (1) раз.

Алгоритм, который вы также можете найти в другом месте, выглядит следующим образом:

a = array(0, n - 1, [])          // create an empty list for each bucket
for x in input:
  a[floor(n * cdf(x))].append(x) // O(1) time for each x
input.clear()
for i in {0,...,n - 1}:
  // this sorting step costs O(|a[i]|^2) time for each bucket
  // but most buckets are small and the cost is O(1) per bucket in expectation
  insertion_sort(a[i])
  input.concatenate(a[i])

Время ожидания - это O (n) в ожидании, так как в ожидании есть пары O (n) (x, y), такие, что x и y попадают в одно и то же ведро, а время выполнения сортировки вставки точно равно O ( n + # пар в том же ковше). Анализ аналогичен анализу FKS статическое идеальное хеширование.

EDIT: если вы не знаете дистрибутив, но знаете, из какого семейства это, вы можете просто оценить распределение в O (n), в случае Гаусса, вычислив среднее значение и дисперсию, а затем использовать тот же алгоритм (кстати, вычисление cdf в этом случае нетривиально).

Ответ 6

Вы можете использовать эту информацию в quicksort, чтобы выбрать значение поворота. Я думаю, что это улучшило бы вероятность того, что алгоритм останется в стороне от сложности худшего случая O (N ** 2).

Ответ 7

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

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