Chapter 8 高級迭代器 · Dive Into Python3

# Chapter 8 高級迭代器 > " Great fleas have little fleas upon their backs to bite ’em, > And little fleas have lesser fleas, and so ad infinitum. " > — Augustus De Morgan ## 深入 H`AWAII + IDAHO + IOWA + OHIO == STATES`. 或者，換個說法, `510199 + 98153 + 9301 + 3593 == 621246`. 我在說是方言嗎？不，這只是一個謎題。讓我來給你解釋一下。 ``` HAWAII + IDAHO + IOWA + OHIO == STATES 510199 + 98153 + 9301 + 3593 == 621246 H = 5 A = 1 W = 0 I = 9 D = 8 O = 3 S = 6 T = 2 E = 4 ``` 像這樣的謎題被稱為_cryptarithms_ 或者 _字母算術(alphametics)_。字母可以拼出實際的單詞，而如果你把每一個字母都用`0–9`中的某一個數字代替后, 也同樣可以#8220;拼出” 一個算術等式。關鍵的地方是找出每個字母都映射到了哪個數字。每個字母所有出現的地方都必須映射到同一個數字，數字不能重復, 并且“單詞”不能以0開始。最著名的字母算術謎題是`SEND + MORE = MONEY`。在這一章中，我們將深入一個最初由Raymond Hettinger編寫的難以置信的Python 程序。這個程序_只用14行代碼_來解決字母算術謎題。 [[下載 `alphametics.py`](examples/alphametics.py)] ``` import re import itertools def solve(puzzle): words = re.findall('[A-Z]+', puzzle.upper()) unique_characters = set(''.join(words)) assert len(unique_characters) <= 10, 'Too many letters' first_letters = {word[0] for word in words} n = len(first_letters) sorted_characters = ''.join(first_letters) + \ ''.join(unique_characters - first_letters) characters = tuple(ord(c) for c in sorted_characters) digits = tuple(ord(c) for c in '0123456789') zero = digits[0] for guess in itertools.permutations(digits, len(characters)): if zero not in guess[:n]: equation = puzzle.translate(dict(zip(characters, guess))) if eval(equation): return equation if __name__ == '__main__': import sys for puzzle in sys.argv[1:]: print(puzzle) solution = solve(puzzle) if solution: print(solution) ``` 你可以從命令行運行這個程序。在Linux上, 運行情況看起來是這樣的。(取決于你機器的速度，計算可能要花一些時間，而且不會有進度條。耐心等待就好了。) ``` you@localhost:~/diveintopython3/examples$ python3 alphametics.py "HAWAII + IDAHO + IOWA + OHIO == STATES" HAWAII + IDAHO + IOWA + OHIO = STATES 510199 + 98153 + 9301 + 3593 == 621246 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "I + LOVE + YOU == DORA" I + LOVE + YOU == DORA 1 + 2784 + 975 == 3760 you@localhost:~/diveintopython3/examples$ python3 alphametics.py "SEND + MORE == MONEY" SEND + MORE == MONEY 9567 + 1085 == 10652 ``` ## 找到一個模式所有出現的地方字母算術謎題解決者做的第一件事是找到謎題中所有的字母(A–Z)。 ``` >>> import re ['16', '2', '4', '8'] ['SEND', 'MORE', 'MONEY'] ``` 1. `re` 模塊是[正則表達式](regular-expressions.html)的Python實現。它有一個漂亮的函數`findall()`，接受一個正則表達式和一個字符串作為參數，然后找出字符串中出現該模式的所有地方。在這個例子里，模式匹配的是數字序列。`findall()`函數返回所有匹配該模式的子字符串的列表。 2. 這里正則表達式匹配的是字母序列。再一次，返回值是一個列表，其中的每一個元素是匹配該正則表達式的字符串。這是另外一個稍微復雜一點的例子。 ``` >>> re.findall(' s.*? s', "The sixth sick sheikh's sixth sheep's sick.") [' sixth s', " sheikh's s", " sheep's s"] ``` 這是英語中[最難的繞口令](http://en.wikipedia.org/wiki/Tongue-twister)。很驚奇？這個正則表達式尋找一個空格，一個 `s`, 然后是最短的任何字符構成的序列(`.*?`), 然后是一個空格, 然后是另一個`s`。在輸入字符串中，我看見了五個匹配: 1. `The sixth sick sheikh's sixth sheep's sick.` 2. `The sixth sick sheikh's sixth sheep's sick.` 3. `The sixth sick sheikh's sixth sheep's sick.` 4. `The sixth sick sheikh's sixth sheep's sick.` 5. `The sixth sick sheikh's sixth sheep's sick.` 但是`re.findall()`函數值只返回了3個匹配。準確的說，它返回了第一，第三和第五個。為什么呢？因為_它不會返回重疊的匹配_。第一個匹配和第二個匹配是重疊的，所以第一個被返回了，第二個被跳過了。然后第三個和第四個重疊，所以第三個被返回了，第四個被跳過了。最后，第五個被返回了。三個匹配，不是五個。這和字母算術解決者沒有任何關系；我只是覺得這很有趣。 ## 在序列中尋找不同的元素 [Sets](native-datatypes.html#sets) 使得在序列中查找不同的元素變得很簡單。 ``` >>> a_list = ['The', 'sixth', 'sick', "sheik's", 'sixth', "sheep's", 'sick'] {'sixth', 'The', "sheep's", 'sick', "sheik's"} >>> a_string = 'EAST IS EAST' {'A', ' ', 'E', 'I', 'S', 'T'} >>> words = ['SEND', 'MORE', 'MONEY'] 'SENDMOREMONEY' {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'} ``` 1. 給出一個有若干字符串組成的列表，`set()`函數返回列表中不同的字符串組成的集合。把它想象成一個`for`循環可以幫助理解。從列表出拿出第一個元素，放到集合。第二個，第三個，第四個。第五個，等等, 它已經在集合里面了，因為Python 集合不允許重復，所以它只被列出了一次。第六個。第七個又是一個重復的，所以它只被列出了一次。原來的列表甚至不需要事先排好序。 2. 同樣的技術也適用于字符串，因為一個字符串就是一個字符序列。 3. 給出一個字符串列表, `''.join(`a_list`)`將所有的字符串拼接成一個。 4. 所以，給出一個字符串列表，這行代碼返回這些字符串中出現過的不重復的字符。字母算術解決者通過這個技術來建立謎題中出現的不同字符的集合。 ``` unique_characters = set(''.join(words)) ``` 這個列表在接下來迭代可能的解法的時候將被用來將數字分配給字符。 ## 作出斷言和很多編程語言一樣，Python 有一個`assert`語句。這是它的用法。 ``` Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError Traceback (most recent call last): File "<stdin>", line 1, in <module> AssertionError: Only for very large values of 2 ``` 1. `assert` 語句后面跟任何合法的Python 表達式。在這個例子里, 表達式 `1 + 1 == 2` 的求值結果為 `True`, 所以 `assert` 語句沒有做任何事情。 2. 然而, 如果Python 表達式求值結果為 `False`, `assert` 語句會拋出一個 `AssertionError`. 3. 你可以提供一個人類可讀的消息，`AssertionError`異常被拋出的時候它可以被用于打印輸出。因此, 這行代碼: ``` assert len(unique_characters) <= 10, 'Too many letters' ``` …等價于: ``` if len(unique_characters) > 10: raise AssertionError('Too many letters') ``` 字母算術謎題使用這個`assert` 語句來排除謎題包含多于10個的不同的字母的情況。因為每個不同的字母對應一個不同的數字，而數子只有10個,含有多于10個的不同的字母的謎題是不可能有解的。 ## 生成器表達式生成表達式類似[生成器函數](generators.html)，只不過它不是函數。 ``` >>> unique_characters = {'E', 'D', 'M', 'O', 'N', 'S', 'R', 'Y'} <generator object <genexpr> at 0x00BADC10> 69 >>> next(gen) 68 (69, 68, 77, 79, 78, 83, 82, 89) ``` 1. 生成器表達式類似一個yield值的匿名函數。表達式本身看起來像[列表解析](comprehensions.html#listcomprehension), 但不是用方括號而是用圓括號包圍起來。 2. 生成器表達式返回迭代器。 3. 調用 `next(`gen`)` 返回迭代器的下一個值。 4. 如果你愿意，你可以將生成器表達式傳給`tuple()`, `list()`, 或者 `set()`來迭代所有的值并且返回元組，列表或者集合。在這種情況下，你不需要一對額外的括號?—?將生成器表達式`ord(c) for c in unique_characters` 傳給 `tuple()` 函數就可以了, Python 會推斷出它是一個生成器表達式。 > ?使用生成器表達式取代列表解析可以同時節省CPU 和內存(RAM)。如果你構造一個列表的目的僅僅是傳遞給別的函數，(_比如_ 傳遞給`tuple()` 或者 `set()`), 用生成器表達式替代吧! 這里是到達同樣目的的另一個方法, 使用[生成器函數](generators.html): ``` def ord_map(a_string): for c in a_string: yield ord(c) gen = ord_map(unique_characters) ``` 生成器表達式功能相同但更緊湊。 ## 計算排列… 懶惰的方法! 首先, 排列到底是個什么東西? 排列是一個數學概念。(取決于你在處理哪種數學，排列有好幾個定義。在這里我們說的是組合數學, 如果你完全不知道組合數學是什么也不用擔心。同往常一樣, [維基百科是你的朋友](http://en.wikipedia.org/wiki/Permutation)。) 想法是這樣的，你有某物件(可以是數字，可以是字母，也可以是跳舞的熊)的一個列表，接著找出將它們拆開然后組合成小一點的列表的所有可能。所有的小列表的大小必須一致。最小是1，最大是元素的總數目。哦，也不能有重復。數學家說“讓我們找出3個元素取2個的排列,” 意思是你有一個3個元素的序列，然后你找出所有可能的有序對。 ``` (1, 2) >>> next(perms) (1, 3) >>> next(perms) >>> next(perms) (2, 3) >>> next(perms) (3, 1) >>> next(perms) (3, 2) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration ``` 1. `itertools`模塊里有各種各樣的有趣的東西，包括`permutations()`函數，它把查找排列的所有辛苦的工作的做了。 2. `permutations()` 函數接受一個序列(這里是3個數字組成的列表) 和一個表示你要的排列的元素的數目的數字。函數返回迭代器，你可以在`for` 循環或其他老地方使用它。這里我遍歷迭代器來顯示所有的值。 3. `[1, 2, 3]`取2個的第一個排列是`(1, 2)`。 4. 記住排列是有序的: `(2, 1)` 和 `(1, 2)`是不同的。 5. 這就是了。這些就是`[1, 2, 3]`取兩個的所有排列。像`(1, 1)` 或者 `(2, 2)`這樣的元素對沒有出現，因為它們包含重復導致它們不是合法的排列。當沒有更多排列的時候，迭代器拋出一個`StopIteration`異常。 `itertools`模塊有各種各樣的有趣的東西。 `permutations()`函數并不一定要接受列表。它接受任何序列?—?甚至是字符串。 ``` >>> import itertools >>> next(perms) >>> next(perms) ('A', 'C', 'B') >>> next(perms) ('B', 'A', 'C') >>> next(perms) ('B', 'C', 'A') >>> next(perms) ('C', 'A', 'B') >>> next(perms) ('C', 'B', 'A') >>> next(perms) Traceback (most recent call last): File "<stdin>", line 1, in <module> StopIteration [('A', 'B', 'C'), ('A', 'C', 'B'), ('B', 'A', 'C'), ('B', 'C', 'A'), ('C', 'A', 'B'), ('C', 'B', 'A')] ``` 1. 字符串就是一個字符序列。對于查找排列來說，字符串`'ABC'`和列表 `['A', 'B', 'C']`是等價的。 2. `['A', 'B', 'C']`取3個的第一個排列是`('A', 'B', 'C')`。還有5個其他的排列?—?同樣的3個字符，不同的順序。 3. 由于`permutations()`函數總是返回迭代器，一個簡單的調試排列的方法是將這個迭代器傳給內建的`list()`函數來立刻看見所有的排列。 ## `itertools`模塊中的其它有趣的東西 ``` >>> import itertools [('A', '1'), ('A', '2'), ('A', '3'), ('B', '1'), ('B', '2'), ('B', '3'), ('C', '1'), ('C', '2'), ('C', '3')] [('A', 'B'), ('A', 'C'), ('B', 'C')] ``` 1. `itertools.product()`函數返回包含兩個序列的笛卡爾乘積的迭代器。 2. `itertools.combinations()`函數返回包含給定序列的給定長度的所有組合的迭代器。這和`itertools.permutations()`函數很類似，除了不包含因為只有順序不同而重復的情況。所以`itertools.permutations('ABC', 2)`同時返回`('A', 'B')` and `('B', 'A')` (同其它的排列一起), `itertools.combinations('ABC', 2)` 不會返回`('B', 'A')` ，因為它和`('A', 'B')`是重復的，只是順序不同而已。 [[下載 `favorite-people.txt`](examples/favorite-people.txt)] ``` >>> names ['Dora\n', 'Ethan\n', 'Wesley\n', 'John\n', 'Anne\n', 'Mike\n', 'Chris\n', 'Sarah\n', 'Alex\n', 'Lizzie\n'] >>> names ['Dora', 'Ethan', 'Wesley', 'John', 'Anne', 'Mike', 'Chris', 'Sarah', 'Alex', 'Lizzie'] >>> names ['Alex', 'Anne', 'Chris', 'Dora', 'Ethan', 'John', 'Lizzie', 'Mike', 'Sarah', 'Wesley'] >>> names ['Alex', 'Anne', 'Dora', 'John', 'Mike', 'Chris', 'Ethan', 'Sarah', 'Lizzie', 'Wesley'] ``` 1. 這個表達式將文本內容以一行一行組成的列表的形式返回。 2. 不幸的是，(對于這個例子來說), `list(open(`filename`))` 表達式返回的每一行的末尾都包含回車。這個列表解析使用`rstrip()` 字符串方法移除每一行尾部的空白。(字符串也有一個`lstrip()`方法移除頭部的空白，以及`strip()`方法頭尾都移除。) 3. `sorted()` 函數接受一個列表并將它排序后返回。默認情況下，它按字母序排序。 4. 然而，`sorted()`函數也接受一個函數作為`key` 參數, 并且使用key來排序。在這個例子里，排序函數是`len()`,所以它按`len(`each item`)`來排序。短的名字排在前面，然后是稍長，接著是更長的。這和`itertools`模塊有什么關系? 很高興你問了這個問題。 ``` …continuing from the previous interactive shell… >>> import itertools >>> groups <itertools.groupby object at 0x00BB20C0> >>> list(groups) [(4, <itertools._grouper object at 0x00BA8BF0>), (5, <itertools._grouper object at 0x00BB4050>), (6, <itertools._grouper object at 0x00BB4030>)] ... print('Names with {0:d} letters:'.format(name_length)) ... for name in name_iter: ... print(name) ... Names with 4 letters: Alex Anne Dora John Mike Names with 5 letters: Chris Ethan Sarah Names with 6 letters: Lizzie Wesley ``` 1. `itertools.groupby()`函數接受一個序列和一個key 函數, 并且返回一個生成二元組的迭代器。每一個二元組包含`key_function(`each item`)`的結果和另一個包含著所有共享這個key結果的元素的迭代器。 2. 調用`list()` 函數會“耗盡”這個迭代器, _也就是說_ 你生成了迭代器中所有元素才創造了這個列表。迭代器沒有“重置”按鈕。你一旦耗盡了它，你沒法重新開始。如果你想要再循環一次(例如, 在接下去的`for`循環里面), 你得調用`itertools.groupby()`來創建一個新的迭代器。 3. 在這個例子里，給出一個_已經按長度排序_的名字列表, `itertools.groupby(names, len)`將會將所有的4個字母的名字放在一個迭代器里面，所有的5個字母的名字放在另一個迭代器里，以此類推。`groupby()`函數是完全通用的; 它可以將字符串按首字母，將數字按因子數目, 或者任何你能想到的key函數進行分組。 > ?`itertools.groupby()`只有當輸入序列已經按分組函數排過序才能正常工作。在上面的例子里面，你用`len()` 函數分組了名字列表。這能工作是因為輸入列表已經按長度排過序了。 Are you watching closely? ``` >>> list(range(0, 3)) [0, 1, 2] >>> list(range(10, 13)) [10, 11, 12] [0, 1, 2, 10, 11, 12] [(0, 10), (1, 11), (2, 12)] [(0, 10), (1, 11), (2, 12)] [(0, 10), (1, 11), (2, 12), (None, 13)] ``` 1. `itertools.chain()`函數接受兩個迭代器，返回一個迭代器，它包含第一個迭代器的所有內容，以及跟在后面的來自第二個迭代器的所有內容。(實際上，它接受任何數目的迭代器，并把它們按傳入順序串在一起。) 2. `zip()`函數的作用不是很常見，結果它卻非常有用: 它接受任何數目的序列然后返回一個迭代器，其第一個元素是每個序列的第一個元素組成的元組，然后是每個序列的第二個元素（組成的元組），以此類推。 3. `zip()` 在到達最短的序列結尾的時候停止。`range(10, 14)` 有四個元素(10, 11, 12, 和 13), 但是 `range(0, 3)`只有3個, 所以 `zip()`函數返回包含3個元素的迭代器。 4. 相反，`itertools.zip_longest()`函數在到達_最長的_序列的結尾的時候才停止, 對短序列結尾之后的元素填入`None`值. 好吧，這些都很有趣，但是和字母算術謎題解決者有什么聯系呢? 請看下面: ``` >>> characters = ('S', 'M', 'E', 'D', 'O', 'N', 'R', 'Y') >>> guess = ('1', '2', '0', '3', '4', '5', '6', '7') (('S', '1'), ('M', '2'), ('E', '0'), ('D', '3'), ('O', '4'), ('N', '5'), ('R', '6'), ('Y', '7')) {'E': '0', 'D': '3', 'M': '2', 'O': '4', 'N': '5', 'S': '1', 'R': '6', 'Y': '7'} ``` 1. 給出一個字母列表和一個數字列表(兩者的元素的形式都是1個字符的字符串), `zip`函數按順序創建一組組字母，數字對。 2. 為什么這很酷? 因為這個數據結構正好可以用來傳遞給`dict()`函數來創建以字母為鍵，對應數字為值的字典。(這不是實現這個目的唯一方法。你當然可以使用[字典解析](comprehensions.html#dictionarycomprehension)來直接創建字典。) 盡管字典的打印形式以另一個順序列出了這些鍵值對(字典本身沒有#8220;順序” ), 但是你可以看見每一個字母都按`characters` 和 `guess`序列的原始順序對應到了相應的數字。算術謎題解決者使用這個技術對每一個可能的解法創建一個將謎題中的字母映射到解法中的數字的字典。 ``` characters = tuple(ord(c) for c in sorted_characters) digits = tuple(ord(c) for c in '0123456789') ... for guess in itertools.permutations(digits, len(characters)): ... equation = puzzle.translate(dict(zip(characters, guess))) ``` 但是`translate()`方法是什么呢? 啊哈, 我們現在到了_真正_有趣的部分了。 ## 一種新的操作字符串的方法 Python 字符串有很多方法。我們在[字符串章節](strings.html)中學習了其中一些: `lower()`, `count()`, 和 `format()`。現在我要給你介紹一個強大但鮮為人知的操作字符串的技術: `translate()` 方法。 ``` {65: 79} 'MORK' ``` 1. 字符串翻譯從一個轉換表開始, 轉換表就是一個將一個字符映射到另一個字符的字典。實際上，“字符” 是不正確的?—?轉換表實際上是將一個 _字節（byte)_映射到另一個。 2. 記住，Python 3 中的字節是整形數。`ord()` 函數返回字符的ASCII碼。在這個例子中，字符是A–Z, 所以返回的是從65 到 90的字節。 3. 一個字符串的`translate()`方法接收一個轉換表，并用它來轉換該字符串。換句話說，它將出現在轉換表的鍵中的字節替換為該鍵對應的值。在這個例子里，將`MARK` “翻譯為” `MORK`. 現在你開始進入_真正_有趣的部分了。這和解決字母算術謎題有什么關系呢？實際上，關系大著呢。 ``` >>> characters (83, 77, 69, 68, 79, 78, 82, 89) >>> guess (57, 49, 53, 55, 48, 54, 56, 50) >>> translation_table {68: 55, 69: 53, 77: 49, 78: 54, 79: 48, 82: 56, 83: 57, 89: 50} '9567 + 1085 == 10652' ``` 1. 使用[生成器表達式](#generator-expressions), 我們快速的計算出字符串中每個字符的字節值。`characters`是`alphametics.solve()`函數中的`sorted_characters`的示例值 . 2. 使用另一個生成器表達式，我們快速的計算出字符串中每個數字的字節值。計算結果`guess`, 正好是[`alphametics.solve()`函數中的`itertools.permutations()`函數](#guess)返回值的格式。 3. 通過將[`characters` 和 `guess`zipping 出來的元素對序列](#dict-zip)構造出的字典來作為轉換表。這正是`alphametics.solve()` 在`for` 循環里面干的事情。 4. 最后我們將轉換表傳遞給原始字符串的`translate()`方法。這會將字符串中的每個字母轉化成相應的數字(基于`characters`中字母和`guess`中的數字)。結果是一個字符串形式的合法的Python表達式。這相當令人難忘。但你能對正巧是一個合法Python 表達式的字符串干什么呢？ ## 將任何字符串作為Python表達式求值這是謎題的最后一部分(或者說, 謎題解決者的最后一部分)。經過華麗的字符串操作，我們得到了類似`'9567 + 1085 == 10652'`這樣的一個字符串。但那是一個字符串，字符串有什么好的？輸入`eval()`, Python 通用求值工具。 ``` >>> eval('1 + 1 == 2') True >>> eval('1 + 1 == 3') False >>> eval('9567 + 1085 == 10652') True ``` 但是等一下，不止這些! `eval()` 并不限于布爾表達式。它能處理_任何_ Python 表達式并且返回_任何_數據類型。 ``` >>> eval('"A" + "B"') 'AB' >>> eval('"MARK".translate({65: 79})') 'MORK' >>> eval('"AAAAA".count("A")') 5 >>> eval('["*"] * 5') ['*', '*', '*', '*', '*'] ``` 等一下，還沒完呢! ``` >>> x = 5 25 25 >>> import math 2.2360679774997898 ``` 1. `eval()`接受的表達式可以引用在`eval()`之外定義的全局變量。如果(`eval()`)在函數內被調用, 它也可以引用局部變量。 2. 以及函數。 3. 以及模塊。喂，等一下… ``` >>> import subprocess 'Desktop Library Pictures \ Documents Movies Public \ Music Sites' ``` 1. `subprocess` 模塊允許你執行任何shell命令并以字符串形式獲得輸出。 2. 執行任意的shell命令可能會導致永久的（不好的）后果。更壞的是，由于存在全局函數`__import__()`，它接收字符串形式的模塊名，導入模塊，并返回模塊的引用。和`eval()`的能力結合起來，你可以構造一個單獨的表達式來刪除你所有的文件: 1. 現在想象一下`'rm -rf ~'`的輸出。實際上它不會有任何輸出，但是你也不會有任何文件還留著。 eval() 是邪惡的好吧, 邪惡部分是對來自非信任源的表達式進行求值。你應該只在信任的輸入上使用`eval()`。當然，關鍵的部分是確定什么是“可信任的”。但有一點我敢肯定: 你**不**應該將這個字母算術表達式放到網上最為一個小的web服務。不要錯誤的認為，“Gosh, 這個函數在求值以前做了那么多的字符串操作。_我想不出_ 誰能利用這個漏洞。” **會**有人找出穿過這些字符串操作把危險的可執行代碼放進來的方法的。([更奇怪的事情都發生過。](http://www.securityfocus.com/blogs/746)), 然后你就得和你的服務器說再見了。但是肯定有_某種_辦法可以安全的求值表達式吧？將`eval()`放到一個不能訪問和傷害外部世界的沙盒里面。嗯，對也不對。 ``` >>> x = 5 Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<string>", line 1, in <module> NameError: name 'x' is not defined >>> import math Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<string>", line 1, in <module> NameError: name 'math' is not defined ``` 1. 傳給`eval()`函數的第二和第三個函數擔當了求值表達式是的全局和局部名字空間的角色。在這個例子里，它們都是空的，意味著當字符串`"x * 5"`被求值的時候, 在全局和本地的名字空間都沒有變量`x`, 所以 `eval()`拋出了一個異常。 2. 你可以通過一個個列出的方式選擇性在全局名字空間里面包含一些值。這些?—?并且這有這些?—?變量在求值的時候可用。 3. 即使你剛剛導入了`math`模塊, 你沒有在傳給`eval()`函數的名字空間里包含它，所以求值失敗了。哎呀，這很簡單。讓我來做一個字母算術謎題的Web服務吧！ ``` 25 2.2360679774997898 ``` 1. 即使你傳入空的字典作為全局和局部名字空間，所有的Python 內建函數在求值時還是可用的。所以`pow(5, 2)`可以工作, 因為 `5` 和 `2`是字面量，而`pow()`是內建函數。 2. 很不幸 (如果你不明白為什么不幸，繼續讀。), `__import__()` 也是一個內建函數，所以它也能工作。是的，這意味著即使你在調用`eval()`的時候顯式的將全局和局部名字空間設置為空字典，你仍然可以做壞事。 ``` >>> eval("__import__('subprocess').getoutput('rm /some/random/file')", {}, {}) ``` 哎呀. 幸虧我沒有做那個字母算術web服務。存在_任何_安全的使用 `eval()`的方法嗎? 嗯, 有也沒有。 ``` >>> eval("__import__('math').sqrt(5)", Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<string>", line 1, in <module> NameError: name '__import__' is not defined >>> eval("__import__('subprocess').getoutput('rm -rf /')", Traceback (most recent call last): File "<stdin>", line 1, in <module> File "<string>", line 1, in <module> NameError: name '__import__' is not defined ``` 1. 為了安全的求值不受信任的表達式, 你需要定義一個將`"__builtins__"` 映射為 `None`(Python 的空值)的全局名字空間字典. 在內部, “內建” 函數包含在一個叫做`"__builtins__"`的偽模塊內。這個偽模塊(_即_ 內建函數的集合) 在沒有被你顯式的覆蓋的情況下對被求值的表達式是總是可用的。 2. 請確保你覆蓋的是`__builtins__`。不是`__builtin__`, `__built-ins__`, 或者其它某個變量，否則程序還是可以運行但是會有巨大的風險。那么`eval()`現在安全了? 嗯，是也不是。 ``` >>> eval("2 ** 2147483647", ``` 1. 即使不能訪問到`__builtins__`, 你還是可以開啟一個拒絕服務攻擊。例如, 試圖求`2` 的 `2147483647`次方會導致你的服務器的 CPU 利用率到達100% 一段時間。(如果你在交互式shell中試驗這個, 請多按幾次 `Ctrl-C`來跳出來。) 技術上講，這個表達式最終_將會_返回一個值, 但是在這段時間里你的服務器將啥也干不了。最后, Python 表達式的求值_是_可能達到某種意義的“安全”的, 但結果是在現實生活中沒什么用。如果你只是玩玩沒有問題，如果你只給它傳遞安全的輸入也沒有問題。但是其它的情況完全是自找麻煩。 ## 把所有東西放在一起總的來說: 這個程序通過暴力解決字母算術謎題， _也就是_通過窮舉所有可能的解法。為了達到目的，它 1. 通過`re.findall()`函數[找到謎題中的所有字母](#re-findall) 2. 使用集合和`set()`函數[找到謎題出現的所有_不同_的字母](#unique-items) 3. 通過`assert`語句[檢查是否有超過10個的不同的字母](#assert) (意味著謎題無解) 4. 通過一個生成器對象[將字符轉換成對應的ASCII碼值](#generator-objects) 5. 使用`itertools.permutations()`函數[計算所有可能的解法](#permutations) 6. 使用`translate()`字符串方法[將所有可能的解轉換成Python表達式](#string-translate) 7. 使用`eval()`函數[通過求值Python 表達式來檢驗解法](#eval) 8. 返回第一個求值結果為`True`的解法 …僅僅14行代碼. ## 進一步閱讀 * [`itertools` 模塊](http://docs.python.org/3.1/library/itertools.html) * [`itertools`?—?用于高效循環的迭代器函數](http://www.doughellmann.com/PyMOTW/itertools/) * [觀看 Raymond Hettinger 在 PyCon 2009 上的 “Easy AI with Python” 演講](http://blip.tv/file/1947373/) * [Recipe 576615: Alphametics solver](http://code.activestate.com/recipes/576615/), Raymond Hettinger 的原始的適用于Python 2的算木謎題解決程序 * [More of Raymond Hettinger’s recipes](http://code.activestate.com/recipes/users/178123/) in the ActiveState Code repository * [算木謎題在維基百科上的頁面](http://en.wikipedia.org/wiki/Verbal_arithmetic) * [字母索引](http://www.tkcs-collins.com/truman/alphamet/index.shtml), 包含 [很多謎題](http://www.tkcs-collins.com/truman/alphamet/alphamet.shtml) 以及 [一個創建你自己的謎題的工具](http://www.tkcs-collins.com/truman/alphamet/alpha_gen.shtml) 非常感謝Raymond Hettinger同意重現授權他的代碼，因此我才能將它移植到Python 3 并作為本章的基礎。