Fork me on GitHub

使用缓存优化斐波那契

当你觉得很累的时候,说明你正在走上坡路。

网上看到某位大佬讲这个,自己也动手写写

cache优化

通过缓存,如果计算过的值在缓存中,就不需要重复计算

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
from functools import wraps
import time

def cache(func):
data = {}

@wraps(func) # 消除装饰的副作用
def wrapper(n):
if n not in data:
result = func(n)
data[n] = result
return data[n]
return wrapper

@cache
def fib_use_cache(n):
if n <= 2:
return 1
return fib_use_cache(n - 2) + fib_use_cache(n - 1)

def fib_none_cache(n):
if n <= 2:
return 1
return fib_none_cache(n - 2) + fib_none_cache(n - 1)

def main():
# none cache
print('none cache')
start_time = time.time()
for i in range(1, 30):
print(fib_none_cache(i))
end_time = time.time()
print('cost time:{}'.format(end_time - start_time))
print('-' * 30)

# use cache
print('use cache')
start_time = time.time()
for i in range(1, 30):
print(fib_use_cache(i))
end_time = time.time()
print('cost time:{}'.format(end_time - start_time))

if __name__ == '__main__':
main()

缓存有限,使用LRUcache优化

使用双端链表加快添加和删除
使用LRU算法,维护最近使用过的,移除最近未使用的

大致流程:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
from functools import wraps
import time


class Node(object):
def __init__(self, prev=None, next=None, key=None, value=None):
self.prev = prev
self.next = next
self.key = key
self.value = value

# 使用循环双端链表,做到O(1)的删除和添加
class CircularDoubleLinkList(object):
def __init__(self):
self.root_node = Node()
self.root_node.prev, self.root_node.next = self.root_node, self.root_node

def head_node(self):
return self.root_node.next

def tail_node(self):
return self.root_node.prev

def append(self, node):
tail_node = self.tail_node()
tail_node.next = node
node.prev = tail_node
node.next = self.root_node
self.root_node.prev = node

def remove(self, node):
if node is self.root_node:
return
node.prev.next = node.next
node.next.prev = node.prev


class LRUCache(object):
def __init__(self, max_size=16):
self.max_size = max_size
self.cache = {}
self.access = CircularDoubleLinkList()

def is_full(self):
return len(self.cache) >= self.max_size

def __call__(self, func):
@wraps(func)
def wrapper(n):
if n in self.cache: # 在缓存中
node = self.cache[n]
self.access.remove(node)
self.access.append(node)
res = node.value
else: # 不在缓存中
new_value = func(n)
res = new_value
new_node = Node(key=n, value=new_value)
self.cache[n] = new_node

if self.is_full(): # 缓存full
rm_node = self.access.head_node()
self.access.remove(rm_node)
del self.cache[rm_node.key]
self.access.append(new_node)
return res
return wrapper

@LRUCache()
def fib_use_lrucache(n):
if n <= 2:
return 1
return fib_use_lrucache(n - 1) + fib_use_lrucache(n - 2)

def fib_none_cache(n):
if n <= 2:
return 1
return fib_none_cache(n - 1) + fib_none_cache(n - 2)

def main():
# none cache
print('none cache')
start_time = time.time()
for i in range(1, 30):
print(fib_none_cache(i))
end_time = time.time()
print('cost time:{}'.format(end_time - start_time))
print('-' * 30)

# use lrucache
print('use lrucache')
start_time = time.time()
for i in range(1, 30):
print(fib_use_lrucache(i))
end_time = time.time()
print('cost time:{}'.format(end_time - start_time))


if __name__ == '__main__':
main()
-------------本文结束感谢您的阅读-------------

本文标题:使用缓存优化斐波那契

文章作者:Longofo

发布时间:2018年06月15日 - 20:06

最后更新:2018年06月15日 - 20:06

原始链接:http://longofo.cc/使用缓存优化斐波那契.html

许可协议: 署名-非商业性使用-禁止演绎 4.0 国际 转载请保留原文链接及作者。

请我吃包辣条也好啊!!!
分享到: