从Python的数据结构说起

正值毕业季，这些天一直忙于面试各个踏出校门的大学生。惯例性的，我会出一些看似很简单，但其实很刁钻的题目，主要是看看面试者的知识是否可以用“扎实”来形容。

对于Python来说，我习惯性的一个问题是“Python常用的dict, list, set数据结构有什么区别？”然后就是设定一个场景看看更适合什么结构实现之类的问题。谈不上是难题，但回答的结果有些大失所望。

作为自己给自己出的题目，我决定自己挑战一把。

Dict（或者说dictionary, 字典）

从字面上看得出，它是一系列key=>value的映射关系的集合，底层映射到hash map数据结构。Python（json）中可以通过{“key”: value}的方法快速建立一个dict，但Python要求key必须为一个str。

由于底层为hash map，根据key找到value的复杂度为O(1)。非常适合对于成员进行频繁的查找和更新操作。

最快速的耗尽内存的方法dict(zip(range(10**10), range(10**10)))

List（列表）

不定长的连续内存空间。访问时需要例编元素，所以查找元素的复杂度是O(n)。Python中可以使用[1,2,3]的方式快速建立list。可以用[i+1 for i in list]的方式（列表解析式）实现一个map操作。当然更为快速且变态的解析式是(i+1 for i in list)。

考虑到性能和资源的耗用，Python 2.4以后在在使用List的时候可以考虑使用yield等方式实现一个迭代器，迭代器并不会将所有元素加载到内存。

List 对象可以使用 * 和 + 操作

Set（无序队列）

表现非连续的内存空间，相对List来说，内存利用率高。要求内部元素不能重复。一般用来做数据的交差并补计算。可以用set(list)的方法将一个List转为一个Set。

List去重的快速方法是转成set再转回list(list(set(list)))

只有set对象默认就定义了+ – & | 操作。

字符

对于字符的操作，由于直接格式化系统上是直接调用了stdio的printf，性能上远好于字符串的+运算。

同理，字符串的join方法也是最高效的列表转字符的方式。