C++,python,热爱算法和机器学习
全部博文（1214）
分类： Python/Ruby
2020-09-01 11:08:49
前言：
前一篇简单探讨了python递归的深度问题，递归深度有了底，你可以大胆使用递归了，然而问题又来了，有朋友说python的递归和蜗牛一样慢，那么有没有优化的余地呢？因为我也是菜鸟，所以简单提供几种优化方案供大家学习交流，主要思路学习于简书我们测试案例有所区别；
具体优化：
优化思路：第一角度优化算法，根据递归的计算过程计算过程中实例化了大量重复的函数计算，第一角度尝试优化计算逻辑，但是这虽然计算过程看起来像一个二叉树，但是怎么优化算法说实话心里没谱；
既然优化算法没法实现，那么我们分析一下耗时的原因，其实在递归过程中自身调用自身不断实例化自身，计算机堆内存溢出导致递归有深度一次，在运算结果时候也是不断去计算每个实例化返回值，是否可以将计算过程中实例化返回值保存在一个缓存中或者一个IO中，计算结果时候每次从缓存护着IO中读取是不是能简化计算量从而提高效率呢？尝试去寻找一下缓存解决方案。最终找到好几种缓存优化方案，下面来共同学习下：
看方案之前我们先测试一下1000次斐波那契数列递归结果耗时，最终对比每一种缓存方案结果来进行比较：
代码实现和结果（本篇就不上图了）：
-
#coding:utf-8
-
from timeit import Timer
-
import sys
-
sys.setrecursionlimit(3000)
-
-
#没有使用缓存的斐波那契数列
-
def fib(n):
-
if n <= 2:
-
return 1
-
else:
-
return fib(n-1)+fib(n-2)
-
-
if __name__ == "__main__":
-
t1 = Timer("fib(100)","from __main__ import fib")
-
# 斐波那契数列递归深度100，计算1000次平均时间
-
print("fib--100", t1.timeit(number=1000), "seconds")
-
#计算结果我的电脑没计算出来，后边使用深度20做了计算；
方案一：使用计算缓存：
-
#coding:utf-8
-
from timeit import Timer
-
import sys
-
sys.setrecursionlimit(3000)
-
#使用计算缓存
-
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__":
-
t1 = Timer("cache_fib(100)","from __main__ import cache_fib")
-
print("cache_fib--100", t1.timeit(number=1000), "seconds")
-
-
#计算结果：
-
cache_fib--100 0.00034458100000001046 seconds
方案二：使用functools 中缓存：
-
#coding:utf-8
-
from timeit import Timer
-
from functools import lru_cache
-
import sys
-
sys.setrecursionlimit(3000)
-
-
#使用functools装饰器
-
@lru_cache(maxsize=None)
-
def fib_cache(n):
-
if n <= 2:
-
return 1
-
else:
-
return fib_cache(n-1)+fib_cache(n-2)
-
-
if __name__ == "__main__":
-
t1 = Timer("fib_cache(100)","from __main__ import fib_cache")
-
print("fib_cache(100)",t1.timeit(number=1000),"seconds")
-
-
#计算结果；
-
#fib_cache(100) 0.0001750409999999869 seconds
方案三：使用cache（github上方案）
-
#coding:utf-8
-
from timeit import Timer
-
import cache
-
import sys
-
sys.setrecursionlimit(3000)
-
-
@cache.cache(timeout=20,fname="my_cache.pkl")
-
def fib_cache(n):
-
if n <= 2:
-
return 1
-
else:
-
return fib_cache(n-1)+fib_cache(n-2)
-
-
if __name__ == "__main__":
-
t1 = Timer("fib_cache(100)","from __main__ import fib_cache")
-
print("fib_cache(100)",t1.timeit(number=1000),"seconds")
-
-
#计算结果：
-
fib_cache(100) 0.39800654799999996 seconds
-
-
-
#使用从cache代码如下：
-
import pickle
-
import time
-
import inspect
-
import base64
-
import hashlib
-
-
-
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专业的缓存方案（重量级选手，越复杂效果越显著）
-
#coding:utf-8
-
from timeit import Timer
-
from diskcache import FanoutCache
-
import sys
-
sys.setrecursionlimit(3000)
-
-
#缓存临时文件位置
-
cache = FanoutCache('tmp/diskcache/fanoutcache')
-
-
@cache.memoize(typed=True,expire=None,tag='fib_disk')
-
def fib_disk(n):
-
if n <= 2:
-
return 1
-
else:
-
return fib_disk(n-1)+fib_disk(n-2)
-
-
if __name__ == "__main__":
-
t1 = Timer("fib_disk(100)","from __main__ import fib_disk")
-
print("fib_disk(100)",t1.timeit(number=1000),"seconds")
-
-
#运行时间：
-
fib_disk(100) 0.12914266199999996 seconds
以上就是五组递归缓存方案，通过运行时间对比采取合适的优化方案即可，没有使用缓存方案的递归运行期间我的cpu利用率一直都是100%，好伤，所以如果有非常多层次递归深度，而且计算次数还非常多，奉劝一句已经使用缓存，或者放弃python的递归，要不那就是在玩火；
斐波那契数列递归深度100，1000次运行平均秒数如下：
#计算结果：
使用计算缓存：
cache_fib--100 0.00034458100000001046 seconds
使用functools中装饰器：
fib_cache(100) 0.0001750409999999869 seconds
使用缓存临时文件：
fib_disk(100) 0.12914266199999996 seconds
使用github上的cache方案：
fib_cache(100) 0.39800654799999996 seconds
至于斐波那契数列递归深度100，运行1000次平均时间感觉说起来就没意思，记住一句不要玩火就好；
所以使用@lru_cache深度层次感觉还是不错的选择；
递归深度100，不使用任何优化跑1000次我的物理机cpu转的飞起，cpu利用率时刻接近100%，运行了15分钟没出结果我掐断了，所以如果递归深度够大请不要玩火，然后尝试小的深度和之前最优方案比对了下：
20深度1000次平均结果：
fib--20 1.707903223 seconds
然后再看下lru_cache缓存20深度1000次运行平均结果：
fib_cache(20) 7.102700000000128e-05 seconds
注意是科学输入法输出的，7.1乘以10的-5次方，结果显而易见，优化速度是多少备我就不算了，所以你的递归还不使用缓存优化吗？