Чтение потоковых данных в отсортированный список

Question

Мы знаем, что в общем случае «более умные» сортировки по произвольным данным выполняются в худшем случае со сложностью O (N * log (N)).

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

Сбор и сортировка были бы O (N + N * log (N)) = O (N * log (N)).Однако, если мы сортируем его по мере поступления, это O (N * K), где K = время, чтобы найти правильный индекс + время для вставки элемента.Это усложняет ситуацию, так как значение K теперь зависит от нашего выбора структуры данных.Массив лучше в поиске индекса, но тратит время на вставку элемента.Связанный список может быть вставлен легче, но не может выполнить бинарный поиск для поиска индекса.

Есть ли полное обсуждение этого вопроса?Когда мы должны использовать тот или иной метод?Может ли быть желательной промежуточная стратегия сортировки время от времени?

Answer 1

Сбалансированная сортировка деревьев имеет сложность O(N log N) и поддерживает список в отсортированном порядке при добавлении элементов.

Answer 2

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

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

Answer 3

Абсолютно нет!

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

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

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

Answer 4

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