Если у меня есть отсортированный список (скажем, быстрая сортировка для сортировки), если мне нужно добавить много значений, лучше ли приостановить сортировку и добавить их в конец, а затем отсортировать или использовать двоичную отбивку для правильного размещения элементов, пока добавляя их. Имеет ли значение, если элементы расположены в случайном порядке или уже более или менее упорядочены?
изменен тег "алгоритмы" на "алгоритм"
Обычно гораздо лучше использовать куча. Короче говоря, он разделяет расходы на поддержание порядка между толкачом и сборщиком. Обе операции - O (log n), а не O (n log n), как и большинство других решений.
Это особенно хороший совет, если список представляет собой какую-то очередь с приоритетом. Гугл на предмет слабых куч в таком случае.
Вставка элемента в отсортированный список - O (log n), а сортировка списка - O (n log N) Это предполагает, что всегда лучше сначала сортировать, а затем вставлять
Но помните, что большая буква «О» касается только масштабирования скорости с количеством элементов, возможно, что для вашего приложения вставка посередине стоит дорого (например, если бы это был вектор), и поэтому добавление и сортировка после этого могут быть лучше.
Вставка в отсортированный список - O (log n). Вставка в хеш - это O (1).
Хорошо, вы исправили свои обозначения, но теперь ваше первое утверждение неверно. Скорость сортировки и вставки одинакова. Сортировка выполняется за O (N log N), а при вставке выполняется операция O (log N) N раз, то есть O (N log N).
Но это другое N, если вам нужно вставить только 10 элементов в миллион, тогда 10 * (log 1M) превосходит 10 + (1M log 1M) ps. Извините, я оставил вам комментарий, поблагодарил вас за обнаружение опечатки, но похоже, что она исчезла?
Справедливо. Технически Big-O не заботится о размере N, только Big-Omega заботится, но, вероятно, только профессорам информатики. Спасибо, что смирились с моим вниманием.
И большинство людей считает, что O () говорит вам все о скорости. Строительство пирамид занимает O (n), но все же намного медленнее, чем сортировка их высоты!
если это был вектор, найти место и вставить элемент можно за O (N). Но добавление и сортировка после этого только для одного элемента еще хуже - O (N log N).
@Martin Beckett: Если только вы не построите много пирамид;)
Примерно то же самое. Вставка элемента в отсортированный список - это 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.
параграф 2 в некоторых случаях неверен. Выполнение быстрой сортировки почти отсортированного списка приближается к O (n ^ 2), а не к O (n log n).
Если список а) уже отсортирован и б) является динамическим по своей природе, то вставка в отсортированный список всегда должна выполняться быстрее (найти нужное место (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)).
вставка должна быть O (log (N)), если вы все делаете правильно и имеете относительно равномерно распределенные данные
Ваш первый абзац описывает одно слияние двух отсортированных связанных списков. Если одно слияние - O (N), ваша общая сортировка будет O (NlogN), если вы каким-то образом не сможете получить количество отсортированных фрагментов O (1) менее чем за O (NlogN) времени. Поэтапная сортировка путем вставки каждого элемента в двоичное дерево поиска составляет O (N log N), потому что операция вставки - O (logN), и вам нужно сделать это N раз. (простые бинарные деревья имеют O (N) вставки в худшем случае для одного элемента.) В любом случае, последние два абзаца - ерунда. Ни один из них не поможет вам превзойти O (NlogN) или даже превзойти qsort.
@ PeterCordes - Я вообще не описываю слияние двух отсортированных списков: я описываю добавление элементов неизвестного порядка сортировки в уже отсортированный список
В принципе, быстрее создать дерево, чем сортировать список. Дерево вставок составляет O (log (n)) для каждой вставки, что приводит к общему O (nжурнал (п)). Сортировка за O (nlog (n)).
Вот почему в Java есть TreeMap (в дополнение к реализациям списка TreeSet, TreeList, ArrayList и LinkedList).
TreeSet сохраняет порядок сравнения объектов. Ключ определяется интерфейсом Comparable.
LinkedList хранит элементы в порядке вставки.
ArrayList использует больше памяти, быстрее выполняет некоторые операции.
TreeMap аналогичным образом устраняет необходимость сортировки по ключу. Карта строится в порядке ключей во время вставок и постоянно поддерживается в отсортированном порядке.
Однако по какой-то причине Java-реализация TreeSet немного медленнее, чем использование ArrayList и сортировки.
[Трудно предположить, почему это будет значительно медленнее, но это так. Это должно быть немного быстрее за один проход данных. Зачастую управление памятью обходится дороже алгоритмического анализа.]
Я был бы осторожен, говоря, что дерево быстрее, чем список. Это действительно зависит от размера ввода и используемой реализации дерева.
Проведите несколько тестов скорости, и вы убедитесь, что это не так. TreeSet против ArrayList, ArrayList был примерно в 2 раза быстрее, чтобы добавить 500 тыс. Случайных чисел, отсортировать и выгрузить их в другой список. Если мы не перенесем их в другой список, ArrayList выиграет примерно в 1,6 раза.
TreeSet и TreeMap - это, по сути, один и тот же класс; TreeSet <E> - это TreeMap <E, Object> со значением, установленным для одноэлементного объекта при вставке. Время почти идентично и все еще примерно в 2 раза медленнее, чем решение ArrayList.
Я сказал, что вставить все в ArrayList + Collections.sort примерно в 2 раза быстрее, чем просто вставить все в Tree [Set | Map]. Это для большого количества значений. Разница по-прежнему составляет примерно 2x для небольшого количества значений, но 1 мс против 2 мс особого значения не имеет.
Причина разницы в скорости заключается в том, что ArrayList реализован с использованием одного массива, а древовидная карта представляет собой связанную структуру с различными объектами узлов для каждой записи. Доступ к массивам намного быстрее, и JVM может оптимизировать лучше, чем объекты (регистры повторного использования, лучшая локальность кеша)
TreeList? Я никогда не видел таких. Искал его на платформе Java ™, Standard Edition 7 и не нашел.
Вы должны добавить их раньше, а затем использовать сортировку по основанию, которая должна быть оптимальной
Если это .NET, а элементы являются целыми числами, их быстрее добавить в словарь (или, если вы используете .Net 3.0 или выше, используйте HashSet, если вы не против потери дубликатов). Это дает вам автоматическую сортировку.
Я думаю, что струны тоже будут работать так же. Прелесть в том, что вы получаете вставку O (1) и сортировку таким образом.
Dictionary <T> не является отсортированной коллекцией. SortedDictionary <T> есть.
(Если список, о котором вы говорите, похож на 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.
Если это не постоянная операция, это не O (1). Период. Код для вставки в список (для списка на основе массива): for (i = last; i> idx; --i) {list [i + 1] = list [i]; } список [idx] = элемент; Я не думаю, что вы будете спорить, что это O (n). Вы не можете просто игнорировать часть своего кода в Big O.
Это O (1), если он ограничен некоторой константой для любого N. Есть способы организовать массив так, чтобы вставка была эффективной, например, сделав его из блоков, которые имеют определенное количество пустого пространства.
@MikeDunlavey Для всех, кто этим занимается, мы вошли в область сложности, зависящей от реализации. Возможно, можно составить список, в котором вставка является операцией O (1), но это не значит, что ваш список такой. Например, std::vector::insert
- это O (n), тогда как std::list::insert
- O (1).
Если вы добавляете в группы, вы можете использовать сортировку слиянием. Отсортируйте список добавляемых элементов, затем скопируйте из обоих списков, сравнивая элементы, чтобы определить, какой из них будет скопирован следующим. Вы даже можете скопировать на месте, если измените размер целевого массива и начнете работать с конца в обратном направлении.
Эффективность этого решения составляет 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)
@MilesRout, это совсем не так. m log m > m
, поэтому лучшее, что вы можете упростить, - это O(n+(m log m))
.
ой, не видел m перед журналом m. игнорируй меня!
Я бы сказал, давай проверим! :)
Я пробовал с быстрой сортировкой, но сортировка почти сортировочного массива с помощью быстрой сортировки ... ну, на самом деле не очень хорошая идея. Я попробовал модифицированный, отрезав 7 элементов и применив для этого сортировку вставкой. Тем не менее, производительность ужасная. Я переключился на сортировку слиянием. Для сортировки может потребоваться довольно много памяти (она не на месте), но производительность намного лучше для отсортированных массивов и почти идентична для случайных (начальная сортировка заняла почти одинаковое время для обоих, быстрая сортировка была лишь немного быстрее ).
Это уже показывает одно: ответ на ваши вопросы сильно зависит от используемого вами алгоритма сортировки. Если он будет иметь низкую производительность в почти отсортированных списках, вставка в правильную позицию будет намного быстрее, чем добавление в конце с последующей повторной сортировкой; и сортировка слиянием может быть для вас не вариантом, так как может потребоваться слишком много внешней памяти, если список огромен. Кстати, я использовал настраиваемую реализацию сортировки слиянием, которая использует только половину внешнего хранилища для наивной реализации (для которой требуется столько же внешнего хранилища, сколько размер самого массива).
Если сортировка слиянием не подходит и быстрая сортировка точно не подходит, лучшей альтернативой, вероятно, является сортировка кучи.
Мои результаты: Добавление новых элементов просто в конце, а затем повторная сортировка массива было на несколько порядков быстрее, чем их вставка в правильное положение. Однако в моем исходном массиве было 10 миллионов элементов (отсортированных), и я добавлял еще один миллион (несортированный). Таким образом, если вы добавляете 10 элементов в массив размером 10 миллионов, их правильная вставка будет намного быстрее, чем повторная сортировка всего. Итак, ответ на ваш вопрос также зависит от того, насколько велик исходный (отсортированный) массив и сколько новых элементов вы хотите добавить к нему.
На высоком уровне это довольно простая проблема, потому что вы можете думать о сортировке как о повторном поиске. Если вы хотите вставить элемент в упорядоченный массив, список или дерево, вам нужно найти точку, в которой его нужно вставить. Затем вы вставляете его, надеюсь, по низкой цене. Таким образом, вы можете думать об алгоритме сортировки, как о том, что он просто берет кучу вещей и, один за другим, ищет нужную позицию и вставляет их. Таким образом, сортировка вставкой (O (n * n)) является повторным линейным поиском (O (n)). Дерево, куча, слияние, основание и быстрая сортировка (O (n * log (n))) можно рассматривать как повторяющийся двоичный поиск (O (log (n))). Возможна сортировка O (n), если основной поиск - O (1), как в упорядоченной хеш-таблице. (Примером этого является сортировка 52 карт, бросая их в 52 ячейки.)
Итак, ответ на ваш вопрос: вставлять вещи по одной, а не сохранять их, а затем сортировать, не должно иметь большого значения в смысле большого количества. Конечно, вы можете иметь дело с постоянными факторами, и они могут быть значительными.
Конечно, если n мало, например 10, все обсуждение глупо.
Это массив или связанный список? Я знаю, что вы сказали «список», но упомянули о двоичном выполнении, что подразумевает массив.