Стратегия для оптимизации скорости поиска нагула

Question

Обзор: Я хочу узнать, какой из 50 000 слов «от 3 до 15 символов» присутствует хотя бы один раз в базе данных из 100 миллионов «предложений» длиной от 50 до 1200 символов без но с разрывами строк.

(Почему это проект протеомики. «Слова» представляют собой последовательности пептидов, например MRQNTWAAV, а предложения - полные последовательности белка, например MRQNTWAAVTGGQTNRALI ... Существуют инструменты протеомики для поиска, но они будут еще меньше эффективны, поскольку они оптимизированы для длинных строк запросов и для неточных совпадений.)

Кроме того, я буду делать это на обычном ПК, 8 ГБ оперативной памяти.

Я новичок в питоне, будучи ученым по профессии, а не программистом; Я написал сценарий, но это довольно медленно (на мой взгляд). Так как я только хочу, чтобы выяснить, какие условия присутствуют, по крайней мере один раз, я думал, что ускорить процесс по:

• раздробления ссылки база данных на 200 части 500000 предложений
• итерации этих частичных баз данных , загружая каждый из них в память с помощью mmain
• Загрузка списка условий запроса в список в памяти
• нумерация по списку с помощью поиска mmain (не регулярное выражение, конечно!) и запись терминов, которые НЕ находятся в новый список условий запроса
• , когда цикл переходит к ne х базы данных, что делает новый список более короткого файла терминов запроса
• т.д.

Вот мой код: как я сказал, что я не программист, так что я знаю, что это не является оптимальным. Это, безусловно, отлично работает с набором пробоотборников. Если есть некоторые фундаментальные элементы дизайна, которые могут помочь ему работать быстрее (мне все равно, если это займет ночь, но я надеюсь, что это не займет несколько дней ... Я признаю, что я еще не систематически приурочил его.)

Несколько вещей, которые сразу происходят со мной: - Будут ли файлы базы данных размером более 50 МБ более оптимальными? - Я уверен, что мне следует сохранить список «не найденных» терминов в памяти, только записывая их на диск в конце процесса. Я сделал это так, чтобы я мог оценить процесс на этом этапе проектирования.

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) 

Answer 1

Может быть, вы могли бы, однако попробуйте использовать регулярные выражения:

>>> 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 вместо этого, если вы заинтересованы только в подсчете совпадений.

Answer 2

У меня меньше опыта работы с python, поэтому лично я бы сделал это на C или C++. Проблема упрощена, потому что вы ищете только точные соответствия.

Внутренний цикл - это время, где все время тратится, поэтому я сосредоточусь на этом.

Во-первых, я бы взял список терминов 5e4, отсортировал их, поместил в таблицу для бинарного поиска или (еще лучше) поместил их в структуру trie для поиска по буквам.

Затем в каждой позиции символа в «предложении» вызовите функцию поиска. Должно быть довольно быстро. В принципе, хеш-таблица имела бы производительность O (1), но постоянный фактор важен. Я бы поспорил, что в этом случае trie все равно бьет его, и вы можете настроить дневной свет.