Подтвердить что ты не робот

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

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

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

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)

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

Спасибо!

4b9b3361

Ответ 1

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

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

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

Ответ 2

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

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

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

EDIT: Я предположил, что вставка в середине отсортированного списка после того, как вы нашли точку вставки, будет постоянным (т.е. список ведет себя как связанный список, который представляет собой структуру данных вы использовали бы для такого алгоритма). Это, вероятно, не относится к спискам Python, как указал Свен. Это сделало бы подход "сохранить отсортированный список" O (n ^ 2), т.е. Сортировку вставки.

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

Ответ 3

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

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