Разлика в скоростта между повторение на генератори и списъци

Вашият първи пример е генераторен израз, който обхожда списък. Вашият втори пример е израз на списък, който итерира списък. Наистина, вторият пример е малко по-бърз.

>>> import timeit
>>> timeit("sorted(a for a in l)", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.963912010192871
>>> timeit("sorted([a for a in l])", setup="import random;l = [int(1000*random.random()) for i in xrange(10*6)]")
5.021576881408691

Причината за това несъмнено е, че съставянето на списък се извършва наведнъж, докато итерацията върху генератор изисква извиквания на функции.

Генераторите не трябва да ускоряват малки списъци като този (имате 60 елемента в списъка, това е много малко). Основно е за пестене на памет при създаване на дълги списъци.

Ако погледнете източника за sorted, всяка последователност, която подадете, първо се копира в нов списък.

newlist = PySequence_List(seq);

generator --> list изглежда по-бавно от list --> list.

>>> timeit.timeit('x = list(l)', setup = 'l = xrange(1000)')
16.656711101531982
>>> timeit.timeit('x = list(l)', setup = 'l = range(1000)')
4.525658845901489

Що се отнася до това защо трябва да се направи копие, помислете как работи сортирането. Сортировките не са линейни алгоритми. Ние се движим през данните няколко пъти, понякога преминавайки през данните в двете посоки. Генераторът е предназначен за създаване на последователност, през която итерираме веднъж и само веднъж, от началото до някъде след него. Списък позволява произволен достъп.

От друга страна, създаването на списък от генератор ще означава само един списък в паметта, докато създаването на копие на списък ще означава два списъка в паметта. Добър старомоден компромис пространство-време.

Python използва Timsort, хибрид на сортиране чрез сливане и сортиране чрез вмъкване.

Списъчните изрази, първо, зареждат данни в памет. След това извършване на всякакви операции с получения списък. Нека времето за разпределение е T2 (за втори случай). Изразите на генератора не разпределят време наведнъж, но променят стойността на итератора за време t1[i]. Сумата от всички t1[i] ще бъде T1. T1 ≈ T2.

Но когато извикате sorted(), в първия случай времето T1 се добавя с времето за разпределение на паметта на всяка двойка в сравнение със сортирането (tx1[i]). В резултат T1 се добавя със сумата от всички tx1[i].

Следователно, T2 ‹ T1 + sum(tx1[i])