微信公众号：geekkr

本文目录：一、计时模块；二、字典与散哈希表；三、图与树的实现；四、成员查询；五、插入对象</br>一、计时模块（timeit、cProfile）

import timeittimeit.timeit('x = 1 + 2')

既然学习算法，那么来计算程序所耗费的时间是重要的，但是需要注意：timeit()计时函数会多次运行相关的代码段并求得平均值，以提高计时的精准度，所以，我们需要预防早先的执行操作影响之后代码的执行。举个栗子：若我们执行排序算法，则只有第一次执行代码时是在随机的情况下计时，剩余的数千次运行则都在有序列表的前提下运行，这会导致最终的计时结果偏低。所以，可以尝试使用cProfile模块。

import cProfilecProfile.run('函数名'）

cProfile（或profile）能够将各函数的计时结果打印出来。

</br></br></br>二、字典与散哈希表（hashing）哈希表（Hash table，也叫散列表），是根据关键码值(Key value)而直接进行访问的数据结构。也就是说，它通过把关键码值映射到表中一个位置来访问记录，以加快查找的速度。这个映射函数叫做散列函数，存放记录的数组叫做散列表。可以猜到，哈希表被用于Python中字典（dict）类型与集合（set）类型的实现，且我们对其元素的访问也只是耗费常数级的时间。而Python中的hash()函数则用于获取一个对象（字符串或者数值等）的哈希值。</br></br></br>三、图与树的实现邻接列表可以视为图结构的表达方式。

# 举个邻接列表的栗子a, b, c, d, e, f, g, h = range(8)N = [    {b, c, d, e, f}, # a节点所指向的节点，如果想要加权则利用字典类型改为{b:2, c:1, …}    {c, e}, # b …    {d},    {e},    {f},    {c, g, h},    {f, h},    {f, g}]b in N[a]len(N[f])N[a][b]

同时，邻接矩阵也是图的一种常见的表示方式。

# 举个邻接矩阵的栗子a, b, c, d, e, f, g, h = range(8)N = [[0,1,1,1,1,1,0,0],     [0,0,1,0,1,0,0,0],     [0,0,0,1,0,0,0,0],     [0,0,0,0,0,1,0,0],     [0,0,1,0,0,0,1,1],     [0,0,0,0,0,1,0,1],     [0,0,0,0,0,1,1,0]]N[a][b] # Neighborhood membership, answer is 1sum(N[f]) # Degree, answer is 3

二叉树的表示方式。

class Tree：    def __init__(self, left, right):        self.left = left        self.right = rightt = Tree(Tree('a', 'b'), Tree('c', 'd'))t.right.left # answer is 'c'

多路搜索树的表达方式。

class Tree:    def __init__(self, kids, next=None):        self.kids = kids        self.next = nextt = Tree(Tree('a', Tree('b', Tree('c', Tree('d')))))t.kids.next.next.kids # answer is 'c'

</br>

</br></br>四、成员查询

from random import randrangeL = [randrange(10000) for i in range(1000)]1 in L # 第一种查询操作S = set(L)1 in S # 第二种查询操作

看起来第二种查询操作多此一举，但要知道，在数列中查询成员所耗费的时间是线性级的，而在集合中则是常数级的。

</br></br></br>五、插入对象

# 比较两段代码# 第一段代码s = ''"for chunk in string_producer():    s += chunk# 第二段代码chunks = []for chunk in string_producer():    chunks.append(chunk)s = ' '.join(chunks)

相比较之下，第二段代码是更为高效的解决方案。因为在执行第一段代码时，我们每次执行“+=”时都需要新建一个字符串并对其进行转移性质的赋值，以至于其时间复杂度为平方级。同样，在对数列进行相加操作时，使用extend()函数要比sum()函数高效得多。