你知道疯狂的字典吗？

你好，知道我是疯狂 somenzz，Python 的字典灵活程度让人发指，今天来分享一下关于字典的知道疯狂操作，计算斐波那契数列，疯狂话不多说，字典先看代码:

代码定义了一个类 FibDict，知道继承自 dict，疯狂自定义了魔术方法 __missing__ 当 dict 查找 key失败(missing)的字典时候，会由 Python 解释器自行调用改方法。知道换句话说，疯狂如果试图从 dict 中获取不存在的字典 key，就会执行这个方法。知道

因此计算 fib_dict[10] 就会执行这个方法，疯狂计算 fib_dict[9] 和 fib_dict[8]，服务器托管字典就这样递归，一直到 fib_dict[0]和 fib_dict[1]。

这是递归，但是字典是一种 hash 表，只要计算过的数据不会重复计算，因此效率非常高。

我们可以验证下计算 fib_dict[200] 的耗时：

可以看出连 1 毫秒都不到。

不过，递归虽爽，可不要贪杯哦，任何事情都有极限，1000 是递归的默认极限(sys.getrecursionlimit() ==1000)，高防服务器如果你直接计算 fib_dict[501] 就抛出 RecursionError 异常。

你可能有个小小的疑问，为什么递归的深度是 1000，但我调用 501 次就不行了呢?其实原因在于 __missing__ 调用了 __setitem__，__setitem__ 又调用了 __missing__，因此每个缺失的 key 其实调用了两次，所以超过 500 就会报错。

但是，字典是有记忆的，如果你这样调用它，永远不会出现递归的问题：

本文地址：http://www.bhae.cn/html/203a20199595.html