Могу ли я создать список и отсортировать его одновременно?

Question

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

Итак, на данный момент я в основном получил это:

my_list = []

for item in "query for stuff":
    my_list.append("query for %s data" % item)

my_list.sort()

do_stuff(my_list)

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

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

for item in "query for stuff":
    my_list.append_sorted(item)

Стоит ли пытаться делать это так, или я должен просто придерживаться построения списка, а затем сортировать его?

Спасибо!

Answer 1

Короткий ответ: оно того не стоит.

Посмотрите на сортировку вставок . Время работы в худшем случае составляет O(n^2) (среднее значение также квадратично). С другой стороны, сортировка Python (также известная как Timsort ) в худшем случае займет O(n log n).

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

Answer 2

Два подхода асимптотически эквивалентны.

Сортировка - O (n lg n) (Python использует Timsort по умолчанию, за исключением очень маленьких массивов), а вставка в отсортированный список - O (lg n) (с использованием бинарного поиска), что вы должны сделать n раз.

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

РЕДАКТИРОВАТЬ: Я предполагал, что вставка в середине отсортированного списка после того, как вы нашли точку вставки, будет постоянным временем (то есть список ведет себя как связанный список, который структура данных, которую вы бы использовали для такого алгоритма). Это, вероятно, не относится к спискам Python, как указал Свен. Это сделало бы подход «держать список отсортированным» O (n ^ 2), то есть сортировка вставкой.

Я говорю «вероятно», потому что некоторые реализации списка переключаются с массива на связанный список по мере роста списка, наиболее ярким примером является CFArray / NSArray в CoreFoundation / Cocoa. Это может или не может быть в случае с Python.

Answer 3

Посмотрите на модуль bisect. Это дает вам различные инструменты для поддержания порядка списка. В вашем случае вы, вероятно, хотите использовать bisect.insort.

for item in query_for_stuff():
    bisect.insort( my_list, "query for %s data" % item )