iT邦幫忙

第 11 屆 iT 邦幫忙鐵人賽

DAY 17
1
Software Development

活用python- 路遙知碼力,日久練成精系列 第 17

Day17- 存在所有人喜歡的文章?認識any(), all()函數

路遙知碼力,日久練成精- 只要在程式之路鑽研的夠深,便能夠充分發揮程式碼的力量; 練習的日子夠久,便能夠練成寫出精簡代碼的能力。

大家好,我是心原一馬,
在昨天課後練習中給大家思考如何優化判斷質數效率的問題,
首先討論一下昨天課後練習解答:
(還沒看過題目的朋友歡迎點昨日題目傳送門)
這邊以解法一為例,小馬猜可能蠻多人直覺會想要這樣改寫函數

def isPrime(n):
    return len([i for i in range(1,int(n**0.5)+1) if n%i==0])==1

因為只要判斷到根號n以前的數就好,
所以在根號n以下,如果n只能被1整除就當做質數,
乍看之下也蠻合理的。
但這種寫法會掉入一個小陷阱,
不信的信我們測試isPrime(1)的值,

print(isPrime(1))

結果為: True
咦咦?跟預期結果不太一樣?
因為1確實只被1整除,但在數學定義上不認為1是質數。
以下給出小馬的解答:

參考解答

def isPrime(n):
    return n>=2 and len([i for i in range(1,int(n**0.5)+1) if n%i==0])==1

想法很簡單,只有2以上的整數才有可能是質數,
在前面加上判斷n>=2的條件即可。
解法可能不只一種,
如有其它寫法或任何問題也歡迎留言討論哦。
等一下文中會繼續討論進一步的效率優化。

多個and, or 的實現- any, all

今天再來跟大家介紹幾個python好用的函數,
先簡介any及all這兩個函數,
它們的參數都是接收一個迭代器
它們有點像是口語說的存在所有這兩個詞,
分別用來判斷「迭代器存在一個元素為True嗎?」及
「迭代器的所有元素皆為True嗎?」這兩件事。
any及all有點像是我們在Day7技巧5中教過的多個and, or的特性實現,
0、空(如: 空字串、空列表、…)、None、False 都視為 False,
除此之外的元素都視為 True。
與python 中and, or 不同的特性為:
any及all一定是返回True或是False這兩個值。

any- 存在

any 參數接收一個迭代器,
只要迭代器有任何一個元素的值為True
那麼any函數的值就為True,否則為False
注意若參數本身為空列表any的值則為False
例如:

>>> any([2>5,5>0,0>2])
True
>>> any([-1,0,[]])
True #數字0才會被視為False,-1是非0數字,視為True
>>> any([])
False

any函數有點像是我們口語所說的存在
True可以看做是滿足條件的元素,
所以只要迭代器存在一個元素的值為True就算True

all- 所有

all 參數接收一個迭代器,
如果迭代器所有元素的值為True
那麼all函數的值才為True
注意若參數本身為空列表all的值則為True
例如:

>>> all(['a'<'b','b'<'c'])
True
>>> all(['a'<'b',1<2, 0])
False #數字0視為False
>>> all([])
True

all函數有點像是我們口語所說的所有
True可以看做是滿足條件的元素,
當迭代器每個元素都為True,即看作所有元素都滿足條件了。

範例17-1 在找到其它因數時,提早結束判斷質數

好的,目前我們已經寫出這樣的判斷質數程式:

def isPrime(n):
    return n>=2 and len([i for i in range(1,int(n**0.5)+1) if n%i==0])==1

不過想要繼續優化效率的話,
any, all函數不失為一個很好的方法哦,
關鍵在於any, all函數不一定需要把列表中所有的值都檢查過,
而能夠提早返回結果。
我們以any函數,「存在」為例子,
試想,假設我們問這樣的問題:
「某某大學裡存在漂亮的女生嗎?」
那麼其實你走在校園裡只要看到一個漂亮的女生,
這個問題的答案便是True
而不需要把所有學生都看過一遍。

回到判斷質數的例子,
其實如果2到根號n之間,
存在一個數字可以整除n,
那麼n便不會是質數了,
因此函數可以改寫為:

def isPrime(n):
    return n>=2 and not any(n%i==0 for i in range(2,int(n**0.5+1)))

注意any函數中放的是生成器而不是列表
才能達到效率最佳化。

在優化判斷質數的路上…

Day13起,我們已經教各位多種判斷質數函數的寫法了,
究竟後續的寫法是否效率真的高於前者呢?
讓我們以數據實測看執行時間吧。

我們仿照Day14的寫法,寫一個測量函數時間的函數:

import time
def measureTime(func):
    tStart = time.time() #計時開始
    for i in range(1000, 30000):
        func(i)
    tEnd = time.time() #計時結束
    print(f"{func.__name__} 總共執行了{(tEnd - tStart):.4f}秒")

其實參數func表示某種判斷質數的函數,
measureTime這個函數做的事情,
便是計算該函數判斷所有1000到30000之間的數字是否為質數所需的總時間。

我們再寫上五種不同版本的判斷質數函數:

def isPrimeV1_1(n):
    return len([i for i in range(1,n+1) if n%i==0])==2

def isPrimeV1_2(n):
    return sum([1 if n%i==0 else 0 for i in range(1,n+1)])==2

def isPrime_V2(n):
    return n>=2 and len([i for i in range(1,int(n**0.5)+1) if n%i==0])==1

def isPrime_V3_List(n):
    return n>=2 and not any([n%i==0 for i in range(2,int(n**0.5+1))])

def isPrime_V3(n):
    return n>=2 and not any(n%i==0 for i in range(2,int(n**0.5+1)))

版本V1_1V1_2是在Day13提出的算法,
會檢查所有一到n之間的數字。
版本V2是今天提出的第一種優化版本,只檢查到根號n以下的數字便停下來。
版本V3是透過any函數達到提早結束判斷的優化,
版本V3_List則是將any函數內改放列表生成式,
測試究竟不用生成器效能是否真的差很多。

效率大比拼

未看先猜,你覺得哪一個函數效能最好?大約好多少?
完整的檢驗程式碼如下:

def isPrimeV1_1(n):
    return len([i for i in range(1,n+1) if n%i==0])==2

def isPrimeV1_2(n):
    return sum([1 if n%i==0 else 0 for i in range(1,n+1)])==2

def isPrime_V2(n):
    return n>=2 and len([i for i in range(1,int(n**0.5)+1) if n%i==0])==1

def isPrime_V3_List(n):
    return n>=2 and not any([n%i==0 for i in range(2,int(n**0.5+1))])

def isPrime_V3(n):
    return n>=2 and not any(n%i==0 for i in range(2,int(n**0.5+1)))

measureTime(isPrimeV1_1)
measureTime(isPrimeV1_2)
measureTime(isPrime_V2)
measureTime(isPrime_V3_List)
measureTime(isPrime_V3)

其實,單純看程式碼的話,
你可能覺得五支程式碼看起來程式都差不多啊?
應該…不會差很多吧,
看了結果絕對讓你吃驚:

isPrimeV1_1 總共執行了25.3204秒
isPrimeV1_2 總共執行了38.2611秒
isPrime_V2 總共執行了0.2678秒
isPrime_V3_List 總共執行了0.2990秒
isPrime_V3 總共執行了0.1491秒

驚訝不驚訝?
第二版和第三版的函數,
效率比第一版函數快了一百倍左右。
想要提升程式速度,
除了買一台更好的硬體設備,
好的演算法才是百倍速的王道啊。

效能差異分析

其中版本V1_2的所需時間約是版本V1_1的1.5倍,
原因大概可歸咎於「計算總和」比「計算列表長度」的開銷來的大,
而版本V1_2所存的列表又比版本V1_1來的大的緣故。

單純版本V2V3比較的話,V3真的快上許多,
V3_List反而更慢了,
這其實提醒我們,
生成器保存的只是一種算法,
需要時才會去計算下一個元素,
不必像列表生成式一樣一開始就把所有東西算好存起來,
使any()能夠真正在找到滿足條件元素時提早跳出迴圈。

今天先學到這裡吧,
希望大家除了精簡的語法外,
也能體會好的演算法對程式效率的影響。

課後練習

最近好像對於質數的問題研究很多呢。
今天給大家練習的是「如何找下一個質數」。

習題: 下一個質數

給你底下這支程式:

def isPrime(n):
    return n>=2 and not any(n%i==0 for i in range(2,int(n**0.5+1)))
    
def nextPrime(n):
    pass
    
n=1
for i in range(20):
    n = nextPrime(n)
    print(f'{n} is a {i}th prime.')

我們希望用這支程式找前20小的質數,
函數isPrime(n)與測試的程式都已經寫好了,
請完成nextPrime(n)函數的定義,
使nextPrime(n)回傳大於n的第一個質數吧。
歡迎於留言區討論你的答案哦。

預期結果:

2 is a 0th prime.
3 is a 1th prime.
5 is a 2th prime.
7 is a 3th prime.
11 is a 4th prime.
13 is a 5th prime.
17 is a 6th prime.
19 is a 7th prime.
23 is a 8th prime.
29 is a 9th prime.
31 is a 10th prime.
37 is a 11th prime.
41 is a 12th prime.
43 is a 13th prime.
47 is a 14th prime.
53 is a 15th prime.
59 is a 16th prime.
61 is a 17th prime.
67 is a 18th prime.
71 is a 19th prime.

(註: 隨著「路遙知碼力,日久練成精」已進入後半段,
給讀者們的練習難度也隨之加深,
未必能像之前的課後練習總是能一行解開,
盡可能的寫你覺得好的答案即可)


上一篇
Day16- Project1- 數字世界的朋友與戀人 (趣味數論問題: 友好數、婚約數)
下一篇
Day18 - 當我們「鏈」在一起,認識zip()函數
系列文
活用python- 路遙知碼力,日久練成精30

尚未有邦友留言

立即登入留言