使用生成器表達式排序（）而不是列表

Question

看到這裏的討論後：Python - generate the time difference我很好奇。我最初也認爲生成器比列表更快，但是當涉及到排序時（）我不知道。將生成器表達式發送到sorted（）而不是列表有什麼好處嗎？無論如何，生成器表達式最終會在排序之前進入sorted（）列表中嗎？

編輯：它傷感我只能夠接受一個答案，因爲我覺得很多答覆有助於澄清問題。再次感謝大家。

Answer 1

sorted()所做的第一件事是將數據轉換爲列表。基本上執行的第一行（參數驗證之後）是

newlist = PySequence_List(seq); 

參見the full source code version 2.7和version 3.1.2。

編輯：正如answer by aaronasterling指出，變量newlist是，好了，一個新的名單。如果該參數已經是一個列表，它將被複制。所以一個生成器表達式確實具有使用較少內存的優勢。

Answer 2

沒有辦法在不知道序列的所有元素的情況下對序列進行排序，因此傳遞給sorted()的任何生成器都已耗盡。

Answer 3

我最初還以爲列表 理解比列表

你的意思是不是名單​​還快？你的意思是比明確的for更快嗎？爲此，我會說這取決於：列表理解更像是一個語法糖，但它對於簡單循環來說非常方便。

但是，當涉及到排序（）我不知道 知道。將 生成器表達式發送到sorted（） 而不是列表有什麼好處嗎？

List comprehensions和Generator表達式的主要區別在於Generator表達式避免了一次生成整個列表的開銷。相反，它們會返回一個可以逐個迭代的生成器對象，因此生成器表達式更有可能用於節省內存使用量。

但是你要明白一件事在Python：這很難說，如果一個方式是更快（樂觀），比另一種方式只是看着它，如果你想這樣做，你應該使用timeit爲基準（而且基準測試比在一臺機器上運行一次測試更復雜）。

有關某些優化技術的更多信息，請閱讀this。

Answer 4

Python使用Timsort。 Timsort需要知道前面的元素總數，以計算minrun參數。因此，正如Sven所報道的那樣，當給定一個生成器時，排序的第一件事就是將它變成一個列表。也就是說，可以編寫一個Timsort的增量版本，它可以更慢地消耗發生器中的值 - 在啓動之前，您只需修復minrun，並接受在發生一些不平衡合併的痛苦結束。 Timsort分兩個階段工作。第一個階段包括遍歷整個數組，識別運行並進行插入排序以使數據無序的運行。運行發現和插入排序都是內在遞增的。第二階段涉及排序運行的合併;那會像現在一樣發生。

儘管如此，我不認爲會有很多觀點。也許這會讓內存管理變得更容易，因爲不必從發生器讀取一個不斷增長的數組（因爲我毫無根據地假設當前的實現），您可以將每次運行讀入一個小緩衝區，然後只分配一個final-大小緩衝一次，最後。但是，這將涉及在內存中同時存儲2N個陣列的陣列，而如果陣列增長時陣列增加一倍，則可以使用1.5N陣列來增加陣列。所以，可能不是一個好主意。

Answer 5

這是一個巨大的好處。由於排序不會影響順序傳遞，因此必須複製它。如果它從生成器表達式中創建一個列表，那麼只有一個列表被創建。如果列表理解被傳入，那麼首先，構建它，然後sorted將它的副本進行排序。

這反映在Sven Marnach's answer引述線

newlist = PySequence_List(seq); 

。實質上，這將無條件地複製傳遞給它的任何序列。

Answer 6

，看看這是更快，最簡單的方法是使用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()將傳入值轉換爲列表時，對於已經是列表的某個事物而不是生成器，它可以更快地執行此操作。 The source code seems to confirm this（但是這是通過閱讀評論而不是完全理解正在發生的一切）。

Answer 7

如果性能很重要，爲什麼不處理由生成器生成的數據，並將迭代的結果應用於排序？當然，只有在迭代之間不存在因果條件的情況下（即，對於排序迭代＃[i + 1]，不需要排序迭代＃[i]的數據），這可以被使用。 我在這種情況下要說的是，對發生器產生的一組可能較大的結構進行排序可能會給處理所有元素後可能發生的排序增加許多不必要的複雜性。

Answer 8

我應該只是增加戴夫·韋伯的時間回答[我把什麼可能是一個匿名編輯]，當你訪問一個優化的發電機直接，它可能快得多;大部分開銷可能是代碼創建自己的列表或生成器：

>>> 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