LeetCode 128 DFS解法中LRU缓存比字典查找更快的原因问询

1. 代码逻辑并不等价，重复元素导致解法2出现大量重复计算 #

LeetCode 128的测试用例允许输入数组包含重复元素，这是性能差距最主要的来源：

• 解法1的lru_cache会缓存所有dfs(num)的执行结果，同一个数值不管在数组里出现多少次，都只会执行一次递归计算，后续调用直接取缓存结果，总时间复杂度严格为O(n)。
• 解法2没有任何结果缓存逻辑，且遍历的是未去重的原始输入数组：假设某连续序列的起点数值x在数组中重复出现了k次，那么每次遍历到x时都会触发一次完整的dfs递归，每次递归都要走完整个连续序列的所有节点，时间复杂度直接退化为O(kL)*（L为对应连续序列的长度），重复度越高性能损耗越大。
  你可以尝试在解法2遍历前先对nums做去重处理，或者给dfs手动加字典缓存，性能会立刻大幅提升。

2. 底层实现效率存在量级差距 #

就算输入数组完全没有重复元素，解法1的速度也会更快：
functools.lru_cache是CPython内置的C语言扩展实现，缓存命中判断、结果读写的效率都远高于Python层手写的num-1 not in graph判断+纯Python递归的执行效率，原生C实现和纯Python代码的执行速度本身就有1~2个数量级的差距。 #

内容的提问来源于stack exchange，提问作者erickcgt