摘要:例如,以下對兩個的相應元素求和這個例子很好的解釋了如何構建中所謂的迭代器代數的函數的含義。為簡單起見,假設輸入的長度可被整除。接受兩個參數一個可迭代的正整數最終會在中個元素的所有組合的元組上產生一個迭代器。
前言
大家好,今天想和大家分享一下我的itertools學習體驗及心得,itertools是一個Python的自帶庫,內含多種非常實用的方法,我簡單學習了一下,發現可以大大提升工作效率,在sf社區內沒有發現十分詳細的介紹,因此希望想自己做一個學習總結。也和朋友們一起分享一下心得
首先,有關itertools的詳細介紹,我參考的是Python 3.7官方文檔:itertools — Functions creating iterators for efficient looping,大家感興趣可以去看看,目前還沒有中文版本,十分遺憾,這里不得不吐槽一句,為啥有日語,韓語,中文的版本沒有跟上呢?
書規正傳,itertools 我個人評價是Python3里最酷的東西! 如果你還沒有聽說過它,那么你就錯過了Python 3標準庫的一個最大隱藏寶藏,是的,我很快就拋棄了剛剛分享的collections模塊:Python 進階之路 (七) 隱藏的神奇寶藏:探秘Collections,畢竟男人都是大豬蹄子
網上有很多優秀的資源可用于學習itertools模塊中的功能。但對我而言,官方文檔本身總是一個很好的起點。學會做甜點之前,總是要會最基礎的面包。這篇文章便是基本基于文檔歸納整理而來。
我在學習后的整體感受是,關于itertools只知道它包含的函數是遠遠不夠的。真正的強大之處在于組合這些功能以創建快速,占用內存效率極少,漂亮優雅的代碼。
在這篇很長的文章里,我會全面復盤我的學習歷程,爭取全面復制每一個細節,在開始之前,如果朋友們還不太知道迭代器和生成器是什么,可以參考以下科普掃盲:
菜鳥教程 迭代器生成器
廖雪峰的迭代器講解
廖雪峰的生成器講解
神奇的itertools好啦,坐好扶穩,我們準備上車了,根據官方文檔的定義:
This module implements a number of iterator building blocks inspired by constructs from APL, Haskell, and SML. Each has been recast in a form suitable for Python.
翻譯過來大概就是它是一個實現了許多迭代器構建的模塊,它們受到來自APL,Haskell和SML的構造的啟發......可以提高效率啥的,
這主要意味著itertools中的函數是在迭代器上“操作”以產生更復雜的迭代器。
例如,考慮內置的zip()函數,該函數將任意數量的iterables作為參數,并在其相應元素的元組上返回迭代器:
print(list(zip([1, 2, 3], ["a", "b", "c"]))) Out:[(1, "a"), (2, "b"), (3, "c")]
這里讓我們思考一個問題,這個zip函數到底是如何工作的?
與所有其他list一樣,[1,2,3] 和 ["a","b","c"] 是可迭代的,這意味著它們可以一次返回一個元素。
從技術上講,任何實現:
.__ iter __()
或.__ getitem __()
方法的Python對象都是可迭代的。如果對這方面有疑問,大家可以看前言部分提到的教程哈
其實有關iter()這個內置函數,當在一個list或其他可迭代的對象 x 上調用時,會返回x自己的迭代器對象:
iter([1, 2, 3, 4]) iter((1,2,3,4)) iter({"a":1,"b":2}) Out:
實際上,zip()函數通過在每個參數上調用iter(),然后使用next()推進iter()返回的每個迭代器并將結果聚合為元組來實現。 zip()返回的迭代器遍歷這些元組
而寫到這里不得不回憶一下,之前在 Python 進階之路 (五) map, filter, reduce, zip 一網打盡我給大家介紹的神器map()內置函數,其實某種意義上也是一個迭代器的操作符而已,它以最簡單的形式將單參數函數一次應用于可迭代的sequence的每個元素:
模板: map(func,sequence)
list(map(len, ["xiaobai", "at", "paris"])) Out: [7, 2, 5]
參考map模板,不難發現:map()函數通過在sequence上調用iter(),使用next()推進此迭代器直到迭代器耗盡,并將func 應用于每步中next()返回的值。在上面的例子里,在["xiaobai", "at", "paris"]的每個元素上調用len(),從而返回一個迭代器包含list中每個元素的長度
由于迭代器是可迭代的,因此可以用 zip()和 map()在多個可迭代中的元素組合上生成迭代器。
例如,以下對兩個list的相應元素求和:
a = [1, 2, 3] b = [4, 5, 6] list(map(sum, zip(a,b))) Out: [5, 7, 9]
這個例子很好的解釋了如何構建itertools中所謂的 “迭代器代數” 的函數的含義。我們可以把itertools視為一組構建磚塊,可以組合起來形成專門的“數據管道”,就像這個求和的例子一樣。
其實在Python 3里,如果我們用過了map() 和 zip() ,就已經用過了itertools,因為這兩個函數返回的就是迭代器!
我們使用這種 itertools 里面所謂的 “迭代器代數” 帶來的好處有兩個:
提高內存效率 (lazy evaluation)
提速
可能有朋友對這兩個好處有所疑問,不要著急,我們可以分析一個具體的場景:
現在我們有一個list和正整數n,編寫一個將list 拆分為長度為n的組的函數。為簡單起見,假設輸入list的長度可被n整除。例如,如果輸入= [1,2,3,4,5,6] 和 n = 2,則函數應返回 [(1,2),(3,4),(5,6)]。
我們首先想到的解決方案可能如下:
def naive_grouper(lst, n): num_groups = len(lst) // n return [tuple(lst[i*n:(i+1)*n]) for i in range(num_groups)]
我們進行簡單的測試,結果正確:
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] naive_grouper(nums, 2) Out: [(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)]
但是問題來了,如果我們試圖傳遞一個包含1億個元素的list時會發生什么?我們需要大量內存!即使有足夠的內存,程序也會掛起一段時間,直到最后生成結果
這個時候如果我們使用itertools里面的迭代器就可以大大改善這種情況:
def better_grouper(lst, n): iters = [iter(lst)] * n return zip(*iters)
這個方法中蘊含的信息量有點大,我們現在拆開一個個看,表達式 [iters(lst)] * n 創建了對同一迭代器的n個引用的list:
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] iters = [iter(nums)] * 2 list(id(itr) for itr in iters) # Id 沒有變化,就是創建了n個索引 Out: [1623329389256, 1623329389256]
接下來,zip(* iters)在 iters 中的每個迭代器的對應元素對上返回一個迭代器。當第一個元素1取自“第一個”迭代器時,“第二個”迭代器現在從2開始,因為它只是對“第一個”迭代器的引用,因此向前走了一步。因此,zip()生成的第一個元組是(1,2)。
此時,iters中的所謂 “兩個”迭代器從3開始,所以當zip()從“first”迭代器中拉出3時,它從“second”獲得4以產生元組(3,4)。這個過程一直持續到zip()最終生成(9,10)并且iters中的“兩個”迭代器都用完了:
注意: 這里的"第一個","第二個" ,"兩個"都是指向一個迭代器,因為id沒有任何變化!!
最后我們發現結果是一樣的:
nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] list(better_grouper(nums, 2)) Out: [(1, 2), (3, 4), (5, 6), (7, 8), (9, 10)]
但是,這里我做了測試,發現二者的消耗內存是天壤之別,而且在使用iter+zip()的組合后,執行速度快了500倍以上,大家感興趣可以自己測試,把 nums 改成 xrange(100000000) 即可
現在讓我們回顧一下剛剛寫好的better_grouper(lst, n) 方法,不難發現,這個方法存在一個明顯的缺陷:如果我們傳遞的n不能被lst的長度整除,執行時就會出現明顯的問題:
>>> nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >>> list(better_grouper(nums, 4)) [(1, 2, 3, 4), (5, 6, 7, 8)]
我們發現分組輸出中缺少元素9和10。發生這種情況是因為一旦傳遞給它的最短的迭代次數耗盡,zip()就會停止聚合元素。而我們想要的是不丟失任何元素。因此解決辦法是我們可以使用 itertools.zip_longest() 它可以接受任意數量的 iterables 和 fillvalue 這個關鍵字參數,默認為None。我們先看一個簡單實例
>>> import itertools as it >>> x = [1, 2, 3, 4, 5] >>> y = ["a", "b", "c"] >>> list(zip(x, y)) # zip總是執行完最短迭代次數停止 [(1, "a"), (2, "b"), (3, "c")] >>> list(it.zip_longest(x, y)) [(1, "a"), (2, "b"), (3, "c"), (4, None), (5, None)]
這個例子已經非常清晰的體現了zip()和 zip_longest()的區別,現在我們可以優化 better_grouper 方法了:
import itertools as it def grouper(lst, n, fillvalue=None): iters = [iter(lst)] * n return it.zip_longest(*iters, fillvalue=fillvalue) # 默認就是None
我們再來看優化后的測試:
>>> nums = [1, 2, 3, 4, 5, 6, 7, 8, 9, 10] >>> print(list(grouper(nums, 4))) [(1, 2, 3, 4), (5, 6, 7, 8), (9, 10, None, None)]
已經非常理想了,各位老鐵們可能還沒有意識到,我們剛剛所做的一切就是創建itertools 里面grouper方法的全過程!
現在讓我們看看真正的 官方文檔 里面所寫的grouper方法:
和我們寫的基本一樣,除了可以接受多個iterable 參數,用了*args
最后心滿意足的直接調用一下:
輸出結果如下:
暴力求解(brute force)首先基礎概念掃盲,所謂暴力求解是算法中的一種,簡單來說就是 利用枚舉所有的情況,或者其它大量運算又不用技巧的方式,來求解問題的方法。
我在看過暴力算法的廣義概念后,首先想到的居然是盜墓筆記中的王胖子
如果有看過盜墓筆記朋友,你會發現王胖子其實是一個推崇暴力求解的人,在無數次遇到困境時祭出的”枚舉法“,就是暴力求解,例如我印象最深的是云頂天宮中,一行人被困在全是珠寶的密室中無法逃脫,王胖子通過枚舉排除所有可能性,直接得到”身邊有鬼“ 的最終解。PS: 此處致敬南派三叔,和那些他填不上的坑
扯遠了,回到現實中來,我們經常會碰到如下的經典題目:
你有三張20美元的鈔票,五張10美元的鈔票,兩張5美元的鈔票和五張1美元的鈔票。可以通過多少種方式得到100美元?
為了暴力破解這個問題,我們只要把所有組合的可能性羅列出來,然后找出100美元的組合即可,首先,讓我們創建一個list,包含我們手上所有的美元:
bills = [20, 20, 20, 10, 10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 1]
這里itertools會幫到我們。 itertools.combinations() 接受兩個參數
一個可迭代的input
正整數n
最終會在 input中 n 個元素的所有組合的元組上產生一個迭代器。
import itertools as it bills = [20, 20, 20, 10, 10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 1] result =list(it.combinations(bills, 3)) print(len(result)) # 455種組合 print(result) Out: 455 [(20, 20, 20), (20, 20, 10), (20, 20, 10), ... ]
我僅剩的高中數學知識告訴我其實這個就是一個概率里面的 C 15(下標),3(上標)問題,好了,現在我們擁有了各種組合,那么我們只需要在各種組合里選取總數等于100的,問題就解決了:
makes_100 = [] for n in range(1, len(bills) + 1): for combination in it.combinations(bills, n): if sum(combination) == 100: makes_100.append(combination)
這樣得到的結果是包含重復組合的,我們可以在最后直接用一個set過濾掉重復值,最終得到答案:
import itertools as it bills = [20, 20, 20, 10, 10, 10, 10, 10, 5, 5, 1, 1, 1, 1, 1] makes_100 = [] for n in range(1, len(bills) + 1): for combination in it.combinations(bills, n): if sum(combination) == 100: makes_100.append(combination) print(set(makes_100)) Out:{(20, 20, 10, 10, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 10, 10, 10, 10, 10, 5, 5), (20, 20, 20, 10, 10, 10, 5, 1, 1, 1, 1, 1), (20, 20, 20, 10, 10, 10, 5, 5), (20, 20, 20, 10, 10, 10, 10)}
所以最后我們發現一共有5種方式。 現在讓我們把題目換一種問法,就完全不一樣了:
現在要把100美元的鈔票換成零錢,你可以使用任意數量的50美元,20美元,10美元,5美元和1美元鈔票,有多少種方法?
在這種情況下,我們沒有預先設定的鈔票數量,因此我們需要一種方法來使用任意數量的鈔票生成所有可能的組合。為此,我們需要用到itertools.combinations_with_replacement()函數。
它就像combination()一樣,接受可迭代的輸入input 和正整數n,并從輸入返回有n個元組的迭代器。不同之處在于combination_with_replacement()允許元素在它返回的元組中重復,看一個小栗子:
>>> list(it.combinations_with_replacement([1, 2], 2)) #自己和自己的組合也可以 [(1, 1), (1, 2), (2, 2)]
對比 itertools.combinations():
>>> list(it.combinations([1, 2], 2)) #不允許自己和自己的組合 [(1, 2)]
所以針對新問題,解法如下:
bills = [50, 20, 10, 5, 1] make_100 = [] for n in range(1, 101): for combination in it.combinations_with_replacement(bills, n): if sum(combination) == 100: makes_100.append(combination)
最后的結果我們不需要去重,因為這個方法不會產生重復組合:
>>> len(makes_100) 343
如果你親自運行一下,可能會注意到輸出需要一段時間。那是因為它必須處理96,560,645種組合!這里我們就在執行暴力求解
另一個“暴力” 的itertools函數是permutations(),它接受單個iterable并產生其元素的所有可能的排列(重新排列):
>>> list(it.permutations(["a", "b", "c"])) [("a", "b", "c"), ("a", "c", "b"), ("b", "a", "c"), ("b", "c", "a"), ("c", "a", "b"), ("c", "b", "a")]
任何三個元素的可迭代對象(比如list)將有六個排列,并且較長迭代的對象排列數量增長得非常快。實際上,長度為n的可迭代對象有n!排列:
只有少數輸入產生大量結果的現象稱為組合爆炸,在使用combination(),combinations_with_replacement()和permutations()時我們需要牢記這一點。
說實話,通常最好避免暴力算法,但有時我們可能必須使用(比如算法的正確性至關重要,或者必須考慮每個可能的結果)
小結由于篇幅有限,我先分享到這里,這篇文章我們主要深入理解了以下函數的基本原理:
map()
zip()
itertools.combinations
itertools.combinations_with_replacement
itertools.permutations
在下一篇文章我會先對最后三個進行總結,然后繼續和大家分享itertools里面各種神奇的東西
文章版權歸作者所有,未經允許請勿轉載,若此文章存在違規行為,您可以聯系管理員刪除。
轉載請注明本文地址:http://specialneedsforspecialkids.com/yun/43224.html
前情回顧 大家好,我又回來了。今天我會繼續和大家分享itertools這個神奇的自帶庫,首先,讓我們回顧一下上一期結尾的時候我們講到的3個方法: combinations() combinations_with_replacement() permutations() 讓我們對這3個在排列組合中經常會使用到的函數做個總結 combinations() 基礎概念 模板:combinations...
摘要:將每一行作為返回,其中是每行中的列名。對于每一行,都會生成一個對象,其中包含和列中的值。它返回一個迭代器,是迭代結果都為的情況。深度解析至此全劇終。 簡單實戰 大家好,我又來了,在經過之前兩篇文章的介紹后相信大家對itertools的一些常見的好用的方法有了一個大致的了解,我自己在學完之后仿照別人的例子進行了真實場景下的模擬練習,今天和大家一起分享,有很多部分還可以優化,希望有更好主意...
摘要:與上面的操作類似,可以使用多種運算符和方法來更改集合的內容。通過修改集合元素方法運算符用法通過修改集合和作用是向集合中添加中所有不存在的元素。 Set是什么 大家好,恰逢初五迎財神,先預祝大家新年財源滾滾!!在上一期詳解tuple元組的用法后,今天我們來看Python里面最后一種常見的數據類型:集合(Set) 與dict類似,set也是一組key的集合,但不存儲value。由于key不...
摘要:上個月,學習群里的同學問了個題目,大意可理解為列表降維,例子如下想得到結果原始數據是一個二維列表,目的是獲取該列表中所有元素的具體值。不經意間,函數的注意事項,竟把其它的進階內容都聯系起來了。小小的函數,竟成為學習之路上的一個樞紐。 上個月,學習群里的 S 同學問了個題目,大意可理解為列表降維 ,例子如下: oldlist = [[1, 2, 3], [4, 5]] # 想得到結果:...
閱讀 2372·2021-11-24 10:31
閱讀 3427·2021-11-23 09:51
閱讀 2239·2021-11-15 18:11
閱讀 2387·2021-09-02 15:15
閱讀 2452·2019-08-29 17:02
閱讀 2285·2019-08-29 15:04
閱讀 831·2019-08-29 12:27
閱讀 2853·2019-08-28 18:15