python基础(补充):关于递归的优化

python基础(补充):关于递归的优化

在上一节中,我们一起探讨了递归的深度
递归深度有了底,你可以大胆使用递归了,然而问题又来了,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的递归,要不那就是在玩火!!!

运算结果的对比

方案 5次运行平均结果
使用计算缓存 0.00033620000000000004
使用functools中装饰器 0.00025677999999999996
使用github上的cache方案 0.6697569800000001
使用diskcache缓存方案 0.16480232

你可能会说:斐波那契数列递归深度100,运行1000次平均时间感觉说起来就没意思。

记住一句不要玩火就好!!!

至于本次的测试环境:python 3.6.8 其他版本的python环境可能会有一捏捏的差别,感兴趣的小伙伴可以自行测试一下。

个人感觉(不喜勿喷,狗头保命):functools中装饰器的方案还是不错的

hmoban主题是根据ripro二开的主题,极致后台体验,无插件,集成会员系统
自学咖网 » python基础(补充):关于递归的优化