iT邦幫忙

第 11 屆 iThome 鐵人賽

DAY 17
1
Software Development

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

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

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

多個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
圖片
  直播研討會
圖片
{{ item.channelVendor }} {{ item.webinarstarted }} |
{{ formatDate(item.duration) }}
直播中

2 則留言

0
YoUoNim
iT邦新手 5 級 ‧ 2020-12-18 13:46:19
def nextPrime(n):
    while n > 0:
        n += 1
        if isPrime(n):
            return n

我寫的真爛~~

0
bluefishtear
iT邦新手 5 級 ‧ 2022-11-28 21:31:40
def nextPrime(n):
    n+=1
    while not isPrime(n):
      n+=1
    return n

我要留言

立即登入留言