为啥我的Python这么慢 - 项查找 (二)

上一篇为啥我的Python这么慢, 字符串的加和和join被陈群主分享到biopython-生信QQ群时,乐平指出字典的写法存在问题,并给了一篇知乎的链接https://zhuanlan.zhihu.com/p/28738634指导如何高效字典操作。

根据那篇文章改了两处写法,如下:

from collections import defaultdict

aDict = 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。一个是使用了defaultdict初始化字典,另外一个是用iteritems遍历字典,节省近一半的内存。

defaultdict用在这效果不太明显,之前处理全基因组每个位点数据的频繁存取时,defaultdict在程序无论速度还是写法上都有很大提升。

time python readFaJoin2.py

real	0m49.114s
user	0m38.442s
sys	0m10.565s

字典本身还有更多高效用法,可以去参考知乎的那篇文章。这儿介绍的是妙用字典的哈希属性快速查找项。

在生信操作中,常常会在一个大矩阵中匹配已小部分基因或位点,提取关注的基因或位点的信息。最开始的写法是:

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

后来,随着数据量变大,发现这个速度并不快,于是换了下面的方式

targetL = ['a', 'n', 'c', 'd']
targetD = dict.fromkeys(targetL, 0)

if item in targetD:
	other_operations

又可以愉快的查询了。

为什么呢?

这是因为:在Pyhton中列表的查询时间复杂度是O(n)(n是列表长度);字典的查询负责度是O(1)(与字典长度无关)。

字典的查询复杂度为什么是O(1)呢? Python中实现了一个hash函数,把字典的key转换为哈希值,组成连续地址的数字哈希表。字典的每次查询转换为了从数组特定位置取出一个元素,所以时间复杂度为O(1)

后来发现pythonset也是用hash table存储,所以上面的程序,可以更简化而不影响速度。

targetS = set(['a', 'n', 'c', 'd'])

if item in targetS:
	other_operations

那么速度到底差多大,有没有直观一些的展示呢? 这是StackOverflow的一个简化例子, 百万倍速度差异。

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:

CHENTONG
版权声明:本文为博主原创文章,转载请注明出处。
alipay.png WeChatPay.png

CHENTONG

CHENTONG
积微,月不胜日,时不胜月,岁不胜时。凡人好敖慢小事,大事至,然后兴之务之。如是,则常不胜夫敦比于小事者矣!何也?小事之至也数,其悬日也博,其为积也大。大事之至也希,其悬日也浅,其为积也小。故善日者王,善时者霸,补漏者危,大荒者亡!故,王者敬日,霸者敬时,仅存之国危而后戚之。亡国至亡而后知亡,至死而后知死,亡国之祸败,不可胜悔也。霸者之善著也,可以时托也。王者之功名,不可胜日志也。财物货宝以大为重,政教功名者反是,能积微者速成。诗曰:德如毛,民鲜能克举之。此之谓也。

生信宝典文章集锦

### 系列教程* [生物信息之程序学习](http://mp.weixin.qq.com/s/xoLBg0pI9seEksa0hMXi0A)* [如何优雅的提问](http://mp.weixin.qq.com/s?__biz=MzI5MTcwNjA4NQ==&m...… Continue reading