# filter Python內建的`filter()`函數用于過濾序列。 和`map()`類似，`filter()`也接收一個函數和一個序列。和`map()`不同的時，`filter()`把傳入的函數依次作用于每個元素，然后根據返回值是`True`還是`False`決定保留還是丟棄該元素。 例如，在一個list中，刪掉偶數，只保留奇數，可以這么寫： ``` def is_odd(n): return n % 2 == 1 list(filter(is_odd, [1, 2, 4, 5, 6, 9, 10, 15])) # 結果: [1, 5, 9, 15] ``` 把一個序列中的空字符串刪掉，可以這么寫： ``` def not_empty(s): return s and s.strip() list(filter(not_empty, ['A', '', 'B', None, 'C', ' '])) # 結果: ['A', 'B', 'C'] ``` 可見用`filter()`這個高階函數，關鍵在于正確實現一個“篩選”函數。 注意到`filter()`函數返回的是一個`Iterator`，也就是一個惰性序列，所以要強迫`filter()`完成計算結果，需要用`list()`函數獲得所有結果并返回list。 ## 用filter求素數 計算[素數](http://baike.baidu.com/view/10626.htm)的一個方法是[埃氏篩法](http://baike.baidu.com/view/3784258.htm)，它的算法理解起來非常簡單： 首先，列出從`2`開始的所有自然數，構造一個序列： 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15, 16, 17, 18, 19, 20, ... 取序列的第一個數`2`，它一定是素數，然后用`2`把序列的`2`的倍數篩掉： 3, ~~4~~, 5, ~~6~~, 7, ~~8~~, 9, ~~10~~, 11, ~~12~~, 13, ~~14~~, 15, ~~16~~, 17, ~~18~~, 19, ~~20~~, ... 取新序列的第一個數`3`，它一定是素數，然后用`3`把序列的`3`的倍數篩掉： 5, ~~6~~, 7, ~~8~~, ~~9~~, ~~10~~, 11, ~~12~~, 13, ~~14~~, ~~15~~, ~~16~~, 17, ~~18~~, 19, ~~20~~, ... 取新序列的第一個數`5`，然后用`5`把序列的`5`的倍數篩掉： 7, ~~8~~, ~~9~~, ~~10~~, 11, ~~12~~, 13, ~~14~~, ~~15~~, ~~16~~, 17, ~~18~~, 19, ~~20~~, ... 不斷篩下去，就可以得到所有的素數。 用Python來實現這個算法，可以先構造一個從`3`開始的奇數序列： ``` def _odd_iter(): n = 1 while True: n = n + 2 yield n ``` 注意這是一個生成器，并且是一個無限序列。 然后定義一個篩選函數： ``` def _not_divisible(n): return lambda x: x % n > 0 ``` 最后，定義一個生成器，不斷返回下一個素數： ``` def primes(): yield 2 it = _odd_iter() # 初始序列 while True: n = next(it) # 返回序列的第一個數 yield n it = filter(_not_divisible(n), it) # 構造新序列 ``` 這個生成器先返回第一個素數`2`，然后，利用`filter()`不斷產生篩選后的新的序列。 由于`primes()`也是一個無限序列，所以調用時需要設置一個退出循環的條件： ``` # 打印1000以內的素數: for n in primes(): if n < 1000: print(n) else: break ``` 注意到`Iterator`是惰性計算的序列，所以我們可以用Python表示“全體自然數”，“全體素數”這樣的序列，而代碼非常簡潔。 ## 練習 回數是指從左向右讀和從右向左讀都是一樣的數，例如`12321`，`909`。請利用`filter()`濾掉非回數： ``` # -*- coding: utf-8 -*- def is_palindrome(n): pass # 測試: output = filter(is_palindrome, range(1, 1000)) print(list(output)) ``` ## 小結 `filter()`的作用是從一個序列中篩出符合條件的元素。由于`filter()`使用了惰性計算，所以只有在取`filter()`結果的時候，才會真正篩選并每次返回下一個篩出的元素。 ## 參考源碼 [do_filter.py](https://github.com/michaelliao/learn-python3/blob/master/samples/functional/do_filter.py) [prime_numbers.py](https://github.com/michaelliao/learn-python3/blob/master/samples/functional/prime_numbers.py)