Day 10 模組與套件：借一段往日旋律，宛轉悠揚
註：本篇文章同步刊載於iT邦幫忙，為鐵人賽之系列文章。
https://ithelp.ithome.com.tw/articles/10242602
先來解答昨天的問題吧！
- 假定有一個樓梯，你從第0階要爬到第n階，
每次你只能選擇爬1階或者爬2階，這樣稱做一步。
請寫出一個函式名為cs ，給定n的値以後(n > 0)，
計算出從第0階爬到第n階的方法共有幾種不同的變化？
上一篇提到了遞迴的關鍵點，首要在於將目標不斷簡化，
那麼我們該怎麼思考這題的簡化呢？
想想看，爬到第n階之前，應該要先爬到哪一階呢？
應該是n-1或n-2階吧？因為一次只能走一步和走兩步。
也就是說，假設我們知道cs(n-1)跟cs(n-2)，
我們就能知道cs(n)，因為它們兩個狀況只要分別走1步或2步，
就可以到達第n階，
而且cs(n-1)跟cs(n-2)彼此之間並沒有重複的走法。
所以cs(n) = cs(n-1) + cs(n-2)，
接下來的問題是，在什麼狀況下該停下來？
顯然，在n = 1及n = 2時，
cs(1)和cs(2)的值已經確定是1跟2了，
所以我們每次在遞迴時，只要碰到n=1或n=2時，就應該回傳n的值即可。
1
2
3
4
| def cs(n):
if n == 1 or n == 2:
return n # 請留意一件事情，函式在使用return回傳以後，不論它當下是否處在迴圏或者是否往下還有東西未完成，都會直接離開函式並回傳值歐！
return cs(n-1) + cs(n-2)
|
1
2
3
| # 測試計算從cs(1)到cs(100)
for i in range(1, 101):
print(cs(i))
|
這麼做其實有一個缺點：
比方說我們算cs(10)的時候，會拆分成cs(9)跟cs(8)，
而接下來會是：
cs(9) -> cs(8) + cs(7) -> cs(7) + cs(6) + cs(6) + cs(5) -> …
cs(8) -> cs(7) + cs(6) -> cs(6) + cs(5) + cs(5) + cs(4) -> …
在化簡的過程中，因為Python並不知道我們有重複的東西，
所以它並不會主動去幫我們把相同的cs(x)給結合在一起，
所以最終就會相當耗時。
(讀者可以執行)
那該怎麼改善呢？
這裡提供兩個方法。
方法一：將用過的答案先記下來(可以使用list或dict)
1
2
3
4
5
6
7
| def cs(n, dic):
# n在裡面就直接回傳(因為已經算過了!)
if n in dic:
return dic[n]
# 先將n的結果算完再回傳，別忘了放到字典裡！
dic[n] = cs(n-1, dic) + cs(n-2, dic)
return dic[n]
|
1
2
3
| dic = {1 : 1, 2 : 2} # 預設cs(1), cs(2)的結果
for i in range(1, 101):
print(cs(i, dic))
|
方法二：lru_cache
lru_cahce是一個工具，
它可以記住函式已經計算過的內容，並存放起來。
在maxsize=None的時候，我們就不會限制它最多可以記幾個，
因此利用這個性質，它會幫我們自主處理重複計算的部分。
1
2
3
4
5
6
| import functools
@functools.lru_cache(maxsize=None) # 用@開頭的稱為裝飾器，有興趣的讀者可再深入了解。
def cs(n):
if n == 1 or n == 2:
return n
return cs(n-1) + cs(n-2)
|
1
2
| for i in range(1, 101):
print(cs(i))
|
那麼該如何做出迭代解呢？
由於cs(n)只跟cs(n-1)和cs(n-2)有關，
我們完全可以從cs(3)開始，一路往上加到結束。
1+2=3, 2+3=5, 3+5=8, …以此類推。
當我們要算cs(n)時，表示我們需要經過n-2次的計算，
因此，我們只要利用兩個變數反覆交替並取代，
最終即可得到答案。
1
2
3
4
5
6
7
8
| def cs(n):
if n == 1 or n == 2: return n
s1, s2 = 1, 2
for i in range(n - 2):
# Python的賦值是會一起看開始前的值來計算
# 所以不會因為s1的值變s2了, s2新的值就變成s2+s2
s1, s2 = s2, s1 + s2
return s2
|
1
2
| for i in range(1, 101):
print(cs(i))
|
註：請留意當我們在使用字典或list時，其做為參數時是整包一起給，
但當傳一般的int時，傳入的值則當成另一個本地端的變數看待。
1
2
3
4
5
| r = 33
def t1(r):
print(r)
r = 2
print(r) # 改完變2
|
1
2
3
4
| def t2(lt):
print(lt)
lt[0] = 100
print(lt)
|
1
2
3
| print('t1')
t1(r)
print(r) # 改完以後外面r的值還是33
|
1
2
3
4
| print('\nt2')
lt = [555]
t2(lt)
print(lt) # 改完後lt內的值已經成為100了!
|
1
2
3
4
| t2
[555]
[100]
[100]
|
今天我們講點比較輕鬆的東西：模組和套件
如同前面我們所提過的，因為重複做相同的事情太麻煩了，
所以使用函式來將要重複做的事情寫在一起，可以反復呼叫。
那麼，如果你知道有些你需要做的事情，
已經有別人寫過了，用現成的當然會比自己寫還要快很多囉！
我們前面已經用過幾次import(匯入)了，
它的根本其實就是從你自己寫的程式，或者別人寫的程式(或函式庫)，
把前人的智慧來個拾人牙慧一下XD!
import的寫法大體有如下的變化：
1
2
3
4
| import module # 直接將整個檔案納入(不用加.py)
from module import function # 只匯入function的部分
import module as xx # xx是自己選的名字，用來在這個程式中全程替代原先的module名
from module import function as oo # 這時候用oo就相當於跟function一樣
|
舉例來說，在Python中有一個內建模組叫random，random中的random()，
可以隨機生成一個0~1之間的小數亂數(包含0但不包含1)，
我們可以先import random，再呼叫random的random()函式來得到亂數；
或者，我們可以從random中取得random()函式，同時將其取一個別名。
(要為模組取別名也行，取別名的好處是可以比較簡短，且可以避免碰到名稱衝突的問題)
1
2
3
4
5
6
| >>> import random
>>> random.random()
0.8076966930768202
>>> from random import random as rd
>>> rd()
0.23723453093568025
|
如果是Python內建的模組，那麼不論你的主要的程式.py檔放在哪都沒問題；
但如果你想要匯入的是別的檔案，那麼要將這些檔案放在同一個目錄 下，
才能夠正常匯入。
如果我們要更嚴謹一點的話，就要使用套件 的形式。
假設我們有一批寫好的檔案，他們都是這個主程式可能會用到的工具，
我們可能會開一個名為utils(工具箱)的資料夾，
裝入所有的檔案，比方說假設有check.py, schedule.py這兩個檔案。
除此以外，還要裝入一個至少是空白的檔案，必須取名為__init__.py。
(前後都有兩個底線)
所以我們的資料夾結構會變成這樣：
1
2
3
4
5
| | — fromzero.py
| — utils
| — __init__.py
| — check.py
| — schedule.py
|
那我們來示範一下運作的模式：
1
2
3
4
| # fromzero.py
from utils import check, schedule # 透過套件的模式來匯入
print("Check a lucky number: ", check.getLucky())
print("Check daily routine: ", schedule.get())
|
1
2
3
4
| # utils/check.py
def getLucky():
from random import random
return int(random() * 7 + 1) # 取1~7之間的亂數
|
1
2
3
| # utils/schedule.py
def get():
return "You have a meeting today!" # 就只是回傳一段str而已
|
那我們一樣來練習題目吧！
- 上次我們的猜數字遊戲本來是固定的數字，
已知現在可以使用從random模組中的函式取得亂數法，
(詳見Python Document https://docs.python.org/3/library/random.html)
請利用random.randint(a,b)或random.random()，
將前面的題目中要猜的數字改成隨機的1~100(含)之間的整數。 - 承上題，1~100當中有一些數假設有我們想避開，
不想被成為要猜的數字的話，
若給定該串列avoid_lt = [4, 14, 44, 94]，
請參照上面的說明，使用random.choice(seq)來處理。
(random.choice()方法可以從一個序列型態的東西seq中隨機取出一個值)
(序列是有順序的元素的集合統稱，比如list, tuple, range)
提示：可以先新增一個數列並去處掉不要的元素再做random.choice()
辛苦啦！我們明天見！
工商時間：
抽獎活動還在繼續累積人數(現在好像沒有人想抽XD)
在Python Taiwan的連結第100篇的文章 底下，
公開分享到你的臉書、按讚該篇文章、並留言告訴我說，
「你最喜歡這一整個系列的哪一篇？為什麼？」或
「除了從LeetCode學演算法系列以外，
你還想要看到關於什麼方向的文章？」
超過20則留言的話 (有完成以上步驟的才算)，我們就抽一組
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」
課程的免費兌換券進行贈送！
期限嘛…就延長到滿人數吧XDD (不然也沒辦法哈哈)
容筆者工商一下，
「從Leetcode學演算法｜進階篇」 開放預購啦！
這次選了40道難度加深的LeetCode題目，
同樣也會細部解說對應的技巧及須要掌握的演算法！
同時這次購買進階篇的話，
額外還加贈**「從Leetcode學演算法｜面試篇」** ！
當中包含了面試準備須知分享 ，及訪談國內外不同經驗的工程師 ，
讓你不論是想走前端/後端/一般軟工 或者是想找國外的工作 ，
是初學想轉職 還是正在工作 ，都能夠從中得到收穫呦！
有興趣的朋友可以使用下面的早鳥優惠～
「從Leetcode學演算法｜進階篇」+「從Leetcode學演算法｜面試篇」 ：
https://bit.ly/advleetcode
「從Leetcode學演算法」全套(基礎/進階/面試篇)同捆優惠：
https://bit.ly/allleetcode
