Вопрос

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

Автор вопроса: someguy03.09.2010Ответов: 6

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

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

performance sorting insert data-structures

Ответы

Ответ 1 · рейтинг 6 · P Daddy

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

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

Ответ 2 · рейтинг 7 · squadette

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

Ответ 3 · рейтинг 2 · sadakurapati

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

Ответ 4 · рейтинг 2 · Isaac Turner

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

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

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

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

Ответ 5 · рейтинг 1 · Mike Dunlavey

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

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

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

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

Ответ 6 · рейтинг 1 · Quasimondo

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

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

Перевод вопроса и ответов сообщества Stack Overflow, лицензия CC BY-SA. Оригинал на Stack Overflow.