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

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

根据那篇文章改了两处写法,如下 (存储于readFaJoin2.py文件中):

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遍历字典,节省近一半的内存。

time python readFaJoin2.py

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

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

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

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

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:

  • 速度测试例子 https://stackoverflow.com/questions/513882/python-list-vs-dict-for-look-up-table
  • python各数据结构时间复杂度 https://wiki.python.org/moin/TimeComplexity

原文发布于微信公众号 - 生信宝典(Bio_data)

原文发表时间:2017-10-10

本文参与腾讯云自媒体分享计划,欢迎正在阅读的你也加入,一起分享。

发表于

我来说两句

0 条评论
登录 后参与评论

相关文章

来自专栏用户2442861的专栏

近一个月的面试总结 分类:JAVA

本文转载自:http://blog.csdn.net/pistolove/article/details/46753275

13320
来自专栏老九学堂

老九学堂第二讲:编写第一个Java程序【原创】

第二讲涉及到的知识点 1Java的运行机制 2Java程序的结构 3熟悉Eclipse开发环境 回顾一下老九君讲的,还记得吗?Java源文件是以后缀为.jav...

39550
来自专栏walterlv - 吕毅的博客

.NET Core/Framework 创建委托以大幅度提高反射调用的性能

发布于 2018-02-07 09:45 更新于 2018-02...

9710
来自专栏小詹同学

Python系列之零——从零说起!!!

2017年可谓是人工智能元年,要问哪个行业最火,詹小白不敢确定,但要问哪个编程语言最热门,好吧,詹小白还是不敢说太满。但是!至少从舆论Pytho...

381100
来自专栏计算机视觉与深度学习基础

Leetcode 211 Add and Search Word - Data structure design

Design a data structure that supports the following two operations: void addWor...

20250
来自专栏Crossin的编程教室

【Python 第26课】 操作list

上周给list开了个头,知道了什么是list。假设我们现在有一个list: l = [365, 'everyday', 0.618, True] 除了用for...

371110
来自专栏lgp20151222

Java的常量接口思考,项目中的常量是放在接口里还是放在类里呢?

最近在看一本书 Java与模式,里面提了一句不建议使用常量接口,甚至举了个java源码的反例,

14310
来自专栏AI科技大本营的专栏

送书 | Python编程:从入门到实践

本文摘自《Python编程:从入门到实践》一书,本书是Amazon编程入门类榜首图书,是一本全面的Python编程从入门到实践教程,带领读者快速掌握编程基础知识...

642100
来自专栏沈唁志

如何提高PHP书写效率?提高PHP书写效率的几个示例

14940
来自专栏老马说编程

计算机程序的思维逻辑 (1)

程序大概是怎么回事 计算机就是个机器,这个机器主要由CPU、内存、硬盘和输入输出设备组成。计算机上跑着操作系统,如Windows或Linux,操作系统上运行着各...

212100

扫码关注云+社区

领取腾讯云代金券