Лучший алгоритм непрерывной сортировки?

Question

У меня есть набор данных с двойной точностью, и мне нужно, чтобы их список всегда сортировался. Каков наилучший алгоритм сортировки данных по мере их добавления?

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

Размер набора действительно переменный, от небольшого числа (30) до большого количества данных (+ 10M).

Answer 1

Создание самобалансирующегося двоичного дерева, такого как красно-черное дерево или AVL-дерево , позволит вставлять и удалять Θ (lg n) и извлекать Θ (n) все элементы в отсортированном порядке (путем обхода в глубину) с использованием Θ (n) памяти. Реализация несколько сложна, но они эффективны, и большинство языков будут иметь библиотечные реализации, поэтому в большинстве случаев они являются хорошим первым выбором.

Кроме того, получение i-го элемента может быть выполнено путем аннотирования каждого ребра (или, что то же самое, узла) в дереве общим количеством узлов под ним. Тогда можно найти i-й элемент в Θ (lg n) времени и Θ (1) пространстве с чем-то вроде:

node *find_index(node *root, int i) {
  while (node) {
    if (i == root->left_count)
      return root;
    else if (i < root->left_count)
      root = root->left;
    else {
      i -= root->left_count + 1;
      root = root->right;
    }
  }
  return NULL; // i > number of nodes
}

Реализацию, которая поддерживает это, можно найти в debian's libavl ; к сожалению, сайт сопровождающего кажется недоступным, но его можно получить с серверов debian .

Answer 2

Структура , используемая для индексов программ баз данных , представляет собой дерево B +. Это сбалансированное n-арное дерево с интервалами.

Из Википедии :

Для дерева B + порядка b с индексами h уровней:

• Максимальное количество сохраняемых записей: n = b ^ h
• Минимальное количество ключей - 2 (б / 2) ^ (ч-1)
• Место, необходимое для хранения дерева, составляет O (n)
• Для вставки записи требуются операции O (log-b (n)) в худшем случае
• Поиск записи требует O (log-b (n)) операций в худшем случае
• Удаление (ранее расположенной) записи требует операций O (log-b (n)) в худшем случае
• Выполнение запроса диапазона с k элементами, входящими в диапазон, требует O (log-b (n + k)) операций в худшем случае.

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

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

Интересная презентация о деревьях B +: Индексы с древовидной структурой

Вы можете получить весь код на C ++ .

---

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

Возможно, вам лучше всего использовать SortedList или, что еще лучше, SortedDictionary. См. Статью: Снижение производительности из SortedList . Обе структуры имеют функцию GetKey, которая будет возвращать i-й элемент.

Answer 3

Если вам просто нужно знать i-й наименьший элемент, как сказано в комментариях, используйте алгоритм BFPRT, который назван в честь фамилий авторов: Blum, Floyd, Pratt, Rivest и Tarjan и в целом согласен быть самой большой концентрацией больших мозгов информатики в той же самой газете. O (n) худший случай.

Answer 4

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

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

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

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

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

Answer 5

Я бы использовал очередь кучи / приоритета. Наихудший случай такой же, как средний случай для времени выполнения. Следующий элемент можно найти за время O (log n).

Вот шаблонная реализация C # , которую я получил из этого кода .

Answer 6

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

Если вам всегда нужно, чтобы весь список сортировался каждый раз, тогда не так много других вариантов, кроме сортировки с вставкой . Вероятно, это будет O (N ^ 2), хотя с ОГРОМНЫМИ хлопотами связаны пропустить списки вы можете сделать это O (N log N).

Answer 7

Рандомизированные Jumplists также интересны. Они требуют меньше места, как BST и скиплисты. Вставка и удаление O (log n)

Answer 8

Проверьте сравнение алгоритмов сортировки в Википедии.

Answer 9

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