[数据结构与算法]计算速度太慢？试试 lru_cache 装饰器

众所周知，python语言是相当好用的，但是它的执行性能也是相对其他语言比较慢的。还好python提供了一个非常优秀的装饰器来解决这个问题，它就是lru_cache装饰器。lru_cache是通过著名的LCU算法来实现的，也就是最近最久未使用缓存淘汰算法。

【阅读全文】

为了形成明显的对比，使用普通的方式来实现一个函数的递归过程，即不添加任何的装饰器来实现。

def func(n):
    '''
    递归样例函数、未添加lru_cache装饰器
    :param n:
    :return:
    '''
    if n <= 1:
        return n
    return func(n - 1) + func(n - 2)

接下来，再使用 lru_cache 装饰器的方式实现一遍，首先，导入需要装饰器模块。

from functools import lru_cache

过程比较简单，这样准备工作就完成。然后，在代码块中直接引用即可。

@lru_cache
def func(n):
    '''
    递归样例函数、添加lru_cache装饰器
    :param n:
    :return:
    '''
    if n <= 1:
        return n
    return func(n - 1) + func(n - 2)

如上述代码所示，只需要在函数定义的部分加入装饰器的修饰大功告成了。

最后，只需要写一个main函数分别调用这两个函数就会出现显而易见的效果。

import time

'''
测试消耗时间
'''
if __name__ == '__main__':
    start_time = time.time()
    result = func(10)
    end_time = time.time()
    cost_time = end_time - start_time
    print('result is ' + str(result),'cost_time is ' + str(cost_time))

通过上面@lru_cache的使用实例，可以清楚的发现cost_time is 0.0，时间上的消耗基本可以忽略不计。而在不使用此装饰器的情况下运算了半天都没有出来结果，效果是显而易见的。

@lru_cache 装饰器使用大致来讲就是将每次递归计算的数据结果作为 hash 缓存记录，当再次需要这个结果的时候就直接从缓存的数据中将结果取出避免重复计算的性能消耗。它的底层实现也牵扯到双向链表、hash表等实现处理过程，更深层次的LCU算法原理大家可以学习数据结构+算法的一些常规知识。

【往期推荐】

冒泡排序、选择排序之间的比较与代码实现！

如何通过pynput与日志记录实现键盘、鼠标的监听行为？

如果你是一名java程序员，面对已经写好的python脚本该如何调用，其实很简单！

如何使用PyQt5一步步实现用户登录GUI界面、登录后跳转？

办公自动化：几行代码将PDF文档转换为WORD文档（代码实战）！