python如何提高大量的字符串比较速度?
每个字符串长度都是23,只要前面20个字符就行,由于数据太大,我只传了五分之一,大神们可以挑战一下,有速度快的可以贴一下代码,让小弟拜读一下,谢谢! 下面是正式的问题:我现在有两个字符串数组,姑且称为candidates和bg_db,全部都是长度为20的短字符串,并且每个字符串的每个字符只有ATCG四种可能(没错!就是基因组序列啦!): candidates = [ 'GGGAGCAGGCAAGGACTCTG', 'GCTCGGGCTTGTCCACAGGA', '...', # 被你看出来啦,这些其实人类基因的片段 ] bg_db = [ 'CTGCTGACGGGTGACACCCA', 'AGGAACTGGTGCTTGATGGC', '...', # 这个更多,有十亿左右 ] 我的任务是对candidates的每一个candidate,找到bg_db中所有与其小于等于4个差异的记录, # 上面一条为candidate,即candidates的一个记录 # 中间|代表相同,*代表不相同 # 下面一条代表bg_db的一条记录 A T C G A T C G A T C G A T C G A T C G | | | | | | | | | | | | | | | | | | | | # 差异为0 A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G * | | | | | | | | | | | | | | | | | | | # 差异为1 T T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G * | | | * | | | | | | | | | | | | | | | # 差异为2 T T C G T T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G A T C G * | | | * | | | | | | * | | | | | | | | # 差异为3 T T C G T T C G A T C C A T C G A T C G A T C G A T C G A T C G A T C G A T C G * | | | * | | | | | | * | | | * | | | | # 差异为4 T T C G T T C G A T C C A T C A A T C G 我的问题是如果快速地找到:每一个candidate在bg_db中与之差异小于等于4的所有记录, def align(candidate, record_from_bg_db): mismatches = 0 for i in range(20): if candidate[i] != record_from_bg_db[i]: mismatches += 1 if mismatches >= 4: return False return True candidate = 'GGGAGCAGGCAAGGACTCTG' record_from_bg_db = 'CTGCTGACGGGTGACACCCA' align(candidate, record_from_bg_db) # 1.24微秒左右 # 总时间: 10000000 * 1000000000 * 1.24 / 1000 / 1000 / 60 / 60 / 24 / 365 # = 393 # 1千万个candidates,10亿条bg_db记录 # 耗时大约393年 # 完全无法忍受啊 我的想法是,bg_db是高度有序的字符串(长度固定,每个字符的可能只有四种),有没有什么算法,可以让candidate快速比较完所有的bg_db,各位大神,求赐教。 补充数据链接:candidates: https://pan.baidu.com/s/1nvGWbrV 解决方法写一个思路 candidates = [ 'GGGAGCAGGCAAGGACTCTG', 'GCTCGGGCTTGTCCACAGGA', '...', # 被你看出来啦,这些其实人类基因的片段 ] bg_db = [ 'CTGCTGACGGGTGACACCCA', 'AGGAACTGGTGCTTGATGGC', '...', # 这个更多,有十亿左右 ] 因为你的数据其实是很有特点的,这里可以进行精简。 A ==> 00 T ==> 01 C ==> 10 G ==> 11 因为一个字符串长度固定,每个字符可以由2个比特位表示,所以每个字符串可以表示为一个40位的整数。可以表示为32+8的形式,也可以直接使用64位整形。建议使用C语言来做。 再来说说比较。 /*****************下面table中值的生成******//** int i; for( i=0;i<256;++i){ int t =0; t += (i&0x01 || i&0x02)?1:0; t += (i&0x04 || i&0x08)?1:0; t += (i&0x10 || i&0x20)?1:0; t += (i&0x40 || i&0x80)?1:0; printf("%d,",t); if(i%10 ==9){putchar('n');} } ********************************************// int table[] = { 0,1,1,1,1,2,2,2,1,2, 2,2,1,2,2,2,1,2,2,2, 2,3,3,3,2,3,3,3,2,3, 3,3,1,2,2,2,2,3,3,3, 2,3,3,3,2,3,3,3,1,2, 2,2,2,3,3,3,2,3,3,3, 2,3,3,3,1,2,2,2,2,3, 3,3,2,3,3,3,2,3,3,3, 2,3,3,3,3,4,4,4,3,4, 4,4,3,4,4,4,2,3,3,3, 3,4,4,4,3,4,4,4,3,4, 4,4,2,3,3,3,3,4,4,4, 3,4,4,4,3,4,4,4,1,2, 2,2,2,3,3,3,2,3,3,3, 2,3,3,3,2,3,3,3,3,4, 4,4,3,4,4,4,3,4,4,4, 2,3,3,3,3,4,4,4,3,4, 4,4,3,4,4,4,2,3,3,3, 3,4,4,4,3,4,4,4,3,4, 4,4,1,2,2,2,2,3,3,3, 2,3,3,3,2,3,3,3,2,3, 3,3,3,4,4,4,3,4,4,4, 3,4,4,4,2,3,3,3,3,4, 4,4,3,4,4,4,3,4,4,4, 2,3,3,3,3,4,4,4,3,4, 4,4,3,4,4,4 }; int getCount(uint64_t cmpresult) { uint8_t* pb = &cmpresult; // 这里假设是小段模式,且之前比较结果是存在低40位 return table[pb[0]]+table[pb[1]]+table[pb[2]]+table[pb[3]]+table[pb[4]]; } 以上是python如何提高大量的字符串比较速度的解决方法,看是否可以帮到你。 (编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |