목록 조회를 빠르게 하시겠습니까?

Question

모든 줄에는 사람 이름과 연설문이 포함 된 파일이 있습니다. 이름이있는 파일은 알파벳 순서로 매우 큰 (250k 줄)이며, 연설 파일에는 약 1k 줄이 있습니다. 내가하고 싶은 일은 텍스트 파일에있는 이름을 검색하고 내 이름 파일에있는 모든 이름의 대체물을 대체하는 것입니다. 이것은 내 코드입니다. 편집 : 목록을 여는 with 함수는 한 번만 실행됩니다.

members_list = [] 
with open(path, 'r') as l: 
    for line in l.readlines(): 
     members_list.append(line.strip('\n')) 

for member in self.members_list: 
    if member in self.body: 
     self.body = self.body.replace(member, '<member>' + member + '</member>') 

이 코드의 실행에는 약 2.2 초가 걸리지 만 많은 음성 파일 (4.5k)이 있기 때문에 총 시간은 약 3 시간입니다. 더 빠르게 만들 수 있습니까? 발전기는 갈 길입니까?

Answer 1

현재 "if member in self.body"를 선택하면 250,000 개의 이름 각각에 대해 메모리의 각 연설을 한 번씩 다시 읽습니다.

전체 단어, 공백 및 구두점을 찾아 음성 본문을 한 번 구문 분석해야합니다. 그런 다음 알려진 이름의 선형 시간 조회를 사용하거나 최악의 로그 시간을 사용하여 이름을 찾았는지 확인해야합니다.

문제는 다양한 단어 길이를 가진 회원 이름을 찾아야한다는 것입니다. 그래서 여기에 마지막 세 단어를 검사하는 것을 처리하기 위해 작성한 빠른 (그리고 아주 좋지 않은) 구현이 있습니다.

# This is where you load members from a file. 
# set gives us linear time lookup 
members = set() 
for line in ['First Person', 'Pele', 'Some Famous Writer']: 
    members.add(line) 

# sample text 
text = 'When Some Famous Writer was talking to First Person about Pele blah blah blah blah' 
from collections import deque 

# pretend we are actually parsing, but I'm just splitting. So lazy. 
# This is why I'm not handling punctuation and spaces well, but not relevant to the current topic 
wordlist = text.split() 

# buffer the last three words 
buffer = deque() 

# TODO: loop while not done, but this sort of works to show the idea 
for word in wordlist: 
    name = None 
    if len(buffer) and buffer[0] in members: 
     name = buffer.popleft() 

    if not name and len(buffer)>1: 
     two_word_name = buffer[0] + ' ' + buffer[1] 
     if two_word_name in members: 
      name = two_word_name 
      buffer.popleft() 
      buffer.popleft() 

    if not name and len(buffer)>2: 
     three_word_name = buffer[0] + ' ' + buffer[1] + ' ' + buffer[2] 
     if three_word_name in members: 
      name = three_word_name 
      buffer.popleft() 
      buffer.popleft() 
      buffer.popleft() 

    if name: 
     print ('<member>', name, '</member> ') 

    if len(buffer) >2: 
     print (buffer.popleft() + ' ') 

    buffer.append(word) 

# TODO handle the remaining words which are still in the buffer 
print (buffer) 

나는 개념을 설명하려고합니다. 공백이나 구두점은 처리하지 않습니다. 이것은 전혀 끝을 처리하지 못합니다. 끝내지 않은 동안 반복해야합니다. 그것은 파싱 할 때 임시 문자열을 생성합니다. 하지만 구문 분석의 기본 개념을 한 번 보여줍니다. 음성 텍스트를 파싱하는 데 너무 느리긴하지만 음성 텍스트를 25 만 회 검색하는 데는 어려움이 있습니다.

텍스트를 구문 분석하고 이름에서 집합을 확인하려는 이유는 한 번 수행하는 것입니다. 한 세트가 선형 시간 조회를 할부 상환 했으므로 구성원의 이름이 맞는지 확인하는 것이 훨씬 빠릅니다.

기회가 생기면 나중에 토큰을 생성하고 끝에 이름을 찾는 문제를 해결할 수 있지만 최종 코드는 아닙니다.