优化搜索速度的策略

概述：我想找出长度为3-15个字符的50,000个“单词”中至少有一次出现在1至50个字符长度的1亿个“句子”的数据库中，而没有空格但有换行符。（为什么？这是一个蛋白质组学项目，“词语”是肽序列，例如MRQNTWAAV，而句子是完整的蛋白质序列，例如MRQNTWAAVTGGQTNRALI ...有蛋白质组学工具可以进行搜索，但它们会更少因为它们是针对长查询字符串和非精确匹配进行优化的。）优化搜索速度的策略

另外，我会在一台普通的PC上，8 GB RAM上做这件事。

我是新来的蟒蛇，是一个贸易科学家，而不是程序员;我写了一个脚本，但速度很慢（在我看来）。因为我只是想找出哪些方面存在至少一次，我想我会加快速度通过：

分裂参考数据库为200份50万句
的遍历这些局部数据库，使用mmain将每个内存加载到内存中
将查询条件列表加载到内存中的列表中
使用mmain的find（当然不是正则表达式）迭代列表，并将未找到的术语写入查询术语的新列表
当循环进入ne XT数据库，使得查询词
的短文件的新名单等

这里是我的代码：就像我说的，我不是一个程序员，所以我知道这是不是最佳的。它削减了样本集当然可以正常工作。如果有一些基本的设计功能可以帮助它运行得更快（我不在乎是否需要一夜之间，但我希望它不会需要几天...我承认我还没有系统地计时。）

我立即想到了几件事： - 数据库文件大于或小于50 MB会更优化吗？ - 我确定我应该在内存中保留“未找到”的术语列表，只在过程结束时将其写入磁盘。我这样做了，所以我可以在这个设计阶段评估过程。

import os 
import mmap 
import glob 

os.chdir("C:/mysearch/") 
searchtermfile = "original_search_terms.txt" 

# load list of 50,000 search terms into memory as a list 
with open(searchtermfile, 'r') as f: 
    searchtermlist = [line.strip() for line in f] 
    numberofsearchterms = len(searchtermlist) 


#make a list of database files in the directory 
dblist = glob.glob('databasepart*.txt') 
sizedblist = len(dblist) 

counterdb = 0 #counts the iterations over the database files 
countersearchterms = 0 #counts the iterations over the search terms 
previousstring = "DUMMY" #a dummy value just for the first time it's used 

#iterate first over list of file names 
for nameoffile in dblist: 
    counterdb += 1 
    countersearchterms = 0 
    #remove old notfound list, this iteration will make a new, shorter one. 
    os.remove("notfound.txt") #returns an error if there is not already a notfound.txt file; I always make sure there's an empty file with that name 
    #read current database file (50 MB) into memory 
    with open(nameoffile, 'r+b') as f: 
     m = mmap.mmap(f.fileno(), 0) #Size 0 reads entire file into memory 
     #iterate over search terms 
     for searchstring in searchtermlist: 
      countersearchterms += 1 
      if m.find(searchstring) == -1: 
       with open("notfound.txt", "a") as myfile: 
        myfile.write(searchstring + "\n") 
      #this print line won't be there in the final code, it's allowing me to see how fast this program runs 
      print str(counterdb) + " of " + str(sizedblist) + " & " + str(countersearchterms) + " of " + str(numberofsearchterms) 
      previousstring = searchstring 
     m.close() 
    #reload saved list of not found terms as new search term list 
    with open('notfound.txt', 'r') as f: 
     searchtermlist = [line.strip() for line in f] 
     numberofsearchterms = len(searchtermlist)

来源

2014-01-15 prooffreader

因为您声明了您的代码有效，所以我在显然错误的地方更正了您的缩进;请确认您的代码正如此处显示的，现在正确地反映了您实际正在使用的内容。 –

我会先尝试现有的工具。它们可能比您想象的更适合您的用例。 – user2357112

你说你“当然”不使用正则表达式，但实际上我会这样。编译的正则表达式应该是用于字符串搜索的相当高效的自动机。你需要的序列可能重叠？如果不是的话，你可以采用findall的方式，它有一个硬编码循环的优点。 – Cilyan

也许你可以尝试但使用正则表达式：

>>> searchterms = ["A", "B", "AB", "ABC", "C", "BC"] 
>>> # To match longest sequences first, yes need to place them at the beginning 
>>> searchterms.sort(key=len, reverse=True) 
>>> searchterms 
['ABC', 'AB', 'BC', 'A', 'B', 'C'] 
>>> # Compile a big regex searching all terms together 
>>> _regex =re.compile("("+"|".join(searchterms)+")") 
>>> _regex.findall("ABCBADCBDACBDACBDCBADCBADBCBCBDACBDACBDACBDABCDABC") 
['ABC', 'B', 'A', 'C', 'B', 'A', 'C', 'B', 'A', 'C', 'B', 'C', 'B', 'A', 'C', 'B', 'A', 'BC', 'BC', 'B', 'A', 'C', 'B', 'A', 'C', 'B', 'A', 'C', 'B', 'ABC', 'ABC'] 
>>>

您可以使用finditer，而是如果你只计算比赛感兴趣。

来源

2014-01-15 12:45:32 Cilyan

哇。一个有50,000个术语的编译正则表达式！它没有发生在我身上。 – prooffreader

那么，无论如何，你想要电脑做这项工作？而且你会以某种方式迭代你检查的所有字符串的所有字符的所有字符。 :)在DokuWiki中使用此方法（零件较少，但正则表达式更复杂）。 – Cilyan

我试图在一个普通的PC上创建一个这样的正则表达式，其中一个测试集的长度为3到15个字符的50,000个元素，耗时2.35秒。 – Cilyan

我对Python的经验不多，所以我个人会用C或C++来做。问题被简化了，因为您只查找完全匹配。

内部循环是所有时间花费的地方，所以我会专注于此。

首先，我将列出5e4项，对它们进行排序，将它们放在一个二进制搜索表中，或者（更好）将它们放入逐字符搜索的特里结构中。

然后，在“句子”中的每个字符位置，调用搜索功能。它应该是相当快的。原则上，散列表具有O（1）性能，但常数因子很重要。我敢打赌，在这种情况下，trie仍然会击败它，并且你可以调整它的日光。

来源

2014-01-15 14:57:30

优化搜索速度的策略

回答

相关问题