从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(set(list))

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

字符

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

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

推荐阅读:
深入读了读python的官方文
尽管现在有了wheel这类更为
gearman,学习好莱坞大片

发表评论

电子邮件地址不会被公开。 必填项已用*标注

请补全下列算式: *

此站点使用Akismet来减少垃圾评论。了解我们如何处理您的评论数据