Окупается ли использование генератора в качестве входных данных для sorted() вместо понимания списка

Возможный дубликат:
sorted() с использованием генератора Выражения вместо списков

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

Вот вопрос, рассмотрим следующий код:

output = SomeExpensiveCallEgDatabase()
results = [result[0] for result in output]
return sorted(results)

Вызов sorted вернет отсортированный список результатов. Было бы лучше или хуже объявить результаты, как показано ниже, а затем вызвать сортировку?

results = (result[0] for result in output)

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


python optimization list-comprehension generator sorted
person Francisco Passos    schedule 03.08.2012    source источник
comment
Я думаю разницы нет.   -  person Denis    schedule 03.08.2012

Ответы (3)


arrow_upward
3
arrow_downward

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

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

Чтобы создать новый список, встроенный метод sorted использует PySequence_List:

PyObject* PySequence_List(PyObject *o) Возвращаемое значение: Новая ссылка. Возвращает объект списка с тем же содержимым, что и произвольная последовательность o. Возвращаемый список гарантированно будет новым.

Плюсы и минусы обоих подходов:

Память:

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

Это делает версию генератора более эффективной с точки зрения памяти.

Скорость:

Здесь побеждает версия со всем списком.

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

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

Так что по скорости выигрывает список.

Ответ на вопрос «что лучше» сводится к наиболее распространенному ответу в любой области техники... это зависит....

person pcalcao    schedule 03.08.2012
comment
Эта ссылка указывает на то, что выражение генератора лучше, поскольку в памяти существует только копия списка, над которым работает sorted. - person ecatmur; 03.08.2012
comment
Вы правы, я отредактировал свой ответ, чтобы уточнить это. Предполагается, что весь генератор проходится до того, как произойдет сортировка, но он все еще имеет преимущества в отношении памяти. - person pcalcao; 03.08.2012

arrow_upward
3
arrow_downward

Нет, вы все еще создаете новый список с sorted()

output = SomeExpensiveCallEgDatabase()
results = [result[0] for result in output]
results.sort()
return results

будет ближе к версии генератора.

Я считаю, что лучше использовать версию генератора, потому что некоторые будущие версии Python могут использовать это для более эффективной работы. Всегда приятно получить ускорение бесплатно.

person John La Rooy    schedule 03.08.2012

arrow_upward
0
arrow_downward

Да, вы правы (хотя я считаю, что процедура сортировки по-прежнему называется tim-sort, в честь дяди тимми ‹подмигивая y’rs›)

person thebjorn    schedule 03.08.2012