Sorted() с использованием выражений генератора, а не списков

Ответ 1

Первое, что делает sorted(), - это преобразование данных в список. В основном первая строка (после проверки аргумента) реализации

newlist = PySequence_List(seq);

См. также полный исходный код версии 2.7 и версия 3.1 0,2.

Изменить. Как указано в ответе aaronasterling, переменная newlist - это нужный список. Если параметр уже является списком, он копируется. Таким образом, выражение генератора действительно имеет преимущество использования меньше памяти.

Ответ 2

Самый простой способ увидеть, что быстрее, это использовать timeit, и он говорит мне, что быстрее передавать список, а не генератор:

>>> import random
>>> randomlist = range(1000)
>>> random.shuffle(randomlist)
>>> import timeit
>>> timeit.timeit("sorted(x for x in randomlist)",setup = "from __main__ import randomlist",number = 10000)
4.944492386602178
>>> timeit.timeit("sorted([x for x in randomlist])",setup = "from __main__ import randomlist",number = 10000)
4.635165083830486

и

>>> timeit.timeit("sorted(x for x in xrange(1000,1,-1))",number = 10000)
1.411807087213674
>>> timeit.timeit("sorted([x for x in xrange(1000,1,-1)])",number = 10000)
1.0734657617099401

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

Ответ 3

Там огромное преимущество. Поскольку сортировка не влияет на пройденную последовательность, она должна сделать ее копию. Если он создает список из выражения генератора, создается только один список. Если во внимание передается представление списка, то сначала создается, а затем sorted делает его копию для сортировки.

Это отражается в строке

newlist = PySequence_List(seq);

цитируется в ответ Свена Марнаха. По сути, это безоговорочно сделает копию любой последовательности, переданной ему.

Ответ 4

Нет способа сортировать последовательность, не зная всех элементов последовательности, поэтому любой генератор, прошедший через sorted(), исчерпан.

Ответ 5

Python использует Timsort. Timsort должен знать общее количество элементов спереди, чтобы вычислить параметр minrun. Таким образом, как сообщает Свен, первое, что сортируется при задании генератора, - это превратить его в список.

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

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

Ответ 6

Я также изначально считал, что список понимание быстрее, чем список

Что вы имеете в виду быстрее, чем список? Вы имеете в виду быстрее, чем явный for? Для этого я скажу, что это зависит: понимание списка больше похоже на синтаксический сахар, но это очень удобно, когда дело доходит до простого цикла.

но когда дело доходит до sorted(), я не знать. Есть ли какая-либо польза для отправки выражение генератора для сортировки() а не список?

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

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

Прочтите этот для получения дополнительной информации о некоторых методах оптимизации.

Ответ 7

Я должен просто добавить к Dave Webb временному ответу [я ввел то, что может быть анонимным правлением], что при доступе к оптимизированному генератору напрямую он может быть намного быстрее; большая часть служебных данных может быть созданием кода собственного списка или генератора:

>>> timeit.timeit("sorted(xrange(1000, 1, -1))", number=10000)
0.34192609786987305
>>> timeit.timeit("sorted(range(1000, 1, -1))", number=10000)
0.4096639156341553
>>> timeit.timeit("sorted([el for el in xrange(1000, 1, -1)])", number=10000)
0.6886589527130127
>>> timeit.timeit("sorted(el for el in xrange(1000, 1, -1))", number=10000)
0.9492318630218506

Ответ 8

Если важна производительность, почему бы не обрабатывать данные, как это дает генератор, и применить порядок над результатами итераций? Конечно, это можно использовать только в том случае, если нет причинно-обусловленной кондиционирования между итерациями (т.е. Данные отсортированной итерации # [i] не нужны, чтобы делать какие-либо вычисления для отсортированной итерации # [i + 1]). То, что я пытаюсь сказать в этом случае, состоит в том, что сортировка набора потенциально больших структур, создаваемых генератором, может добавить много ненужной сложности к упорядочению, которое может происходить позади обработки всех элементов.