Python小书2-趣解Python数据结构

这一节，开始进入最基础的部分：数据结构，依然按照之前的思路，闲话少叙，例子引入，慢慢深入。

1.线性存储

首先我们先看一段代码，之前我们已介绍了基本的列表存储成绩的例子，所以下面的代码应该不陌生。

看一下运行结果吧。

同样是10万个数值，我们从头开始插入花了8.38秒，而从尾开始插入却只花了0.028秒

现在知道了吧，列表List可没有你想象中那么简单，要解释这个现象，这就要牵扯到List列表的底层数据结构了，且听我慢慢说来。

计算机中，存储像列表这种多个数据的线性存储结构，有两种实现方式

• 顺序存储（一个萝卜一个坑）
• 链式存储（大金链子串起来）

顺序存储， 简单点说就是一个萝卜一个坑，一个坑挨着一个坑，要添加新的成员，先要挖坑，而且只能从后面挖，再种新萝卜。

链式存储 ，简单点说就是黄金大项链，一个锁链连着另一个锁链，要添加新成员，只要把新的锁链扣上即可，两边都一样。

这两种底层存储结构，就会在不同角度限制列表的工作效率。

根据前面的代码测试结果，现在想一想，我们Python中的列表用的哪一种数据存储结构呢？？

静静地想一想吧。。。。我先去撸个串

链式存储的话，从开头还是从结尾去接，都没啥区别，本来项链就是两端对称的，所以从前面还是从后面添加新元素执行效果是一样的。

但是顺序存储不一样，因为挖这个坑，只能朝着一个方向，从后面挖，所以从头添加和从尾添加是不一样的。从尾部种萝卜的话，新挖一个坑直接种就可以，或者预先挖出很多坑，然后挨着种萝卜就可以。但是从头添加成员的话，就很麻烦，因为没办法从前面挖坑，所以只能从后面挖坑，然后把之前所有的萝卜整体往后错一个坑位，最后在最开始空出来的坑里，种上新的萝卜。

于是从头插入，所有的萝卜都要移位：

而从尾插入，只要在最后添加即可

这就是为什么，前面的代码用insert要花8秒，而用append只需要花0.028s的原因。

Python中的列表选用的是顺序存储结构，这就决定了它，插入删除元素慢，索引第几个元素快。

像一些高级语言Java针对这两种存储结构，分别设计了顺序存储的ArrayList和链式存储的LinkedList。

列表我们就讲到这里，有一张图，我觉得可以放出来了，就是针对列表list的每个操作，都有对应的时间复杂度。

时间复杂度是什么玩意呢，就是做这个操作花费的时间跟元素总数是怎样一个增长趋势关系，如果O(1)就说明，这个操作的时间跟列表的总元素个数无关，不管列表多长，操作时间都是常数时间，如果是O(n)，这个操作的时间跟列表的总元素个数n就成线性关系，列表越长，操作时间也就越长。

append的为时间复杂为O(1)，就意味着，1个元素的列表插入append，还是100万元素的列表插入append，花费的时间都是一样的。

而insert的时间复杂为O(n)，这就意味着，100万个元素的列表从头insert比1个元素的时间要多花接近100万倍的时间。

我这里，不想一个个去重复讲每个操作是用来做什么的，因为自己随便找本书，跟着走一下就好，但是一定要强调，上面这张表才是关键，最好是印在脑海里。

如果确实有应用场合，需要首尾两个方向都要添加元素，请用双端队列deque，因为这个的底层存储结构是链式存储。

2.集合与字典

有时候，我们存储数据，我们关心存储的顺序用列表去存储，但是像有一些场合，更关心一个数据集的内容，

比如一篇文章有没有出现一个词，以及这个词的含义，
产品集里有没有这个产品，以及产品的介绍，
这部字典里有没有收录这个单词，以及对应单词的解释？

如果只关注有没有出现，那就是集合Set，如果除了关注有没有，还关注具体的内容，那就是字典Dict。本质上这两个是一样的，只不过字典多存了一个具体内容。

像这种情况，就会频繁做类似列表里的contains是否包含这个元素的操作，在列表List里，我们只能一个挨着一个去找，不断地翻个底朝天，才能说到底有没有包含这个元素，于是我们可以看到列表的Contain操作的时间复杂度为O(n)，这个的意思，就是有n个元素，那就要操作n遍。

那有没有办法，能把这个时间复杂度O(n)优化呢？

有呀，当然有，只不过要修改底层的数据结构

优化有两种玩法：

• 哈希方式（将内容散列与位置对应，方便查找）
• 树形结构（根据内容权重构建树形结构，方便查找）

容我画画图哈，这样更形象一点。

线性表 是挨家挨户去问，所有的元素都遍历一遍。

哈希结构 是根据内容直接找到对应位置，然后看这个位置有没有对应元素，空位就是不包含，有对应元素就是包含，这个时间复杂度是常数时间O(1)。

树形结构 的话，首先要对数据建立树形结构起来，然后最常用的就是二叉树，就是每个树枝只分两个叉，这样的话，没经过一个树枝，就会告诉你，在左叉还是右叉上，直到找到最终的元素。原来线性表要扫描所有的元素，到了树形结构，只要要扫描树的深度个元素就可以了。这个时间取决于树的深度O(log(n)）

这时候，我们再看Python自带的集合和字典Dict的时间复杂度，就可以分析出他们底层用的哪种存储结构。

集合Set

字典Dict

从集合Set的x in s的平均时间复杂度为O(1)，字典Get Item的平均时间复杂度为O(1)，都可以知道，判断包不包含一个元素的时间复杂度都是常数时间，也就是都选用的哈希结构！

到此为止，Python中的数据结构部分，就讲解完了。

对于数据结构感兴趣的同学，我觉得可以看看Java内置的数据结构类型，很全面和具体，可以看看我之前画的Java内置数据结构的思维导图。

不过推荐一本书，我自己学的话，当初也是通过这本书学的，只不过他是C语言版的

有一本Python版的很好，但是没有中文版

然后可以看看这个问题

3。附加时间测试

在数据结构这块，我觉得，有一步很重要，就是测试不同时间复杂度代码的时间区别，用直观的方式去感受代码时间复杂度带来时间效率上的差异。

这块一定要动手做，才能找到感觉！！！

所以这里简单说一下如何测试一段Python代码的执行时间。

第一版，就是我们最开始的方式

如果测试别的代码，你第一个念头是会复制一遍，然后改动，如果测试10几个呢，你会发现你的代码越来越长。。。。。。比如

有没有办法，优化这些代码，去掉重复代码呢？？？

当然有啦

优化方案1 ：封装函数

因为所有测试代码的start=和end=等于都是相同的，所以可以把这部分抽离出来建立函数time_it，示例代码如下，将要测试的代码封装为函数，作为参数传给time_it。

优化方案2 ：使用闭包

其实优化方案1的升级版，就是闭包，闭包带来的好处就是，在测试函数的前面加一句@time_it，就搞定了，闭包的结构和封装函数很像。

优化方案3 ：使用匿名函数

如果要测试的多个操作很类似，只修改一小小部分代码，那可以用匿名函数玩，具体示例如下。

优化方案4 ：使用timeit模块

Python的库提供了专门用于测试代码时间的模块timeit，直接使用即可，示例代码如下。

Timer("test()","from __ main __ import test")

这句话的意思第一个参数是执行test函数，第二个参数意思是从当前的__ main _ 模块引入test函数，所有当前运行的模块默认有一个名字叫_ _ main __.

t1.timeit(numer=10)的意思是重复执行10次。

诸位可以根据自己的需要选择合适的测试时间的方式，timeit还是比较好用的。