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

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

Это массив или связанный список? Я знаю, что вы сказали «список», но упомянули о двоичном выполнении, что подразумевает массив.

Mike F 04.10.2008 01:14

изменен тег "алгоритмы" на "алгоритм"

Eric 04.10.2008 18:59
Стоит ли изучать PHP в 2023-2024 годах?
Стоит ли изучать PHP в 2023-2024 годах?
Привет всем, сегодня я хочу высказать свои соображения по поводу вопроса, который я уже много раз получал в своем сообществе: "Стоит ли изучать PHP в...
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
Поведение ключевого слова "this" в стрелочной функции в сравнении с нормальной функцией
В JavaScript одним из самых запутанных понятий является поведение ключевого слова "this" в стрелочной и обычной функциях.
Приемы CSS-макетирования - floats и Flexbox
Приемы CSS-макетирования - floats и Flexbox
Здравствуйте, друзья-студенты! Готовы совершенствовать свои навыки веб-дизайна? Сегодня в нашем путешествии мы рассмотрим приемы CSS-верстки - в...
Тестирование функциональных ngrx-эффектов в Angular 16 с помощью Jest
В системе управления состояниями ngrx, совместимой с Angular 16, появились функциональные эффекты. Это здорово и делает код определенно легче для...
Концепция локализации и ее применение в приложениях React ⚡️
Концепция локализации и ее применение в приложениях React ⚡️
Локализация - это процесс адаптации приложения к различным языкам и культурным требованиям. Это позволяет пользователям получить опыт, соответствующий...
Пользовательский скаляр GraphQL
Пользовательский скаляр GraphQL
Листовые узлы системы типов GraphQL называются скалярами. Достигнув скалярного типа, невозможно спуститься дальше по иерархии типов. Скалярный тип...
75
2
54 870
13
Перейти к ответу Данный вопрос помечен как решенный

Ответы 13

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

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

Daniel Rikowski 18.11.2008 18:42

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

Но помните, что большая буква «О» касается только масштабирования скорости с количеством элементов, возможно, что для вашего приложения вставка посередине стоит дорого (например, если бы это был вектор), и поэтому добавление и сортировка после этого могут быть лучше.

Вставка в отсортированный список - O (log n). Вставка в хеш - это O (1).

bmdhacks 04.10.2008 01:07

Хорошо, вы исправили свои обозначения, но теперь ваше первое утверждение неверно. Скорость сортировки и вставки одинакова. Сортировка выполняется за O (N log N), а при вставке выполняется операция O (log N) N раз, то есть O (N log N).

bmdhacks 04.10.2008 01:13

Но это другое N, если вам нужно вставить только 10 элементов в миллион, тогда 10 * (log 1M) превосходит 10 + (1M log 1M) ps. Извините, я оставил вам комментарий, поблагодарил вас за обнаружение опечатки, но похоже, что она исчезла?

Martin Beckett 04.10.2008 01:16

Справедливо. Технически Big-O не заботится о размере N, только Big-Omega заботится, но, вероятно, только профессорам информатики. Спасибо, что смирились с моим вниманием.

bmdhacks 04.10.2008 01:31

И большинство людей считает, что O () говорит вам все о скорости. Строительство пирамид занимает O (n), но все же намного медленнее, чем сортировка их высоты!

Martin Beckett 04.10.2008 01:39

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

Greg Rogers 07.10.2008 19:06

@Martin Beckett: Если только вы не построите много пирамид;)

Maciej Piechotka 19.08.2010 19:26

Примерно то же самое. Вставка элемента в отсортированный список - это O (журнал 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: ваш список изначально пуст), скорость вставки в отсортированном порядке или последующей сортировки такая же.

Не привередничать, но N - это количество элементов, которые нужно вставить, поэтому последний абзац вашего ответа не имеет для меня особого смысла! Вы имели в виду «если N не слишком велико»?

Remo.D 04.10.2008 01:13

Отредактировано для пояснения после комментария Remo.D.

bmdhacks 04.10.2008 01:22

параграф 2 в некоторых случаях неверен. Выполнение быстрой сортировки почти отсортированного списка приближается к O (n ^ 2), а не к O (n log n).

Tony BenBrahim 04.10.2008 02:17

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

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

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

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

вставка в динамической конструкции, такой как связанный список, по-прежнему O (1) за вставку. Так что да, в целом это составляет O (N) - но это не мультипликативно, это аддитивно (т.е. 2 раза O (n), а не O (n ^ 2)).

warren 06.10.2008 23:10

вставка должна быть O (log (N)), если вы все делаете правильно и имеете относительно равномерно распределенные данные

tloach 08.10.2008 16:56

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

Peter Cordes 13.09.2015 05:51

@ PeterCordes - Я вообще не описываю слияние двух отсортированных списков: я описываю добавление элементов неизвестного порядка сортировки в уже отсортированный список

warren 14.09.2015 17:03

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

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

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

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

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

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

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

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

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

hazzen 04.10.2008 04:33

Проведите несколько тестов скорости, и вы убедитесь, что это не так. TreeSet против ArrayList, ArrayList был примерно в 2 раза быстрее, чтобы добавить 500 тыс. Случайных чисел, отсортировать и выгрузить их в другой список. Если мы не перенесем их в другой список, ArrayList выиграет примерно в 1,6 раза.

hazzen 04.10.2008 11:48

TreeSet и TreeMap - это, по сути, один и тот же класс; TreeSet <E> - это TreeMap <E, Object> со значением, установленным для одноэлементного объекта при вставке. Время почти идентично и все еще примерно в 2 раза медленнее, чем решение ArrayList.

hazzen 04.10.2008 22:37

Я сказал, что вставить все в ArrayList + Collections.sort примерно в 2 раза быстрее, чем просто вставить все в Tree [Set | Map]. Это для большого количества значений. Разница по-прежнему составляет примерно 2x для небольшого количества значений, но 1 мс против 2 мс особого значения не имеет.

hazzen 05.10.2008 00:08

Причина разницы в скорости заключается в том, что ArrayList реализован с использованием одного массива, а древовидная карта представляет собой связанную структуру с различными объектами узлов для каждой записи. Доступ к массивам намного быстрее, и JVM может оптимизировать лучше, чем объекты (регистры повторного использования, лучшая локальность кеша)

ddimitrov 05.10.2008 07:56

TreeList? Я никогда не видел таких. Искал его на платформе Java ™, Standard Edition 7 и не нашел.

Peter Perháč 26.11.2013 18:59

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

http://en.wikipedia.org/wiki/Radix_sort#Efficiency

Если это .NET, а элементы являются целыми числами, их быстрее добавить в словарь (или, если вы используете .Net 3.0 или выше, используйте HashSet, если вы не против потери дубликатов). Это дает вам автоматическую сортировку.

Я думаю, что струны тоже будут работать так же. Прелесть в том, что вы получаете вставку O (1) и сортировку таким образом.

Dictionary <T> не является отсортированной коллекцией. SortedDictionary <T> есть.

Ihar Bury 04.10.2008 01:30

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

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

Ответ принят как подходящий

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

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

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

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

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

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

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

Я думаю, вы совершенно неверно относитесь к нотации О. Вставка элемента в список - это не O (n), это всегда O (1) в теореме алгоритма. Перемещение миллионов байтов в памяти может быть непостоянной операцией, но нотация O касается не времени, которое на это требуется, а сложности, которая равна 1.

Mecki 08.10.2008 14:51

Если это не постоянная операция, это не O (1). Период. Код для вставки в список (для списка на основе массива): for (i = last; i> idx; --i) {list [i + 1] = list [i]; } список [idx] = элемент; Я не думаю, что вы будете спорить, что это O (n). Вы не можете просто игнорировать часть своего кода в Big O.

hazzen 09.10.2008 06:31

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

Mike Dunlavey 26.11.2008 03:01

@MikeDunlavey Для всех, кто этим занимается, мы вошли в область сложности, зависящей от реализации. Возможно, можно составить список, в котором вставка является операцией O (1), но это не значит, что ваш список такой. Например, std::vector::insert - это O (n), тогда как std::list::insert - O (1).

iAdjunct 15.02.2021 16:58

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

Эффективность этого решения составляет 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;
    }
}

O (n + m) + O (m log m) равно O (n + m)

Miles Rout 16.03.2013 08:35

@MilesRout, это совсем не так. m log m > m, поэтому лучшее, что вы можете упростить, - это O(n+(m log m)).

Mark Ransom 16.03.2013 21:42

ой, не видел m перед журналом m. игнорируй меня!

Miles Rout 17.03.2013 03:51

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

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

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

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

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

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

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

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

Другие вопросы по теме