阿神2017-04-18 10:01:45
算法白痴一个, 不过刚好手上有可以用的计算资源, 就按照原来的思路(暴力无脑并行计算流)做一下题主这个例子:
run.py
from multiprocessing import Pool, cpu_count
def do_align(item):
with open("bg_db.txt") as fh, open("result.txt", "a") as rh:
db_line = fh.readline().strip()
while db_line:
counts = 0
for i in [(i, j) for (i, j) in zip(db_line, item)]:
if i[0] != i[1]:
counts += 1
if counts >= 4:
break
if counts < 4:
rh.write("{}\n".format(db_line))
db_line = fh.readline().strip()
def main():
pool = Pool(cpu_count())
with open("candidates.txt") as fh:
pool.map(do_align, map(str.strip, fh))
pool.close()
pool.join()
if __name__ == "__main__":
main()
简单先生成点数据
import random
import string
def id_generator(size=8, chars=string.ascii_letters + string.digits):
return ''.join(random.choice(chars) for _ in range(size))
with open("candidates.txt", "w") as fh:
for i in range(10000):
fh.write("{}\n".format(id_generator(20, "ATCG")))
with open("bg_db.txt", "w") as fh:
for i in range(1000000):
fh.write("{}\n".format(id_generator(20, "ATCG")))
嗯, 造了10000
行的candidates.txt
和1000000
行的bg_db.txt
10000
行的candidates.txt
和1000000
行的bg_db.txt
运行看下时间:
$time python run.py
real 15m45.445s
user 1362m41.712s
sys 1m12.099s
题主实际的数据是千万行的candidates.txt
和十亿行的bg_db.txt
, 简单估算下时间16*1000/(60*24) = 11.11
运行看下时间:
CPU Utilization: 1.0 0.0 98.9
user sys idle
Hardware
CPUs: 96 x 2.10 GHz
Memory (RAM): 1009.68 GB
Local Disk: Using 351.623 of 941.596 GB
Most Full Disk Partition: 53.5% used.
题主实际的数据是千万行的candidates.txt
和十亿行的bg_db.txt
, 简单估算下时间16*1000/(60*24) = 11.11
伊谢尔伦2017-04-18 10:01:45
思路如下:
第一:比如对比4个差异的数据
**TGACGGGTGACACCCA(删除字符串某4个位置的字符),将字符长度变为16,匹配完全相同的字符串
用map之类的保存TGACGGGTGACACCCA为key值,差异的四个作为values值
第二:对比3个差异的数据
在上述基础的上,进行对比上述的values值为比较长度为3完全相同的字符串
以此类推
黄舟2017-04-18 10:01:45
提供一个思路,把四个字符简化成 00, 01, 10, 11。
比较的时候先执行 XOR,这样完全相同的就会变成 00;不完全相同的则是 01, 10或者 11。
然后再对XOR的结果每相邻的pair进行 OR,这样 00 会变成0, 01,10或者11就变成1。最后统计 1 的数量。由于都是位运算,理论上应该很快。
不过我的C学得渣,代码就不能贴出来了。