Python数据结构与算法--List和Dictionaries

Lists

当实现 list 的数据结构的时候Python 的设计者有很多的选择. 每一个选择都有可能影响着 list 操作执行的快慢. 当然他们也试图优化一些不常见的操作. 但是当权衡的时候，它们还是牺牲了不常用的操作的性能来成全常用功能.

本文地址：http://www.cnblogs.com/archimedes/p/python-datastruct-algorithm-list-dictionary.html，转载请注明源地址。

设计者有很多的选择，使他们实现list的数据结构。这些选择可能对如何快速列表操作的影响进行。帮助他们做出正确的选择，他们看着人们最常使用的 列表数据结构的方式和他们优化列表的实现，导致最常见的操作速度非常快。当然他们也试图优化不常见的操作，但当一个权衡不得不作一个不太常见的操作的性能 往往是牺牲在更常见的操作支持。

两种常见的操作的索引和分配给索引位置。不管列表多大这两个操作所需时间相同。称一个独立于list大小的操作时间复杂度为O(1).

另一个常见的编程操作是增长一个 list. 有两种方法来创建一个更长的list.你可以使用附加尾部的方法或串联运算符。附加的方法是O(1)。然而，连接操作是 O(k) 其中k是需要连接列表的尺寸。这对你很重要，因为它可以帮助你选择正确的工具的工作来使自己的节目更有效。

让我们看一下四种不同的方法构造一个包含 n 个数字起始为 0 的list. Listing 1 展示了list的四种不同的方法实现：

Listing 1

def test1():
    l = []
    for i in range(1000):
        l = l + [i]

def test2():
    l = []
    for i in range(1000):
        l.append(i)

def test3():
    l = [i for i in range(1000)]

def test4():
    l = list(range(1000))

想要计算每个函数的执行时间, 我们可以使用Python 的 timeit 模块. timeit 模块设计的目的是允许程序员在一致的环境下跨平台的测量时间.

要使用 timeit 你必须先创建一个 Timer 对象，参数为两个Python声明. 第一个参数是你想计算时间是函数声明; 第二个参数是设置测试的次数. timeit 模块将计算执行时间. timeit 默认情况下执行声明参数代表的操作100万次. 当它完成时将返回一个浮点类型的秒数. 然而,因为它执行声明一百万次，你可以将结果理解为每执行一次花费多少毫秒. 你还可以传递给 timeit 函数一个名叫 number 的参数，它可以允许你指定多少次测试语句来执行. 下面显示运行每一个测试函数1000次需要多长时间.

t1 = Timer("test1()", "from __main__ import test1")
print("concat ",t1.timeit(number=1000), "milliseconds")
t2 = Timer("test2()", "from __main__ import test2")
print("append ",t2.timeit(number=1000), "milliseconds")
t3 = Timer("test3()", "from __main__ import test3")
print("comprehension ",t3.timeit(number=1000), "milliseconds")
t4 = Timer("test4()", "from __main__ import test4")
print("list range ",t4.timeit(number=1000), "milliseconds")

concat  6.54352807999 milliseconds
append  0.306292057037 milliseconds
comprehension  0.147661924362 milliseconds
list range  0.0655000209808 milliseconds

上面是实验中，函数声明是 test1(), test2(), 等等. 设置的声明会让你感觉很怪, 所以让我们来深入理解一下.你可能很熟悉 from, import 语句, 但这通常是用在一个Python程序文件开始. 在这种情况下, from __main__ import test1 从 __main__命名空间将 test1 调入到 timeit 所在的命名空间.

关于这个小实验的最后提到的是, 你看到的关于调用也包含一定的开销时间, 但是我们可以假设, 函数调用的开销在所有四种情况下是相同的, 我们仍然可以得到比较有意义的操作比较结果. 所以不会说串联操作精确地需要6.54毫秒, 而说串联测试函数需要6.54毫秒.

从下表我们可以看到list中所有操作的 Big-O 效率。经过仔细观察，你可能想知道两个不同pop的执行时间的差异。当pop在list的尾部操作需要的时间复杂度为O(1), 当pop在list的头部操作需要的时间复杂度为O(n), 其原因在于Python选择如何实现列表。

为了演示性能上的不同，让我们使用 timeit模块做另一个实验. 我们的目的是能够证实在一个已知大小的list，从list的尾部和从list的头部上面 pop 操作, 我们还要测量不同list尺寸下的时间. 我们期望的是从list的尾部和从list的头部上面 pop 操作时间是保持常数，甚至当list的大小增加的时候, 然而运行时间随着list的大小的增大而增加.

下面的代码让我们可以区分两种pop操作的执行时间. 就像你看到的那样，在第一个例子中, 从尾部pop操作花费时间为0.0003 毫秒, 然而从首部pop操作花费时间为 4.82 毫秒. 

Listing 2

popzero = timeit.Timer("x.pop(0)",
                       "from __main__ import x")
popend = timeit.Timer("x.pop()",
                      "from __main__ import x")

x = list(range(2000000))
popzero.timeit(number=1000)
4.8213560581207275

x = list(range(2000000))
popend.timeit(number=1000)
0.0003161430358886719

上面的代码可以看到 pop(0)确实比 pop()效率低, 但没有验证 pop(0) 时间复杂度为 O(n) 然而 pop() 为 O(1). 要验证这个我们需要看一个例子同时调用一个list. 看下面的代码：

popzero = Timer("x.pop(0)",
                "from __main__ import x")
popend = Timer("x.pop()",
               "from __main__ import x")
print("pop(0)   pop()")
for i in range(1000000,100000001,1000000):
    x = list(range(i))
    pt = popend.timeit(number=1000)
    x = list(range(i))
    pz = popzero.timeit(number=1000)
    print("%15.5f, %15.5f" %(pz,pt))

Dictionaries

Python 第二个主要的数据结构是字典. 你可能记得, 词典不同于列表的是你可以通过关键字而不是位置访问字典中的项. 最重要的是注意获得键和值的操作的时间复杂度是O(1). 另一个重要的字典操作是包含操作. 查看键是否在字典中的操作也为 O(1). 所有的字典操作效率如下表所示：

我们最后的性能实验比较了包含了列表和字典之间的操作性能. 在 这个过程中我们将证实, 列表包含操作是O（N）词典的是O（1）.实验中我们将使用简单的比较. 我们会列出一包含一系列数据的list. 然后, 我们将随机选择数字并查看数据是否在 list中. 如果我们之前的结论正确, 随着list的容量的增大, 所需要的时间也增加.

我们将一个dictionary 包含相同的键做重复的实验. 在这个实验中，我们可以看到, 确定一个数是否在字典中不仅速度快得多, 而且检查的时间甚至不会随着字典容量的增加而改变.

下面的代码实现了这种比较. 注意我们执行相同非操作, number in container. 不同的是第7行 x 是一个list, 第9行 x 是一个dictionary.

import timeit
import random

for i in range(10000,1000001,20000):
    t = timeit.Timer("random.randrange(%d) in x"%i,
                     "from __main__ import random,x")
    x = list(range(i))
    lst_time = t.timeit(number=1000)
    x = {j:None for j in range(i)}
    d_time = t.timeit(number=1000)
    print("%d,%10.3f,%10.3f" % (i, lst_time, d_time))