Python - find() 함수의 비용

Question

짧은 문자열이 긴 문자열인지 확인하는 효과적인 방법을 찾고 있습니다. 이 스레드에 대한 몇 가지 제안을 보았습니다. Python efficient way to check if very large string contains a substring

그러나 find()를 사용하지 못했습니다. find() 함수를 사용하는 것이 비용이 많이 듭니까? 시간의 복잡성은 무엇입니까?

위키 페이지를 살펴 봤지만 find()를 찾지 못했습니다. https://wiki.python.org/moin/TimeComplexity

Answer 1

신속하게 소스를 정독하고,이 나타납니다 str.find 통화 결국 fastsearch를 호출 here에서 stringlib_find_slice. 실제 알고리즘은 here - 파이썬 의사 코드 (설명을 읽지 않고 수집 한)로 설명합니다.

구현이 최악의 경우 O (N * M) (순진한 접근 방식과 동일) 인 것처럼 보이지만 어떤 경우에는 O (N/M)을 수행 할 수 있습니다 (N과 M은 문자열 및 하위 문자열), O (N)은 빈번한 경우 입니다.

^{1은 -}

(그 날을 인용하지 않는 난 단지 문서를 미끄러 져)