regex를 사용하여 목록을 빠르게 필터링하는 방법은 무엇입니까?

Question

음 ... 나는 항목의 목록을 즉석에서 필터링하는 항목을 작성하라는 사소한 요청이 있습니다. (편집기 자동 완성 기능을 생각해보십시오)

요청은 전체 목록에 대한 정규식 필터를 지원하고 일치하는 항목 만 표시하는 것입니다.

예

가

목록이 포함

regex = re.compile(r"{0}".format(entry_value), re.IGNORECASE) 
display_list = list(filter(regex.search, display_list)) 

:

엔트리 여기

Value : List 
hij  : abc.efg.hij.entry, abc.ddd.hij.entry2, hij.some.value.entry 
ddd  : abc.ddd.hij.entry2 
dd*entry : abc.ddd.hij.entry2 
val  : hij.some.value.entry 

에

abc.efg.hij.entry 
abc.ddd.hij.entry2 
hij.some.value.entry 

타이핑 제가리스트를 필터링 사용하고 코드는

실생활의 리 st에는 ~ 300K 개의 문자열 항목 (각각 최대 100 자까지)이 포함되어 있으며 GUI 응답 시간을 고려하면 위의 성능이 매우 좋지 않습니다. 필자는 실제 테스트 케이스를 프로파일 링했으며 엔트리의 각 키 입력에 대해 ~ 0.8s를 산출했습니다.

더 빠른 방법이 있습니까?

Answer 1

300,000 개의 항목이 포함 된 일반 파이썬 목록에 대해 정규 표현식 패턴 일치를 수행하는 경우 자연스럽게 느려질 것입니다. 또한 목록 상자에 300,000 개의 항목을 표시하려는 경우 모든 항목을 표시하는 속도가 느려집니다.

더 나은 데이터 구조를 선택하는 것이 가장 좋습니다. 예를 들어, 내 시스템에서 약 250ms 동안 300,000 개의 항목에 대해 필터를 실행할 수 있지만 300,000 개의 행이있는 메모리 내장 sqlite 데이터베이스에 대한 쿼리에는 약 절반이 소요됩니다. 두 경우 모두 결과가 매우 큰 경우 표시를 완전히 업데이트하는 초를 추가 할 수 있습니다 (예 : 모든 300,000이 일치하는 경우)

물론 sqlite는 정규식을 지원하지 않지만 일부 일반적인 패턴을 SQL 패턴으로 변환하십시오 (예 : 'foo. * bar'는 'foo % bar'로 변환 될 수 있음). sqlite 및 regex에 대한 자세한 내용은 How do I use regex in a SQLite query?

을 참조하십시오. 또 다른 전략은 입력 된 모든 문자를 검색하지 않는 것입니다. 사용자가 입력을 일시 중지 할 때까지 기다립니다. 예를 들어, "Lorem"을 입력하면 "L"을 검색 한 다음 "Lo"를 검색 한 다음 "Lor"등을 검색 할 필요가 없습니다. 대신 100 밀리 초 내에 검색되도록 예약하십시오. 각 키를 누를 때마다 검색을 다시 예약 할 수 있습니다. 이렇게하면 검색 속도가 저하되는 것을 막을 수 있으며 사용자에게 상당히 빠른 결과가 나타나는 것으로 나타납니다.