Быстрее ли сортировать список после вставки элементов или добавления их в отсортированный список?

Question

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

Answer 1

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

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

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

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

Answer 2

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

Answer 3

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

Эффективность этого решения составляет O (n + m) + O (m log m), где n - размер исходного списка, а m - количество вставляемых элементов.

Редактировать: Поскольку этот ответ не вызывает никакой любви, я решил дополнить его некоторым примером кода на C ++. Я предполагаю, что отсортированный список хранится в связанном списке, а не в массиве. Это меняет алгоритм так, чтобы он выглядел скорее как вставка, чем слияние, но принцип тот же.

// Note that itemstoadd is modified as a side effect of this function
template<typename T>
void AddToSortedList(std::list<T> & sortedlist, std::vector<T> & itemstoadd)
{
    std::sort(itemstoadd.begin(), itemstoadd.end());
    std::list<T>::iterator listposition = sortedlist.begin();
    std::vector<T>::iterator nextnewitem = itemstoadd.begin();
    while ((listposition != sortedlist.end()) || (nextnewitem != itemstoadd.end()))
    {
        if ((listposition == sortedlist.end()) || (*nextnewitem < *listposition))
            sortedlist.insert(listposition, *nextnewitem++);
        else
            ++listposition;
    }
}

Answer 4

Я бы сказал, давайте проверим это! :)

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

Это уже показывает одну вещь: ответ на ваши вопросы сильно зависит от алгоритма сортировки, который вы используете. Если он будет иметь низкую производительность в почти отсортированных списках, вставка в нужную позицию будет намного быстрее, чем добавление в конце, а затем повторная сортировка; и сортировка слиянием может не подойти вам, поскольку может потребоваться слишком много внешней памяти, если список огромен. Кстати, я использовал собственную реализацию сортировки слиянием, которая использует только половину внешней памяти для простой реализации (которая требует столько же внешней памяти, сколько и сам размер массива).

Если сортировка слиянием не является опцией, а быстрая сортировка не является опцией, лучшей альтернативой, вероятно, является сортировка кучи.

Мои результаты таковы: добавление новых элементов просто в конце, а затем повторная сортировка массива происходит на несколько величин быстрее, чем вставка их в правильное положение. Однако в моем исходном массиве было 10 млн. Элементов (отсортировано), и я добавлял еще один (не отсортированный). Поэтому, если вы добавите 10 элементов в массив из 10 миллионов, их правильная вставка будет намного быстрее, чем повторная сортировка всего. Таким образом, ответ на ваш вопрос также зависит от размера исходного (отсортированного) массива и количества новых элементов, которые вы хотите добавить в него.

Answer 5

В принципе, создать дерево быстрее, чем отсортировать список. Древовидные вставки имеют O (log (n)) для каждой вставки, что приводит к общему O (n log (n)). Сортировка по O (n log (n)).

Именно поэтому в Java есть TreeMap (в дополнение к реализациям ListS для TreeSet, TreeList, ArrayList и LinkedList).

• TreeSet хранит вещи в порядке сравнения объектов. Ключ определяется интерфейсом Comparable.

• LinkedList сохраняет все в порядке вставки.

• ArrayList использует больше памяти, быстрее для некоторых операций.

• TreeMap, аналогично, устраняет необходимость сортировки по ключу. Карта строится в ключевом порядке во время вставок и постоянно поддерживается в отсортированном порядке.

Однако по какой-то причине Java-реализация TreeSet немного медленнее, чем использование ArrayList и сортировки.

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

Answer 6

Если список а) уже отсортирован и б) динамичен по природе, то вставка в отсортированный список всегда должна выполняться быстрее (найти правильное место (O (n)) и вставить (O (1))).

Однако, если список статичен, то должна произойти перестановка оставшейся части списка (O (n), чтобы найти правильное место, и O (n), чтобы скользить вниз).

В любом случае, вставка в отсортированный список (или что-то вроде бинарного дерева поиска) должна быть быстрее.

O (n) + O (n) всегда должно быть быстрее, чем O (N log n).

Answer 7

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

Если вы вместо этого вставите их в переднюю часть, это будет O (1), но после быстрой сортировки все равно будет O (N log N).

Я бы пошел с первым подходом, потому что он может быть немного быстрее. Если начальный размер вашего списка, N, намного больше, чем количество элементов для вставки, X, то подход к вставке будет O (X log N). Сортировка после вставки в начало списка происходит O (N log N). Если N = 0 (IE: ваш список изначально пуст), скорость вставки в отсортированном порядке или последующая сортировка одинаковы.

Answer 8

На высоком уровне это довольно простая проблема, потому что вы можете думать о сортировке как об итеративном поиске. Если вы хотите вставить элемент в упорядоченный массив, список или дерево, вам нужно найти точку, в которую его нужно вставить. Затем вы вставляете его по низкой цене. Таким образом, вы можете думать о алгоритме сортировки, как о том, чтобы просто брать кучу вещей и, один за другим, искать правильную позицию и вставлять их. Таким образом, сортировка вставкой (O (n * n)) является итеративным линейным поиском (O (n)). Дерево, куча, слияние, основание и быстрая сортировка (O (n * log (n))) можно рассматривать как повторный бинарный поиск (O (log (n))). Возможно иметь сортировку O (n), если основной поиск - O (1), как в упорядоченной хеш-таблице. (Примером этого является сортировка 52 карточек путем помещения их в 52 ячейки.)

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

Конечно, если n мало, например 10, все обсуждение глупо.

Answer 9

Вставка элемента в отсортированный список занимает O(n) время, а не O(log n) время. Вы должны найти место, чтобы положить его, потратив O(log n) времени. Но тогда вы должны перебрать все элементы - это займет O(n) время. Таким образом, вставка с сохранением сортировки равна O(n ^ 2), где как вставка их всех, а затем сортировка - O(n log n).

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

Так что делайте вставку все и сортируйте решение, если число вставок велико, иначе это, вероятно, не будет иметь значения.

Answer 10

(Если список, о котором вы говорите, похож на C # List<T>.) Добавление некоторых значений в правильные позиции в отсортированный список с большим количеством значений потребует меньше операций. Но если количество добавляемых значений становится большим, это потребует большего.

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