Python에서 다중 문자열 대체를 수행하는 가장 빠른 구현

Question

문자열 (예 : text.replace (a, b) .replace (c, d))에서 '대체'체인을 수행하는 것 이외에 여러 문자열 대체를 수행하는 권장 방법이 있습니까? replace (e, f) ...)? 예를 들어 파이썬에서 PHP의 htmlspecialchars처럼 동작하는 빠른 함수를 어떻게 구현합니까?

필자는 (1) 다중 대체 방법, (2) 정규 표현 방법 및 (3) 매트 앤더슨 방법을 비교했다.

100에 문자 :

 
TIME: 0 ms [ replace_method(str) ] 
TIME: 5 ms [ regular_expression_method(str, dict) ] 
TIME: 1 ms [ matts_multi_replace_method(list, str) ] 

1000 문자 :

 
TIME: 0 ms [ replace_method(str) ] 
TIME: 3 ms [ regular_expression_method(str, dict) ] 
TIME: 2 ms [ matts_multi_replace_method(list, str) ] 

10000에 문자 :

다음과 같이 N = 10 타점

는 결과를 내놓았다

 
TIME: 3 ms [ replace_method(str) ] 
TIME: 7 ms [ regular_expression_method(str, dict) ] 
TIME: 5 ms [ matts_multi_replace_method(list, str) ] 

100000 자 :

 
TIME: 36 ms [ replace_method(str) ] 
TIME: 46 ms [ regular_expression_method(str, dict) ] 
TIME: 39 ms [ matts_multi_replace_method(list, str) ] 

1000000에 문자 :

 
TIME: 318 ms [ replace_method(str) ] 
TIME: 360 ms [ regular_expression_method(str, dict) ] 
TIME: 320 ms [ matts_multi_replace_method(list, str) ] 

3,687,809에 문자 : 매트에

 
TIME: 1.277524 sec [ replace_method(str) ] 
TIME: 1.290590 sec [ regular_expression_method(str, dict) ] 
TIME: 1.116601 sec [ matts_multi_replace_method(list, str) ] 

그래서 명성 상당히 큰 입력 문자열에 멀티 '대체'방법을 치기위한 .

누구나 작은 문자열로 박살내는 아이디어가 있습니까?

Answer 1

일반적으로, .replace 방법은 다른 모든 방법을 친다. (위의 벤치 마크를 참조하십시오.)

Answer 2

얼마나 빠릅니까? 또한 문자열이 얼마나 큽니까?

정규 표현식을 구축하여 다른 사이트에서 작업하는 데 매우 간단한 recipe이 있습니다. regex 메타 문자를 처리하기 위해 약간의 조정이 필요할 수 있습니다. 나는 너무 가깝게 보지 않았다.

충분하지 않다면 솔직히 C 코드를 작성해야 할 것입니다. 간단한 상태 머신을 만들어 모든 대체 작업을 수행 한 다음 컴퓨터에서 역 추적을하지 않고 바이트 단위로 모든 문자열을 처리하여 실제로 작업을 수행 할 수 있습니다. 그러나, 나는 C로 가서 최적화하지 않고 정규식 엔진을 이길 것이라고는 생각하지 않는다.

Answer 3

다음과 같은 어쩌면? 첫 번째 "대체"항목으로 텍스트를 분할 한 다음 해당 부분을 하위 부분으로 재귀 적으로 분할하여 다음 "대체 항목"항목을 교체 할 때까지 계속 반복합니다. 모든 대체 항목을 방문 할 때까지 계속됩니다 . 그런 다음 재귀 함수가 완료되면 각 "to"대체 항목과 조인하십시오.

아마도 다음 코드 주위에 머리를 감싸기가 힘들 것입니다. (그것은 나를위한 것이었고 작성했습니다.) 의도 한대로 작동하는 것 같습니다. 나는 벤치마킹을하지 않았지만 합리적으로 빠를 것이라고 생각합니다. 대한

def multi_replace(pairs, text): 
    stack = list(pairs) 
    stack.reverse() 
    def replace(stack, parts): 
     if not stack: 
      return parts 
     # copy the stack so I don't disturb parallel recursions 
     stack = list(stack) 
     from_, to = stack.pop() 
     #print 'split (%r=>%r)' % (from_, to), parts 
     split_parts = [replace(stack, part.split(from_)) for part in parts] 
     parts = [to.join(split_subparts) for split_subparts in split_parts] 
     #print 'join (%r=>%r)' % (from_, to), parts 
     return parts 
    return replace(stack, [text])[0] 


print multi_replace(
    [('foo', 'bar'), ('baaz', 'foo'), ('quux', 'moop')], 
    'foobarbaazfooquuxquux') 

:

barbarfoobarmoopmoop