iT邦幫忙

第 12 屆 iT 邦幫忙鐵人賽

DAY 10
0
Software Development

從零開始學Python系列 第 10

[Day 10] 從零開始學Python - 模組與套件:借一段往日旋律,宛轉悠揚

註:本文同步刊載在Medium,若習慣Medium的話亦可去那邊看呦!

先來解答昨天的問題吧!

  1. 假定有一個樓梯,你從第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的值即可。

def cs(n):
    if n == 1 or n == 2:
        return n # 請留意一件事情,函式在使用return回傳以後,不論它當下是否處在迴圏或者是否往下還有東西未完成,都會直接離開函式並回傳值歐!
    return cs(n-1) + cs(n-2)

# 測試計算從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)

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]

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的時候,我們就不會限制它最多可以記幾個,
因此利用這個性質,它會幫我們自主處理重複計算的部分。

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)

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次的計算,
因此,我們只要利用兩個變數反覆交替並取代,
最終即可得到答案。

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

for i in range(1, 101):
    print(cs(i))

註:請留意當我們在使用字典或list時,其做為參數時是整包一起給,
但當傳一般的int時,傳入的值則當成另一個本地端的變數看待。

r = 33
def t1(r):
	print(r)
	r = 2
	print(r) # 改完變2

def t2(lt):
	print(lt)
	lt[0] = 100
	print(lt)
print('t1')
t1(r)
print(r) # 改完以後外面r的值還是33

print('\nt2')
lt = [555]
t2(lt)
print(lt) # 改完後lt內的值已經成為100了!

t1
33
2
33

t2
[555]
[100]
[100]

今天我們講點比較輕鬆的東西:模組和套件
如同前面我們所提過的,因為重複做相同的事情太麻煩了,
所以使用函式來將要重複做的事情寫在一起,可以反復呼叫。
那麼,如果你知道有些你需要做的事情,
已經有別人寫過了,用現成的當然會比自己寫還要快很多囉!

我們前面已經用過幾次import(匯入)了,
它的根本其實就是從你自己寫的程式,或者別人寫的程式(或函式庫),
把前人的智慧來個拾人牙慧一下XD!
import的寫法大體有如下的變化:

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()函式,同時將其取一個別名。
(要為模組取別名也行,取別名的好處是可以比較簡短,且可以避免碰到名稱衝突的問題)

>>> import random
>>> random.random()
0.8076966930768202
>>> from random import random as rd
>>> rd()
0.23723453093568025

如果是Python內建的模組,那麼不論你的主要的程式.py檔放在哪都沒問題;
但如果你想要匯入的是別的檔案,那麼要將這些檔案放在同一個目錄下,
才能夠正常匯入。

如果我們要更嚴謹一點的話,就要使用套件的形式。
假設我們有一批寫好的檔案,他們都是這個主程式可能會用到的工具,
我們可能會開一個名為utils(工具箱)的資料夾,
裝入所有的檔案,比方說假設有check.py, schedule.py這兩個檔案。
除此以外,還要裝入一個至少是空白的檔案,必須取名為__init__.py。
(前後都有兩個底線)

所以我們的資料夾結構會變成這樣:
|--fromzero.py
|--utils
  |--__init__.py
  |--check.py
  |--schedule.py

那我們來示範一下運作的模式:

# fromzero.py
from utils import check, schedule # 透過套件的模式來匯入
print("Check a lucky number: ", check.getLucky())
print("Check daily routine: ", schedule.get())
# utils/check.py
def getLucky():
    from random import random
    return int(random() * 7 + 1) # 取1~7之間的亂數
# utils/schedule.py
def get():
    return "You have a meeting today!" # 就只是回傳一段str而已

那我們一樣來練習題目吧!

  1. 上次我們的猜數字遊戲本來是固定的數字,
    已知現在可以使用從random模組中的函式取得亂數法,
    (詳見Python Document https://docs.python.org/3/library/random.html)
    請利用random.randint(a,b)或random.random(),
    將前面的題目中要猜的數字改成隨機的1~100(含)之間的整數。

  2. 承上題,1~100當中有一些數假設有我們想避開,不想被成為要猜的數字的話,
    若給定該串列avoid_lt = [4, 14, 44, 94],
    請參照上面的說明,使用random.choice(seq)來處理。
    (random.choice()方法可以從一個序列型態的東西seq中隨機取出一個值)
    (序列是有順序的元素的集合統稱,比如list, tuple, range)
    提示:可以先新增一個數列並去處掉不要的元素再做random.choice()

辛苦啦!我們明天見!


上一篇
[Day 09] 從零開始學Python - 例外處理、遞迴:誰用三生浮世的煙火,換你一次長憶的交錯
下一篇
[Day 11] 從零開始學Python - 標準程式庫:你的機車不機車,載我瀏覽世界景色
系列文
從零開始學Python30

尚未有邦友留言

立即登入留言