Thực hiện nhanh nhất để thực hiện nhiều thay thế chuỗi trong Python

Question

Có cách nào được khuyến nghị để thực hiện nhiều thay thế chuỗi khác với chuỗi 'thay thế' trên một chuỗi (ví dụ: text.replace (a, b) .replace (c, d). thay thế (e, f) ...)? Ví dụ: bạn sẽ triển khai chức năng nhanh như thế nào hoạt động như htmlspecialchars của PHP bằng Python?

Tôi đã so sánh (1) nhiều phương pháp 'thay thế', (2) phương thức biểu thức chính quy và (3) phương pháp của Matt Anderson.

Với n = 10 chạy, kết quả đã đưa ra như sau:

On 100 ký tự:

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

On 1000 ký tự:

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

On 10000 ký tự:

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

Bật 100000 ký tự:

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

On 1000000 ký tự:

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

On 3.687.809 nhân vật:

 
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) ] 

Vì vậy, thanh danh cho Matt cho đập phương pháp đa 'thay thế' trên một chuỗi đầu vào khá lớn .

Bất kỳ ai có ý tưởng để đánh bại nó trên một chuỗi nhỏ hơn?

Answer 1

phương pháp thường, .replace nhịp đập tất cả các phương pháp khác. (Xem điểm chuẩn của tôi ở trên.)

Answer 2

Nhanh như thế nào? Ngoài ra, dây của bạn lớn đến cỡ nào?

Có một cách đơn giản recipe để xây dựng cụm từ thông dụng để thực hiện công việc trên một trang web khác. Nó có thể cần một số tinh chỉnh để xử lý các metacharacters regex; Tôi không nhìn quá gần.

Nếu điều đó không đủ tốt, bạn có thể cần phải viết một số mã C, một cách trung thực. Bạn có thể xây dựng một máy trạng thái đơn giản để thực hiện tất cả các thay thế, và sau đó xử lý bất kỳ byte chuỗi nào bằng byte mà không có backtracking dọc theo máy để thực sự thực hiện công việc. Tuy nhiên, tôi nghi ngờ bạn sẽ đánh bại các động cơ regex mà không đi đến C và tối ưu hóa điều đó.

Answer 3

Điều gì đó giống như sau? Tách văn bản thành từng phần với mục "từ" đầu tiên được thay thế, sau đó phân tách đệ quy từng phần đó thành các phần phụ với mục "từ" tiếp theo được thay thế, v.v. cho đến khi bạn truy cập tất cả các thay thế của bạn . Sau đó, tham gia với mục "thay thế" cho mỗi mục như hàm đệ quy hoàn thành.

Một chút khó khăn để quấn đầu của bạn xung quanh mã sau đây có lẽ (nó đã được cho tôi, và tôi đã viết nó), nhưng nó có vẻ chức năng như dự định. Tôi đã không đánh giá nó, nhưng tôi nghi ngờ nó sẽ được hợp lý nhanh chóng.

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') 

cho:

barbarfoobarmoopmoop