上一篇為啥我的Python這么慢, 字符串的加和和join被陳群主分享到biopython-生信QQ群時(shí)，樂(lè)平指出字典的寫法存在問(wèn)題，并給了一篇知乎的鏈接https://zhuanlan.zhihu.com/p/28738634指導(dǎo)如何高效字典操作。

根據(jù)那篇文章改了兩處寫法，如下 (存儲(chǔ)于readFaJoin2.py文件中)：

from collections import defaultdictaDict = defaultdict(list)for line in open("GRCh38.fa"):if line[0] == '>':key = line[1:-1]else:aDict[key].append(line.strip())
#----------------------------------------
for key, value in aDict.iteritems():aDict[key] = ''.join(value)

比之前提速接近2s。一個(gè)是使用了defaultdict初始化字典，另外一個(gè)是用iteritems遍歷字典，節(jié)省近一半的內(nèi)存。

time python readFaJoin2.pyreal ? ?0m49.114s
user ? ?0m38.442s
sys ? ?0m10.565s

defaultdict用在這效果不太明顯，之前處理全基因組每個(gè)位點(diǎn)數(shù)據(jù)的頻繁存取時(shí)，defaultdict在程序無(wú)論速度還是寫法上都有很大提升。

字典本身還有更多高效用法，可以去參考知乎的那篇文章。這兒介紹的是妙用字典的哈希屬性快速查找項(xiàng)。

在生信操作中，常常會(huì)在一個(gè)大矩陣中匹配已小部分基因或位點(diǎn)，提取關(guān)注的基因或位點(diǎn)的信息。最開始的寫法是：

targetL = ['a', 'n', 'c', 'd']
if item in targetL:other_operations

后來(lái)，隨著數(shù)據(jù)量變大，發(fā)現(xiàn)這個(gè)速度并不快，于是換了下面的方式

targetL = ['a', 'n', 'c', 'd']
targetD = dict.fromkeys(targetL, 0)if item in targetD:other_operations

又可以愉快的查詢了。

為什么呢？

這是因?yàn)?#xff1a;在Pyhton中列表的查詢時(shí)間復(fù)雜度是O(n)(n是列表長(zhǎng)度)；字典的查詢負(fù)責(zé)度是O(1)(與字典長(zhǎng)度無(wú)關(guān))。

字典的查詢復(fù)雜度為什么是O(1)呢？ Python中實(shí)現(xiàn)了一個(gè)hash函數(shù)，把字典的key轉(zhuǎn)換為哈希值，組成連續(xù)地址的數(shù)字哈希表。字典的每次查詢轉(zhuǎn)換為了從數(shù)組特定位置取出一個(gè)元素，所以時(shí)間復(fù)雜度為O(1)。

后來(lái)發(fā)現(xiàn)python中set也是用hash table存儲(chǔ)，所以上面的程序，可以更簡(jiǎn)化而不影響速度。

targetS = set(['a', 'n', 'c', 'd'])if item in targetS:other_operations

那么速度到底差多大，有沒(méi)有直觀一些的展示呢? 這是StackOverflow的一個(gè)簡(jiǎn)化例子, 百萬(wàn)倍速度差異。

ct@ehbio:~$ python -mtimeit -s 'd=range(10**7)' '5*10**6 in d'

10 loops, best of 3:?182 msec?per loop

ct@ehbio:~$ python -mtimeit -s 'd=dict.fromkeys(range(10**7))' '5*10**6 in d'

10000000 loops, best of 3:?0.16 usec?per loop

ct@ehbio:~$ python -mtimeit -s 'd=set(range(10**7))' '5*10**6 in d'

10000000 loops, best of 3:?0.164 usec?per loop

Ref:

• 速度測(cè)試?yán)?https://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table

• python各數(shù)據(jù)結(jié)構(gòu)時(shí)間復(fù)雜度 https://wiki.python.org/moin/TimeComplexity