從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方法也是最高效的列表轉字符的方式。