ускорить поиск регулярных выражений для большого набора данных

Question

Я пытаюсь найти позиции совпадения (N или -) в большом наборе данных.Количество совпадений на строку (3 миллиона букв) составляет около 300 000.У меня 110 строк для поиска в одном и том же файле, поэтому я сделал цикл, используя re.finditer для сопоставления и сообщения о позиции каждого совпадения, но это занимает очень много времени.Каждая строка (последовательность ДНК) состоит только из шести символов (ATGCN-).Только 17 строк были обработаны за 11 часов.Вопрос в том, что я могу сделать, чтобы ускорить процесс?Часть кода, о которой я говорю:

for found in re.finditer(r"[-N]", DNA_sequence):
    position = found.start() + 1
    positions_list.append(position)
    positions_set = set(positions_list)
all_positions_set = all_positions_set.union(positions_set)
count += 1
print(str(count) + '\t' +record.id+'\t'+'processed')
output_file.write(record.id+'\t'+str(positions_list)+'\n')

Я также пытался использовать re.compile, когда гуглял, и обнаружил, что он может улучшить производительность, но ничего не изменилось (match = re.compile ('[-N] '))

Answer 1

Что касается не использования регулярных выражений, я сделал это на самом деле и теперь изменил свой скрипт, чтобы он выполнялся менее чем за 45 секунд, используя определенную функцию

def find_all(a_str, sub):
start = 0
while True:
    start = a_str.find(sub, start)
    if start == -1: return
    yield start + 1
    start += len(sub)

Итак, новая часть кодирования:

N_list = list(find_all(DNA_sequence, 'N'))
dash_list = list(find_all(DNA_sequence, '-'))
positions_list = N_list + dash_list
all_positions_set = all_positions_set.union(positions_list)
count += 1
print(str(count) + '\t' +record.id+'\t'+'processed')
output_file.write(record.id+'\t'+str(sorted(positions_list))+'\n')

Answer 2

Если у вас примерно 300 тыс. Совпадений - вы воссоздаете все более крупные set с, которые содержат точно такие же элементы, как list, к которым вы уже добавляете:

for found in re.finditer(r"[-N]", DNA_sequence):
    position = found.start() + 1
    positions_list.append(position)
    positions_set = set(positions_list) # 300k times ... why? why at all? 

Вместо этого вы можете просто использовать полученный список и поместить его в свой all_positions_set после того, как найдете все из них:

all_positions_set = all_positions_set.union(positions_list) # union takes any iterable

Это должно уменьшить память более чем на 50% (наборыдороже, чем списки), а также значительно сократить время выполнения.

---

Я не уверен, что быстрее, но вы можете даже пропустить с помощью регулярных выражений:

t = "ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-ATGCN-"

pos = []
for idx,c in enumerate(t):
    if c in "N-":
        pos.append(idx)

print(pos)  # [4, 5, 10, 11, 16, 17, 22, 23, 28, 29, 34, 35, 40, 41, 46, 47]

и вместо этого использовать enumerate () в вашей строке, чтобы найти позиции .... вам нужно проверить, быстрее ли это.