在面向对象中，继承是非常重要的特性，有了继承我们才可以提取公共代码，实现多层抽象。
作为程序员通常不需要考虑依赖关系，这是编译器做的事。不过在这个Kata中，我们要模拟一回编译器，统计一下依赖关系。
假设有如下输入数据：
A B C
B C D
我们的程序应该输出每个类的所有依赖类：
A B C D
B C D
思路
最直接的思路就是根据输入存储每个类的直接依赖类，最后输出的时候通过递归来遍历出所有依赖类。这一步的代码比较简单我就不贴了，有一个需要注意的细节就是要去掉重复结果，我直接用了Python的set来做。
小坑
写完第一步之后，请用下面的数据测试一下：
A B
B C
C A
你的程序能正常处理吗？还是进入死循环了呢？
这个坑乍一看非常明显，但是真正思考问题的时候往往会忽略掉。
改动也很简单，我的做法是加入结果集的时候判断集合中是否已经有这个类，如果有就说明产生循环，直接返回。
万能cache
作者在这个Kata的最后提出了一个问题：处理规模巨大的数据时如何提高性能？
我思考了一下，由于依赖关系非常复杂，找出高性能的算法似乎并不可行，在遍历之前我们根本不知道依赖关系，因此也无法找出最优的遍历路线；而遍历之后我们已经得到了结果，这时即使找到最优遍历路线也已经没用了。另一种思路是在读输入数据的时候不断更新结果，但是这也是不现实的，因为计算结果就需要遍历之前的所有内容，这样每次读入新数据都需要遍历一次之前的所有内容，速度反而不如最后直接计算。
最后，我想到了简单好用的cache，数据很多的时候遍历过程必然会遍历很多共同节点，因此利用cache可以保证不重复计算，可以显著提高效率。Python中的cache可以用装饰器实现，非常方便。
直接上代码：
from functools import wraps
depMap = {}
def add(name, deps):
depMap[name] = deps.split()
def cache(func):
caches = {}
@wraps(func)
def wrap(*args):
if args[0] not in caches:
caches[args[0]] = func(*args)
return caches[args[0]]
return wrap
@cache
def listDeps(name, result):
result.append(name)
for dep in depMap[name]:
if dep in depMap and dep not in result:
result.append(dep)
listDeps(dep, result)
return result
add("A", "B")
add("B", "C")
add("C", "A")
print list(set(listDeps("C", [])))
这里我只输出了C的依赖，其他的同理。
问题
cache是万能的吗？显然不是，由于cache是内存存储，数据量巨大的时候可能导致内存耗尽，所以如果真的要应用在海量数据上，必须实现cache的淘汰算法，保证能在限量内存下运行，常见的算法无非就是什么淘汰最少使用啊淘汰最早内容啊，大家去搜一下就知道了。
Kata已经接近尾声了，虽然不是什么大工程，不过还是有不少收获，等全部做完我会写一篇心得。
