在上一節中，我們一起探討了遞回的深度
遞回深度有了底，你可以大膽使用遞回了，然而問題又來了，python的遞回和蝸牛一樣慢，那么有沒有優化的余地呢？因為我也是菜鳥，所以簡單提供幾種優化方案供大家學習交流，

優化思路

第一角度優化演算法，根據遞回的計算程序計算程序中實體化了大量重復的函式計算，第一角度嘗試優化計算邏輯，但是怎么優化演算法說實話心里沒譜，

既然優化演算法沒法實作，那么我們分析一下耗時的原因，其實在遞回程序中自身呼叫自身不斷實體化自身，計算機堆記憶體溢位導致遞回有深度一次，在運算結果時候也是不斷去計算每個實體化回傳值，是否可以將計算程序中實體化回傳值保存在一個快取中或者一個IO中，計算結果時候每次從快取或者IO中讀取是不是能簡化計算量從而提高效率呢？嘗試去尋找一下快取解決方案，找到了以下幾種快取優化方案，下面來共同學習下：

我們還是以斐波那契函式為例

先來看一下沒有使用快取的斐波那契數列：

import sys
from timeit import Timer

sys.setrecursionlimit(3000)


# 沒有使用快取的斐波那契數列
def fib(n):
	if n <= 2:
		return 1
	else:
		return fib(n - 1) + fib(n - 2)


t1 = Timer("fib(100)", "from __main__ import fib")
# 斐波那契數列遞回深度100，計算1000次時間
print("fib--100", t1.timeit(number=1000), "seconds")

# 結果
# 太傷機器，放棄了

優化方案一：使用計算快取

import sys
from timeit import Timer

sys.setrecursionlimit(3000)


# 使用計算快取
def fib(n, _cache={}):
	if n in _cache:
		return _cache[n]
	elif n > 1:
		return _cache.setdefault(n, fib(n - 1) + fib(n - 2))
	return n


t1 = Timer("fib(100)", "from __main__ import fib")
print("fib--100", t1.timeit(number=1000), "seconds")

# 5次運行結果
# fib--100 0.000353 seconds
# fib--100 0.0004366 seconds
# fib--100 0.0002534 seconds
# fib--100 0.0003519 seconds
# fib--100 0.0002861 seconds
# 平均值 0.00033620000000000004

方案二：使用functools 中裝飾器

import sys
from functools import lru_cache
from timeit import Timer

sys.setrecursionlimit(3000)


# 使用functools裝飾器
@lru_cache(maxsize=None)
def fib(n):
	if n <= 2:
		return 1
	else:
		return fib(n - 1) + fib(n - 2)


t1 = Timer("fib(100)", "from __main__ import fib")
print("fib--100", t1.timeit(number=1000), "seconds")

# 5次運行結果
# fib--100 0.0002997 seconds
# fib--100 0.0002997 seconds
# fib--100 0.00024249999999999999 seconds
# fib--100 0.0002158 seconds
# fib--100 0.0002262 seconds

# 平均值 0.00025677999999999996

方案三：使用github上的cache方案

import sys
from timeit import Timer

import cache

sys.setrecursionlimit(3000)


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


t1 = Timer("fib(100)", "from __main__ import fib")
print("fib--100", t1.timeit(number=1000), "seconds")

# 5次運行結果
# fib--100 0.7063512 seconds
# fib--100 0.6536474000000001 seconds
# fib--100 0.6694901 seconds
# fib--100 0.6670560000000001 seconds
# fib--100 0.6522401999999999 seconds

# 平均值 0.6697569800000001

chahe.py代碼

import base64
import hashlib
import inspect
import pickle
import time

debug = False


def log(s):
	if debug:
		print(s)


caches = dict()
updated_caches = []


def get_cache(fname):
	if fname in caches:
		return caches[fname]
	try:
		with open(fname, "rb") as f:
			c = pickle.load(f)
	except:
		c = dict()
	caches[fname] = c
	return c


def write_to_cache(fname, obj):
	updated_caches.append(fname)
	caches[fname] = obj


def cleanup():
	for fname in updated_caches:
		with open(fname, "wb") as f:
			pickle.dump(caches[fname], f)


def get_fn_hash(f):
	return base64.b64encode(hashlib.sha1(inspect.getsource(f).encode("utf-8")).digest())


NONE = 0
ARGS = 1
KWARGS = 2


def cache(fname=".cache.pkl", timeout=-1, key=ARGS | KWARGS):
	def impl(fn):
		load_t = time.time()
		c = get_cache(fname)
		log("loaded cache in {:.2f}s".format(time.time() - load_t))

		def d(*args, **kwargs):
			log("checking cache on {}".format(fn.__name__))
			if key == ARGS | KWARGS:
				k = pickle.dumps((fn.__name__, args, kwargs))
			if key == ARGS:
				k = pickle.dumps((fn.__name__, args))
			if key == KWARGS:
				k = pickle.dumps((fn.__name__, kwargs))
			if key == NONE:
				k = pickle.dumps((fn.__name__))
			if k in c:
				h, t, to, res = c[k]
				if get_fn_hash(fn) == h and (to < 0 or (time.time() - t) < to):
					log("cache hit.")
					return res
			log("cache miss.")
			res = fn(*args, **kwargs)
			c[k] = (get_fn_hash(fn), time.time(), timeout, res)
			save_t = time.time()
			write_to_cache(fname, c)
			log("saved cache in {:.2f}s".format(time.time() - save_t))
			return res

		return d

	return impl


@cache(timeout=0.2)
def expensive(k):
	time.sleep(0.2)
	return k


@cache(key=KWARGS)
def expensive2(k, kwarg1=None):
	time.sleep(0.2)
	return k


def test():
	# Test timeout
	t = time.time()
	v = expensive(1)
	assert v == 1
	assert time.time() - t > 0.1
	t = time.time()
	expensive(1)
	assert time.time() - t < 0.1
	time.sleep(0.3)
	t = time.time()
	expensive(1)
	assert time.time() - t > 0.1
	t = time.time()
	v = expensive(2)
	assert v == 2
	assert time.time() - t > 0.1
	# Test key=_ annotation
	t = time.time()
	v = expensive2(2, kwarg1="test")
	assert v == 2
	assert time.time() - t > 0.1
	t = time.time()
	v = expensive2(1, kwarg1="test")
	assert v == 2
	assert time.time() - t < 0.1
	t = time.time()
	v = expensive2(1, kwarg1="test2")
	assert v == 1
	assert time.time() - t > 0.1
	cleanup()
	print("pass")


if __name__ == "__main__":
	test()

方案四：使用diskcache專業的快取方案

import sys
from timeit import Timer

from diskcache import FanoutCache  #如果沒有diskcache包需要先安裝 
sys.setrecursionlimit(3000)

# 快取臨時檔案位置
cache = FanoutCache('tmp/diskcache/fanoutcache')


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


t1 = Timer("fib(100)", "from __main__ import fib")
print("fib--100", t1.timeit(number=1000), "seconds")

# 5次運行結果
# fib--100 0.1423292 seconds
# fib--100 0.18016089999999998 seconds
# fib--100 0.1670817 seconds
# fib--100 0.1760245 seconds
# fib--100 0.15841529999999998 seconds

# 平均值 0.16480232

以上就是四種遞回快取方案，通過運行時間對比采取合適的優化方案即可，至于沒有使用快取方案的遞回——好傷，好傷，好傷，所以如果有非常多層次遞回深度，而且計算次數還非常多，奉勸一句或者使用快取，或者放棄python的遞回，要不那就是在玩火！！！

運算結果的對比

你可能會說：斐波那契數列遞回深度100，運行1000次平均時間感覺說起來就沒意思，

記住一句不要玩火就好！！！

至于本次的測驗環境：python 3.6.8 其他版本的python環境可能會有一捏捏的差別，感興趣的小伙伴可以自行測驗一下，

個人感覺（不喜勿噴，狗頭保命）：functools中裝飾器的方案還是不錯的

標籤：Python

上一篇：day-13-匿名函式-內置函式2-閉包

下一篇：Python 多執行緒