大展身手的字典树

简单字典树(Trie)的实现一文中,我们以单词输入自动提示为引子,简单介绍了字典树的实现。那么,字典树到底可以用于哪些场合呢?

  1. 前缀匹配:给定字典库,输入一段字符,返回以该字符串为前缀的所有单词。
  2. 字频统计:给出一段文本,统计其中指定单词出现的频数。

阅读更多

python装饰器详解

之前用python简单写了一下斐波那契数列的递归实现(如下),发现运行速度很慢。

1
2
3
4
5
6
def fib_direct(n):
assert n > 0, 'invalid n'
if n < 3:
return n
else:
return fib_direct(n - 1) + fib_direct(n - 2)

然后大致分析了一下fib_direct(5)的递归调用过程,如下图:

递归调用

可以看到多次重复调用,因此效率十分低。进一步,可以算出递归算法的时间复杂度。T(n) = T(n-1) + T(n-2),用常系数线性齐次递推方程的解法,解出递推方程的特征根,特征根里最大的n次方就是它的时间复杂度O(1.618^n),指数级增长。

为了避免重复调用,可以适当地做缓存,python的装饰器可以完美的完成这一任务。

阅读更多

操作之灵魂——拷贝

首先需要搞清楚两个概念:赋值引用,对于操作 target = source:

  1. 赋值操作:程序先新建对象target,然后将source的值拷贝到target中。这里,target和source值相同,但是它们是两个完全不同的对象。

  2. 引用操作:程序直接将target指向source,也就是说target和source是同一个对象,target只不过是source的一个别名。

python中没有赋值,只有引用。

1
2
3
4
>>> source = 12
>>> target = source
>>> target is source
True

如果我们想拷贝一个对象,而不仅仅是创建一个引用,那么该如何操作呢?万能的python提供了两种拷贝机制浅拷贝(shallow copy)、深拷贝(deep copy)供我们选择,浅拷贝和深拷贝的唯一区别在于对嵌套对象的拷贝处理上。

Function Description
copy.copy(x) Return a shallow copy of x.
copy.deepcopy(x) Return a deep copy of x.
exception copy.error Raised for module specific errors.

阅读更多