Python 高階函數 -- filter

詳細內容請參考廖雪峰官網，此處只是一些摘抄，心得與練習的coding。

1. Python內建的filter()函數用於過濾序列。

   和map()類似(可參考 Python 高階函數 -- map/reduce)，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]

    

2. 用filter求素數
   

   計算素數的一個方法是埃氏篩法，它的演算法理解起來非常簡單：

   首先，列出從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表示“全體自然數”，“全體素數”這樣的序列，而代碼非常簡潔。

3. 練習
   回數是指從左向右讀和從右向左讀都是一樣的數，例如12321，909。請利用filter()篩選出回數：
   

   # -*- coding: utf-8 -*-
   def is_palindrome(n):
       s = str(n)
       count = 0
       length = len(s)
       half = int(length/2) #eg. 1234321 ->half num:3
       flag = True
       while count< half:
           if s[count] == s[length-count-1] :
               count +=1
               continue
           else:
               flag=False
               break
       return flag
   
   
   # 測試:
   output = filter(is_palindrome, range(1, 1000))
   print('1~1000:', list(output))
   if list(filter(is_palindrome, range(1, 200))) == [1, 2, 3, 4, 5, 6, 7, 8, 9, 11, 22, 33,
                                                     44, 55, 66, 77, 88, 99, 101, 111, 121,
                                                     131, 141, 151, 161, 171, 181, 191]:
       print('測試成功!')
   else:
       print('測試失敗!')