Самая быстрая структура данных для вставки/сортировки

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


performance sorting insert data-structures
person someguy    schedule 03.09.2010    source источник
comment
если вы просматриваете массив, зачем вам нужна сортировка структуры данных? Должен ли он быть в порядке после каждой вставки?   -  person Chris Card    schedule 03.09.2010
comment
Да, это должно быть в порядке после вставки. Я не буду индексировать элемент напрямую, а скорее узел, который должен иметь доступ к соседним узлам.   -  person someguy    schedule 03.09.2010
comment
Вы сами себе противоречите. В вопросе говорится, что я буду вставлять гораздо больше, чем сортировать, но в вашем комментарии говорится, что это должно быть в порядке после [каждой] вставки. Если верно первое, то мой ответ может быть уместным. Если последнее верно, то вам, вероятно, лучше с деревом, как предлагает отряд (хотя я не уверен, что его нужно сбалансировать, как он предлагает, поскольку поиск не представляет большой проблемы).   -  person P Daddy    schedule 03.09.2010
comment
Упс, не правильно подумал. Я имел в виду, что не обязательно следовать порядку после каждой вставки. Извиняюсь.   -  person someguy    schedule 03.09.2010

Ответы (6)


arrow_upward
6
arrow_downward

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

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

person P Daddy    schedule 03.09.2010
comment
@ хотя я не уверен, что его нужно сбалансировать, как он предлагает, поскольку поиск не представляет большой проблемы. Разве вставка не будет быстрее, если она сбалансирована? P.S. Под поиском я не подразумеваю поиск. - person someguy; 03.09.2010
comment
@someguy: Ну, я полагаю, это зависит от того, сколько накладных расходов на балансировку на самом деле возникает и сколько обходов это предотвращает. - person P Daddy; 03.09.2010
comment
Вы можете быть умны о сорте. Если вы создаете оболочку для списка/вектора, вы можете отслеживать, какая часть уже была отсортирована (это начало списка, поэтому вам нужен только один индекс). Затем, когда вы хотите прибегнуть, вы просто сортируете несортированную часть и объединяете. Тогда сложность намного меньше, чем обычно O (n log n) для сортировки. - person Jeremy West; 14.02.2018

arrow_upward
7
arrow_downward

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

person squadette    schedule 03.09.2010
comment
Мне было интересно, есть ли что-то более быстрое, плюс я хотел бы вручную сбалансировать/сортировать. - person someguy; 03.09.2010
comment
Если вы хотите, чтобы он сортировался после каждой вставки с произвольным количеством элементов, чтобы вы не могли просто иметь ведра для каждого элемента, тогда дерево - это путь. Это вставляет и сортирует в той же операции; Боюсь, вы не станете намного быстрее. - person thecoop; 03.09.2010

arrow_upward
2
arrow_downward

Используйте любое из сбалансированных двоичных деревьев, таких как деревья AVL. Это должно дать временную сложность O (lg N) для обеих операций, которые вы ищете.

person sadakurapati    schedule 28.08.2013

arrow_upward
2
arrow_downward

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

Худшая и средняя временная сложность:

  • O(log N) вставка
  • O(1) прочитать наибольшее значение
  • O (log N), чтобы удалить наибольшее значение

Можно перенастроить, чтобы задать наименьшее значение вместо наибольшего. Многократно удаляя наибольшее/наименьшее значение, вы получаете отсортированный список за O (N log N).

person Isaac Turner    schedule 20.06.2016

arrow_upward
1
arrow_downward

Если вы можете делать много вставок перед каждой сортировкой, то, очевидно, вам следует просто добавлять элементы и сортировать не раньше, чем вам нужно. Моя любимая сортировка слиянием. Это O (N * Log (N)), хорошо себя ведет и имеет минимум манипуляций с хранилищем (новые, malloc, балансировка дерева и т. Д.).

ОДНАКО, если значения в коллекции являются целыми числами и достаточно плотными, вы можете использовать сортировку O(N), где вы просто используете каждое значение в качестве индекса в достаточно большом массиве и устанавливаете логическое значение TRUE в этом индексе. Затем вы просто сканируете весь массив и собираете ИСТИННЫЕ индексы.

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

Несмотря на это, выделение/удаление памяти обходится дорого, и вам следует избегать этого путем предварительного выделения или объединения памяти, если это возможно.

person Mike Dunlavey    schedule 06.09.2010

arrow_upward
1
arrow_downward

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

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

person Quasimondo    schedule 24.06.2013