Поиск сена для нескольких игл равной длины (Python)

Question

Я ищу способ поиска большой строки для большого количества подстрок одинаковой длины.

Мой текущий метод в основном это:

offset = 0 
found = [] 

while offset < len(haystack): 
    current_chunk = haystack[offset*8:offset*8+8] 
    if current_chunk in needles: 
    found.append(current_chunk) 
    offset += 1 

Это мучительно медленно. Есть ли лучший способ для python?

Answer 1

Более Pythonic, намного быстрее:

for needle in needles: 
    if needle in haystack: 
     found.append(needle) 

Edit: С некоторыми ограниченного тестирования здесь результаты испытаний

Этот алгоритм: 0,000135183334351

Ваш алгоритм: 0,984048128128

Гораздо быстрее.

Answer 2

Я думаю, что вы можете разбить его на многоядерном и распараллелить свой поиск. Что-то вроде строк:

from multiprocessing import Pool 

text = "Your very long string" 

""" 
A generator function for chopping up a given list into chunks of 
length n. 
""" 
def chunks(l, n): 
    for i in xrange(0, len(l), n): 
    yield l[i:i+n] 

def searchHaystack(haystack, needles): 
    offset = 0 
    found = [] 

    while offset < len(haystack): 
     current_chunk = haystack[offset*8:offset*8+8] 
     if current_chunk in needles: 
     found.append(current_chunk) 
     offset += 1 
    return(needles) 

# Build a pool of 8 processes 
pool = Pool(processes=8,) 

# Fragment the string data into 8 chunks 
partitioned_text = list(chunks(text, len(text)/8)) 

# Generate all the needles found 
all_the_needles = pool.map(searchHaystack, partitioned_text, needles)