当前位置：自学咖网 > 技术教程 > 编程最新 > python基础（补充）：关于递归的优化
wenwen 编程最新

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基础（补充）：关于递归的优化

wen 普通

分享到：

相关推荐

疯了..Spring 再爆惊天大漏洞。。

Spring 官宣高危漏洞 大家好，我是栈长。 前几天爆出来的 Spring 漏洞，刚修复完又来？ 今天愚人节来了，这是和大家开玩笑吗？ 不是的，我也是猝不及防！这个玩笑也开的太大了！！ 你之前看到的这个漏洞已经是过去式...

c语言怎么输入3个数输出最大值

方法：首先使用scanf()接收从键盘输入的三个数；然后使用“if else”语句比较三个数的大小，获得最大值；最后使用print()函数将最大值输出即可。 本教程操作环境：windows7系统、c99版本、Dell G...

day43-反射02

2.Class类 2.1基本介绍 Class类也是类，因此也继承Object类 Class类对象不是new出来的，而是系统创建的 对于某个类的Class类对象，在内存中只有一份，因为类只加载一次 每个类的实例都会记得自己...

学习PHP中的任意精度扩展函数

今天来学习的是关于数学方面的第一个扩展。对于数学操作来说，无非就是那些各种各样的数学运算，当然，整个程序软件的开发过程中，数学运算也是最基础最根本的东西之一。不管你是学得什么专业，到最后基本上都会要学习数据结构与算法，而...