從斐波那契數(shù)列談起

這里 [https://robert-mcdermott.gitlab.io/posts/speeding-up-python-with-nim/]討論通過一種稱之為 Nim 的技術(shù)框架來進(jìn)行 Python 的加速（后面會(huì)對(duì) Nim 技術(shù)詳細(xì)介紹）。文章從計(jì)算斐波那契數(shù)列開始舉例，用遞歸方式來計(jì)算，并且可以看到同樣的計(jì)算方式，Python 和其他語言的速度上有不小的差異。

上述文章中提到，的確 Python 是一種優(yōu)秀的編程語言，針對(duì)程序員的工作效率進(jìn)行了優(yōu)化；令人驚訝的是，你可以非常快速實(shí)現(xiàn)的從創(chuàng)意到最低可工作的一個(gè)解決方案。它通過其非常靈活的特性和易于編寫和閱讀的語法，大大縮短了代碼開發(fā)時(shí)間。某種程度上，我們一直說 Python 的實(shí)現(xiàn)方式非常接近大腦的思考方式。（從機(jī)器學(xué)習(xí)的發(fā)展史來看，大腦的運(yùn)轉(zhuǎn)速度，比如計(jì)算加法的能力遠(yuǎn)遠(yuǎn)比不上現(xiàn)在的電腦，但是大腦在復(fù)雜推理的場(chǎng)景下有很大的優(yōu)勢(shì)。所以很多時(shí)候我覺得 Python 的直觀易學(xué)要比速度快重要的多，如果必須犧牲其中一個(gè)特性的話。）

雖然 Python 具有很低的“代碼開發(fā)時(shí)間”，但它具有很高的“代碼執(zhí)行時(shí)間”。為了解決Python非常低的執(zhí)行性能，Python 的許多擴(kuò)展模塊都是用C / C++ 等高性能語言編寫的。像 C / C++ 這樣的語言與 Python 完全相反;，它們有很高的“代碼開發(fā)時(shí)間”和非常低的“代碼執(zhí)行時(shí)間”。對(duì)于每種可能需要的計(jì)算密集型任務(wù)，不可能都有現(xiàn)成的擴(kuò)展模塊，并且在C / C++ 中編寫自己的擴(kuò)展模塊以加速Python代碼的慢速部分對(duì)于大多數(shù)Python程序員來說是遙不可及的。好在我們有不少方式可以改變這點(diǎn)。

為了了解 Python 如何執(zhí)行 CPU 密集型任務(wù)，我們使用一個(gè)非常耗時(shí)的遞歸 Fibonacci 算法來確定序列中的第 47 個(gè)數(shù)字，以模擬計(jì)算密集型任務(wù)，計(jì)算復(fù)雜度是 (O(2^n)) 。

斐波那契數(shù)列： 根據(jù)高德納（Donald Ervin Knuth）的《計(jì)算機(jī)程序設(shè)計(jì)藝術(shù)》（The Art of Computer Programming），1150年印度數(shù)學(xué)家 Gopala 和金月在研究箱子包裝對(duì)象長(zhǎng)寬剛好為1和2的可行方法數(shù)目時(shí)，首先描述這個(gè)數(shù)列。在西方，最先研究這個(gè)數(shù)列的人是比薩的列奧那多（意大利人斐波那契 Leonardo Fibonacci），他描述兔子生長(zhǎng)的數(shù)目時(shí)用上了這數(shù)列。斐波那契數(shù)列就是這樣：0, 1, 1, 2, 3, 5, 8, 13, 21……
摘自 [https://zh.wikipedia.org/wiki/斐波那契數(shù)列 ]

斐波那契數(shù)列可以表示如下：

用遞歸方式非常容易實(shí)現(xiàn)：

def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)

if __name__ == "__main__":
    x = 47
    start = time.time()
    res = fib(x)
    elapsed = time.time() - start
    print("Python Computed fib(%s)=%s in %0.4f seconds" % (x, res, elapsed))

這里的 47 是指計(jì)算到斐波那契梳理的第 47 位，在我的電腦上計(jì)算結(jié)果是
Python Computed fib(47)=2971215073 in 667.7838 seconds
將近 11 分鐘，電腦配置 Macbook Pro, 2.5 GHz Intel Core i7，16 GB 1600 MHz DDR3，這臺(tái)電腦是2015年年中的，算是中等計(jì)算水平吧。Python 版本 3.7.2。
原文作者的機(jī)器性能要更加好一點(diǎn)，Ubuntu 16.04LTS，Intel Xeon E5-2667v3 CPUs 3.20GHz.
如下表對(duì)比，我們可以看到 Python 3 在速度上要比 C 語言慢了將近 100 倍，比 Java 也慢了將近 70倍。即便是 PyPy，依然和 C 、Java 語言相比不是一個(gè)數(shù)量級(jí)的。

C Computed fib(47)=2971215073 in 4.58 seconds
Java Computed fib(47)=2971215073 in 7.74 seconds
Go Computed fib(47)=2971215073 in 10.94 seconds
JavaScript Computed fib(47)=2971215073 in 21.384 seconds
PyPy Computed fib(47)=2971215073 in 93.63 seconds
Ruby Computed fib(47)=2971215073 in 191.57 seconds
Python3 Computed fib(47)=2971215073 in 504.55 seconds
Perl5 Computed fib(47)=2971215073 in 980.24 seconds
R Computed fib(47)=2971215073 in 2734.70 seconds

遞歸計(jì)算雖然簡(jiǎn)潔明了，實(shí)際上有包含大量的重復(fù)計(jì)算，因此稱之為計(jì)算密集型，下圖可以說明遞歸過程計(jì)算的重復(fù)性：

利用計(jì)算緩存進(jìn)行優(yōu)化

我們先用一個(gè)非常有效的方式來進(jìn)行優(yōu)化，可以讓 Python 程序計(jì)算斐波那契數(shù)列立刻達(dá)到 C 語言的水平。

在 stackoverflow 上有專門討論 python 實(shí)現(xiàn) 斐波那契數(shù)列的一個(gè)帖子。里面有很多實(shí)現(xiàn)方式，有的非常巧妙執(zhí)行速度也非?？?。[https://stackoverflow.com/questions/494594/how-to-write-the-fibonacci-sequence]

我稱這個(gè)方法是計(jì)算緩存，因?yàn)檫f歸時(shí)候有大量的都是重復(fù)計(jì)算之前計(jì)算過的步驟，我們把每一次的計(jì)算輸入和輸出都存儲(chǔ)下來，形成一個(gè)緩存，這樣一個(gè)(O(2^n)) 的復(fù)雜度就成了 (O(n))，比如當(dāng)計(jì)算第 5 個(gè)數(shù)列中的數(shù)字時(shí)，第 3 個(gè)和 第 4 個(gè)都已經(jīng)在緩存中，這樣就變成了簡(jiǎn)單的加法，而不需要真正的遞歸計(jì)算了。并且并不失遞歸的優(yōu)雅本質(zhì)。

我們來看一下代碼：

def cache_fib(n, _cache={}):

    if n in _cache:
        return _cache[n]
    elif n > 1:
        return _cache.setdefault(n, cache_fib(n-1) + cache_fib(n-2))
    return n

if __name__ == "__main__":
    x = 47
    start = time.time()
    res = cache_fib(x)
    elapsed = time.time() - start
    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))

這樣修改后的執(zhí)行速度就是極速了，為此我把計(jì)算時(shí)間的代碼精確到了小數(shù)點(diǎn)后八位，否則顯示的就是 0 。
Python Computed fib(47)=2971215073 in 0.00016499 seconds

雖然我們用緩存的方式打敗了所有其他語言有點(diǎn)勝之不武，但是在真正的業(yè)務(wù)系統(tǒng)開發(fā)過程中，這樣做無可厚非，且應(yīng)該大力推廣。

“Fibonacci Numbers in Python” [https://mortada.net/fibonacci-numbers-in-python.html] 這篇文章也專門討論了在 Python 中如何實(shí)現(xiàn)斐波那契數(shù)列，并且展示了如何使用 pandas 和 matplotlib 技術(shù)來可視化的分析執(zhí)行效率。

計(jì)算緩存

緩存技術(shù)不是新技術(shù)，只是其概念在實(shí)際使用中再發(fā)生著變化。我們可以學(xué)習(xí)一下標(biāo)準(zhǔn)的緩存的定義。 [https://zh.wikipedia.org/wiki/緩存]

Cache一詞來源于1967年的一篇電子工程期刊論文。其作者將法語詞“cache”賦予“safekeeping storage”的涵義，用于計(jì)算機(jī)工程領(lǐng)域。CPU的緩存曾經(jīng)是用在超級(jí)計(jì)算機(jī)上的一種高級(jí)技術(shù)，不過現(xiàn)今計(jì)算機(jī)上使用的的AMD或Intel微處理器都在芯片內(nèi)部集成了大小不等的數(shù)據(jù)緩存和指令緩存，通稱為L(zhǎng)1緩存（L1 Cache即Level 1 On-die Cache，第一級(jí)片上高速緩沖存儲(chǔ)器）；而比L1更大容量的L2緩存曾經(jīng)被放在CPU外部（主板或者CPU接口卡上），但是現(xiàn)在已經(jīng)成為CPU內(nèi)部的標(biāo)準(zhǔn)組件；更昂貴的CPU會(huì)配備比L2緩存還要大的L3緩存（level 3 On-die Cache第三級(jí)高速緩沖存儲(chǔ)器）。
主存容量遠(yuǎn)大于CPU緩存，磁盤容量遠(yuǎn)大于主存，因此無論是哪一層次的緩存都面臨一個(gè)同樣的問題：當(dāng)容量有限的緩存的空閑空間全部用完后，又有新的內(nèi)容需要添加進(jìn)緩存時(shí)，如何挑選并舍棄原有的部分內(nèi)容，從而騰出空間放入這些新的內(nèi)容。解決這個(gè)問題的算法有幾種，如最久未使用算法（LFU）、先進(jìn)先出算法（FIFO）、最近最少使用算法（LRU）、非最近使用算法（NMRU）等，這些算法在不同層次的緩存上執(zhí)行時(shí)擁有不同的效率和代價(jià)，需根據(jù)具體場(chǎng)合選擇最合適的一種。

在現(xiàn)代開發(fā)系統(tǒng)中，由于數(shù)據(jù)吞吐量太大了，并且重復(fù)訪問的情況也非常多，為了有效的節(jié)約算力、提升響應(yīng)速度、減少對(duì)系統(tǒng)的依賴，緩存技術(shù)大大發(fā)展。比如 Redis 就是廣泛使用的一種緩存技術(shù)。剛才我們看到在遞歸計(jì)算中使用了緩存，對(duì)于性能可以有千萬倍的提升。

下面介紹一下 Python 中的一些緩存技術(shù)。

lru_cache

Python 語言就是一個(gè)瑞士軍刀，絕大多數(shù)需要的功能都已經(jīng)整裝待發(fā)。lru_cache 就是 Python 3.2 開始在 functools 中增加一個(gè)函數(shù)，通過裝飾器的方式來緩存一個(gè)函數(shù)的執(zhí)行結(jié)果。[https://docs.python.org/3/library/functools.html#functools.lru_cache]

在上面的文檔中，我們可以看到 Python 官方同樣是用斐波那契數(shù)列作為例子，可見這個(gè)斐波那契數(shù)列的遞歸其實(shí)是多么的不深入人心啊。

import time
from functools import lru_cache


@lru_cache(maxsize=None)
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


if __name__ == "__main__":
    x = 47
    start = time.time()
    res = fib(x)
    elapsed = time.time() - start
    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))
    print(fib.cache_info())

我們?cè)谧詈笠恍性黾恿孙@示緩存擊中的情況。
Python Computed fib(47)=2971215073 in 0.00003409 seconds
CacheInfo(hits=44, misses=47, maxsize=None, currsize=47)

執(zhí)行速度上可以看到比剛才我們自己實(shí)現(xiàn)的緩存算法還要快。

DiskCache

DiskCache 是一個(gè)純 Python 的緩存包，[http://www.grantjenks.com/docs/diskcache/]

DiskCache 可以有效的只用上 G 空間用于緩存，通過利用堅(jiān)如磐石的數(shù)據(jù)庫(kù)和內(nèi)存映射文件，緩存性能可以匹配并超越行業(yè)標(biāo)準(zhǔn)解決方案。（放在這里解決斐波那契數(shù)列問題有點(diǎn)殺雞用牛刀了?。?/p>

DiskCache 的主要功能如下：

• 純 Python 構(gòu)造
• 完整的文檔
• 100% 單元測(cè)試覆蓋
• 數(shù)小時(shí)的壓力測(cè)試
• Django 兼容的 API
• 線程安全和進(jìn)程安全
• 支持多種緩存算法 (包括LRU 和 LFU)
• Keys 支持標(biāo)簽、元數(shù)據(jù)等
• 基于 Python 2.7 開發(fā)，在 CPython 2.7, 3.4, 3.5, 3.6 和 PyPy 上測(cè)試
• 支持 Linux, Mac OS X 和 Windows
• 通過 Travis CI 和 AppVeyor CI 的集成測(cè)試

DiskCache 的功能更像是 Redis 和 MemCached，并且性能優(yōu)異，我們可以看看下面的性能對(duì)照表。

core-p1-get.e430ef7679304b868a3cc256804af6c3.png

DiskCache 功能非常多，我們用文檔中的一個(gè)例子修改一下，來繼續(xù)剛才的斐波那契數(shù)列的 demo，前面的計(jì)算緩存是將相關(guān)緩存代碼寫在了函數(shù)的邏輯中，通過 DiskCache 的 FanoutCache 來溝通一個(gè)函數(shù)的裝飾器，同樣且更加通用的達(dá)到計(jì)算緩存的效果。

from diskcache import FanoutCache
import time

cache = FanoutCache('/tmp/diskcache/fanoutcache')


@cache.memoize(typed=True, expire=1, tag='fib')
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


if __name__ == "__main__":
    x = 47
    start = time.time()
    res = fib(x)
    elapsed = time.time() - start
    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))

執(zhí)行效果如下：
Python Computed fib(47)=2971215073 in 0.02766585 seconds

裝飾器中的 expire 參數(shù)是多少毫秒后失效，使用 DiskCache 的話，在裝飾器發(fā)揮作用前定義了磁盤緩存文件的位置。如果將參數(shù) expire 調(diào)整到比較大的數(shù)值或者 None 的話，會(huì)發(fā)現(xiàn)再次執(zhí)行的話，速度大大提升。
Python Computed fib(47)=2971215073 in 0.00032520 seconds

DiskCache 功能強(qiáng)大，值得用專門的章節(jié)來完整的介紹。

cache.py

如果想既有 lru_cache 這樣簡(jiǎn)單，又暫時(shí)不想用 DiskCache 這樣的大家伙，但是其文件可以實(shí)例化還是不錯(cuò)的一種解決方案，我們還可以嘗試用一下 cache.py，出處在這里 [https://github.com/bwasti/cache.py]

只要 import cache 之后，就可以直接使用了。

import cache
import time


@cache.cache(timeout=20, fname="my_cache.pkl")
def fib(n):
    if n <= 2:
        return 1
    else:
        return fib(n - 1) + fib(n - 2)


if __name__ == "__main__":
    x = 47
    start = time.time()
    res = fib(x)
    elapsed = time.time() - start
    print("Python Computed fib(%s)=%s in %0.8f seconds" % (x, res, elapsed))

執(zhí)行結(jié)果如下：
Python Computed fib(47)=2971215073 in 0.02948809 seconds

列出四種緩存方式的執(zhí)行速度：

• 內(nèi)置緩存 0.00016499 seconds
• Python 自帶 lru_cache 0.00003409 seconds
• DiskCache 0.00032520 seconds
• cache.py 0.02948809 seconds

現(xiàn)在在這類計(jì)算緩存的場(chǎng)景下，Python 自帶的 lru_cache 速度最快，而 DiskCache 包性能均衡，考慮到其強(qiáng)大的功能，值得一試，cache.py 的性能一般，但是代碼非常簡(jiǎn)潔，可以學(xué)習(xí)。

之后繼續(xù)介紹 Nim 語言和怎么用 Nim 來加速 Python。