Back to blog
Jul 02, 2014
8 min read


Python算法设计篇(2) Chapter 2: The basics

Tracey: I didn’t know you were out there.
Zoe: Sort of the point. Stealth—you may have heard of it.
Tracey: I don’t think they covered that in basic.
—— From “The Message,” episode 14 of Firefly



图灵机模型(Turing machine): A Turing machine is a simple (abstract) device that can read from, write to, and move along an infinitely long strip of paper. The actual behavior of the machines varies. Each is a so-called finite state machine: it has a finite set of states (some of which indicate that it has finished), and every symbol it reads potentially triggers reading and/or writing and switching to a different state. You can think of this machinery as a set of rules. (“If I am in state 4 and see an X, I move one step to the left, write a Y, and switch to state 9.”)

RAM模型(random-access machine):标准的单核计算机,它大致有下面三个性质

• We don’t have access to any form of concurrent execution; the machine simply executes one instruction after the other.


• Standard, basic operations (such as arithmetic, comparisons, and memory access) all take constant (although possibly different) amounts of time. There are no more complicated basic operations (such as sorting).


• One computer word (the size of a value that we can work with in constant time) is not unlimited but is big enough to address all the memory locations used to represent our problem, plus an extra percentage for our variables.


算法的本质: An algorithm is a procedure, consisting of a finite set of steps (possibly including loops and conditionals) that solves a given problem in finite time.

the notion of running time complexity (as described in the next section) is based on knowing how big a problem instance is, and that size is simply the amount of memory needed to encode it.




算法导论介绍到,对于三个符号可以做如下理解:$O$ = $\le$,$\Omega$ = $\ge$, $\Theta$ = $=$


几种常见的运行时间以及算法实例 点击这里可以参考下wiki中的时间复杂度



(1)Tip 1: If possible, don’t worry about it.


(2)Tip 2: For timing things, use timeit.


timeit.timeit("x = sum(range(10))")


(3)Tip 3: To find bottlenecks, use a profiler.

使用cProfile模块来获取更多的关于运行情况的内容,从而可以发现问题的瓶颈,如果系统没有cProfile模块,可以使用profile模块代替,关于这两者的更多内容可以查看Python standard library-Python Profilers

import cProfile
import re're.compile("foo|bar")')


         194 function calls (189 primitive calls) in 0.000 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.000    0.000    0.000    0.000 <string>:1(<module>)
        1    0.000    0.000    0.000    0.000
        1    0.000    0.000    0.000    0.000
        1    0.000    0.000    0.000    0.000
        1    0.000    0.000    0.000    0.000

(4)Tip 4: Plot your results.



(5)Tip 5: Be careful when drawing conclusions based on timing comparisons.


First, any differences you observe may be because of random variations.


Second, there are issues when comparing averages.


At the very least, you should stick to comparing averages of actual timings. A common practice to get more meaningful numbers when performing timing experiments is to normalize the running time of each program, dividing it by the running time of some standard, simple algorithm. This can indeed be useful but can in some cases make your results less than meaningful. See the paper “How not to lie with statistics: The correct way to summarize benchmark results” by Fleming and Wallace for a few pointers. For some other perspectives, you could read Bast and Weber’s “Don’t compare averages,” or the more recent paper by Citron et al., “The harmonic or geometric mean: does it really matter?”

Third, your conclusions may not generalize.

最后,你的结论未必适用于一般情况 (感谢评论者@梁植华的翻译建议)

(6)Tip 6: Be careful when drawing conclusions about asymptotics from experiments.

在对从实验中得到关于渐近时间的信息下结论时需要小心,实验只是对于理论的一个支撑,可以通过实验来推翻一个渐近时间结果的假设,但是反过来一般不行 [以下是作者的解释]

If you want to say something conclusively about the asymptotic behavior of an algorithm, you need to analyze it, as described earlier in this chapter. Experiments can give you hints, but they are by their nature finite, and asymptotics deal with what happens for arbitrarily large data sizes. On the other hand, unless you’re working in theoretical computer science, the purpose of asymptotic analysis is to say something about the behavior of the algorithm when implemented and run on actual problem instances, meaning that experiments should be relevant.


Python中很多地方都使用了hash策略,在前面的Python数据结构篇中的搜索部分已经介绍了hash的内容。Python提供了hash函数,例如hash("Hello, world!")得到-943387004357456228 (结果不一定相同)。Python中的dict和set都使用了hash机制,所以平均情况下它们获取元素都是常数时间的。

(1)图的表示:最常用的两种表示方式是邻接表和邻接矩阵 [假设要表示的图如下]


邻接表 Adjacency Lists


① adjacency lists 表示形式

# A Straightforward Adjacency List Representation
a, b, c, d, e, f, g, h = range(8)
N = [
    [b, c, d, e, f],    # a
    [c, e],             # b
    [d],                # c
    [e],                # d
    [f],                # e
    [c, g, h],          # f
    [f, h],             # g
    [f, g]              # h

b in N[a] # Neighborhood membership -> True
len(N[f]) # Degree -> 3

② adjacency sets 表示形式

# A Straightforward Adjacency Set Representation
a, b, c, d, e, f, g, h = range(8)
N = [
    {b, c, d, e, f},    # a
    {c, e},             # b
    {d},                # c
    {e},                # d
    {f},                # e
    {c, g, h},          # f
    {f, h},             # g
    {f, g}              # h

b in N[a] # Neighborhood membership -> True
len(N[f]) # Degree -> 3

基本上和adjacency lists表示形式一样对吧?但是,对于list,判断一个元素是否存在是线性时间$O(N(v))$,而在set中是常数时间$O(1)$,所以对于稠密图使用adjacency sets要更加高效。

③ adjacency dicts 表示形式,这种情况下如果边是带权值的都没有问题!

# A Straightforward Adjacency Dict Representation
a, b, c, d, e, f, g, h = range(8)
N = [
    {b:2, c:1, d:3, e:9, f:4},    # a
    {c:4, e:3},                   # b
    {d:8},                        # c
    {e:7},                        # d
    {f:5},                        # e
    {c:2, g:2, h:2},              # f
    {f:1, h:6},                   # g
    {f:9, g:8}                    # h

b in N[a] # Neighborhood membership -> True
len(N[f]) # Degree -> 3
N[a][b] # Edge weight for (a, b) -> 2


N = {
    'a': set('bcdef'),
    'b': set('ce'),
    'c': set('d'),
    'd': set('e'),
    'e': set('f'),
    'f': set('cgh'),
    'g': set('fh'),
    'h': set('fg')

邻接矩阵 Adjacency Matrix


# An Adjacency Matrix, Implemented with Nested Lists
a, b, c, d, e, f, g, h = range(8)
N = [[0,1,1,1,1,1,0,0], # a
     [0,0,1,0,1,0,0,0], # b
     [0,0,0,1,0,0,0,0], # c
     [0,0,0,0,1,0,0,0], # d
     [0,0,0,0,0,1,0,0], # e
     [0,0,1,0,0,0,1,1], # f
     [0,0,0,0,0,1,0,1], # g
     [0,0,0,0,0,1,1,0]] # h

N[a][b] # Neighborhood membership -> 1
sum(N[f]) # Degree -> 3


a, b, c, d, e, f, g, h = range(8)
_ = float('inf')

W = [[0,2,1,3,9,4,_,_], # a
     [_,0,4,_,3,_,_,_], # b
     [_,_,0,8,_,_,_,_], # c
     [_,_,_,0,7,_,_,_], # d
     [_,_,_,_,0,5,_,_], # e
     [_,_,2,_,_,0,2,2], # f
     [_,_,_,_,_,1,0,6], # g
     [_,_,_,_,_,9,8,0]] # h

W[a][b] < inf # Neighborhood membership
sum(1 for w in W[a] if w < inf) - 1  # Degree


(2)树的表示 [假设要表示下面的树]



T = [["a", "b"], ["c"], ["d", ["e", "f"]]]
T[2][1][0]  # 'e'


# A Binary Tree Class 二叉树实例
class Tree:
    def __init__(self, left, right):
        self.left = left
        self.right = right

t = Tree(Tree("a", "b"), Tree("c", "d"))
t.right.left  # 'c'


# 左孩子,右兄弟 表示方式
class Tree:
    def __init__(self, kids, next=None): = self.val = kids = next
return Tree

t = Tree(Tree("a", Tree("b", Tree("c", Tree("d")))))  # 'c'

[Bunch Pattern]:有意思的是,上面的实现方式使用了Python中一种常用的设计模式,叫做Bunch Pattern,貌似来自经典书籍Python Cookbook,原书介绍如下:[因为这个不太好理解和翻译,还是原文比较有味]

When prototyping (or even finalizing) data structures such as trees, it can be useful to have a flexible class that will allow you to specify arbitrary attributes in the constructor. In these cases, the “Bunch” pattern (named by Alex Martelli in the Python Cookbook) can come in handy. There are many ways of implementing it, but the gist of it is the following:

class Bunch(dict):
    def __init__(self, *args, **kwds):
        super(Bunch, self).__init__(*args, **kwds)
        self.__dict__ = self
return Bunch

There are several useful aspects to this pattern. First, it lets you create and set arbitrary attributes by supplying them as command-line arguments:

>>> x = Bunch(name="Jayne Cobb", position="Public Relations")
'Jayne Cobb'

Second, by subclassing dict, you get lots of functionality for free, such as iterating over the keys/attributes or easily checking whether an attribute is present. Here’s an example:

>>> T = Bunch
>>> t = T(left=T(left="a", right="b"), right=T(left="c"))
>>> t.left
{'right': 'b', 'left': 'a'}
>>> t.left.right
>>> t['left']['right']
>>> "left" in t.right
>>> "right" in t.right

This pattern isn’t useful only when building trees, of course. You could use it for any situation where you’d want a flexible object whose attributes you could set in the constructor.


• NetworkX:
• python-graph:
• Graphine:
• Pygr: a graph database
• Gato: a graph animation toolbox
• PADS: a collection of graph algorithms


In general, the more important your program, the more you should mistrust such black boxes and seek to find out what’s going on under the cover.


(1)Hidden Squares 隐藏的平方运行时间


from random import randrange
L = [randrange(10000) for i in range(1000)]
42 in L # False
S = set(L)
42 in S #False

(2)The Trouble with Floats 精度带来的烦恼


sum(0.1 for i in range(10)) == 1.0 # False


def almost_equal(x, y, places=7):
    return round(abs(x-y), places) == 0

almost_equal(sum(0.1 for i in range(10)), 1.0) # True


from decimal import *
sum(Decimal("0.1") for i in range(10)) == Decimal("1.0")  # Ture


sage: 3/5 * 11/7 + sqrt(5239)
13*sqrt(31) + 33/35

更多和Python中的浮点数有关的内容可以查看Floating Point Arithmetic: Issues and Limitations

问题2-12. (图的表示)

Consider the following graph representation: you use a dictionary and let each key be a pair (tuple) of two nodes, with the corresponding value set to the edge weight. For example W[u, v] = 42. What would be the advantages and disadvantages of this representation? Could you supplement it to mitigate the downsides?

The advantages and disadvantages depend on what you’re using it for. It works well for looking up edge weights efficiently but less well for iterating over the graph’s nodes or a node’s neighbors, for example. You could improve that part by using some extra structures (for example, a global list of nodes, if that’s what you need or a simple adjacency list structure, if that’s required).