Inverse String.Replace - Cách làm nhanh hơn?

Question

Tôi có một phương pháp để thay thế mọi ký tự ngoại trừ những ký tự tôi chỉ định. Ví dụ,

ReplaceNot("test. stop; or, not", ".;/\\".ToCharArray(), '*'); 

sẽ trở

 
"****.*****;***,****". 

Bây giờ, đây không phải là một thể hiện của tối ưu hóa quá sớm. Tôi gọi phương thức này khá nhiều lần trong một hoạt động mạng. Tôi thấy rằng trên chuỗi dài hơn, nó gây ra một số độ trễ, và loại bỏ nó đã giúp một chút. Bất kỳ trợ giúp để tăng tốc độ này sẽ được đánh giá cao.

public static string ReplaceNot(this string original, char[] pattern, char replacement) 
    {   
     int index = 0; 
     int old = -1; 

     StringBuilder sb = new StringBuilder(original.Length); 

     while ((index = original.IndexOfAny(pattern, index)) > -1) 
     { 
      sb.Append(new string(replacement, index - old - 1)); 
      sb.Append(original[index]); 
      old = index++; 
     } 

     if (original.Length - old > 1) 
     { 
      sb.Append(new string(replacement, original.Length - (old + 1))); 
     } 

     return sb.ToString(); 
    } 

Final # s. Tôi cũng đã thêm một trường hợp thử nghiệm cho chuỗi ký tự 3K, chạy ở 100K lần thay vì 1M để xem mức độ của mỗi thang này. Điều ngạc nhiên duy nhất là các biểu thức chính quy 'quy mô tốt hơn' hơn những người khác, nhưng nó không giúp đỡ vì nó là rất chậm để bắt đầu với:

 
User   Short * 1M Long * 100K  Scale 
John   319    2125   6.66 
Luke   360    2659   7.39 
Guffa   409    2827   6.91 
Mine   447    3372   7.54 
DirkGently  1094   9134   8.35 
Michael   1591   12785   8.04 
Peter   21106   94386   4.47 

Cập nhật: Tôi làm việc tạo ra các biểu thức chính quy cho phiên bản Phêrô một biến tĩnh, và đặt nó vào RegexOptions.Compiled phải công bằng:

 
User   Short * 1M  Long * 100K  Scale 
Peter   8997   74715   8.30 

Pastebin liên kết đến mã thử nghiệm của tôi, hãy sửa lại cho tôi nếu nó là sai: http://pastebin.com/f64f260ee

Answer 1

Alright, trên một chuỗi ~ 60kB, điều này sẽ thực hiện nhanh hơn so với phiên bản của bạn khoảng 40%:

public static string ReplaceNot(this string original, char[] pattern, char replacement) 
{ 
    int index = 0; 

    StringBuilder sb = new StringBuilder(new string(replacement, original.Length)); 

    while ((index = original.IndexOfAny(pattern, index)) > -1) 
    { 
     sb[index] = original[index++]; 
    } 

    return sb.ToString(); 
} 

Bí quyết là để khởi tạo một chuỗi mới với tất cả các ký tự thay thế, vì hầu hết các ký tự sẽ được thay thế.

Answer 2

nó sẽ là O (n). Bạn dường như đang thay thế tất cả các bảng chữ cái và khoảng trắng theo *, tại sao không chỉ kiểm tra nếu ký tự hiện tại là một bảng chữ cái/khoảng trắng và thay thế nó?

Answer 3

bạn không thể sử dụng Regex.Replace như vậy:

Regex regex = new Regex(@"[^.;/\\]"); 
string s = regex.Replace("test. stop; or, not", "*"); 

Answer 4

Tôi không biết nếu điều này sẽ được bất kỳ nhanh hơn, nhưng nó tránh newing lên dây chỉ để họ có thể được nối vào xây dựng chuỗi, mà có thể giúp:

public static string ReplaceNot(this string original, char[] pattern, char replacement) 
    { 
     StringBuilder sb = new StringBuilder(original.Length); 

     foreach (char ch in original) { 
      if (Array.IndexOf(pattern, ch) >= 0) { 
       sb.Append(ch); 
      } 
      else { 
       sb.Append(replacement); 
      } 
     } 

     return sb.ToString(); 
    } 

Nếu số lượng ký tự trong pattern sẽ có kích thước bất kỳ (mà tôi đoán nó thường sẽ không), nó có thể trả tiền để sắp xếp nó và thực hiện một Array.BinarySearch() thay vì Array.indexOf().

Để chuyển đổi đơn giản như vậy, tôi muốn đặt cược rằng nó sẽ không có vấn đề gì nhanh hơn cả regex nữa.

Ngoài ra, vì bộ ký tự của bạn trong pattern có thể thường xuất phát từ chuỗi (ít nhất đó là trải nghiệm chung của tôi với loại API này), tại sao bạn không có chữ ký phương thức là:

public static string ReplaceNot(this string original, string pattern, char replacement) 

hoặc tốt hơn, có tình trạng quá tải nơi pattern có thể là char[] hoặc string?

Answer 5

StringBuilder có quá tải phải mất một ký tự và một số, do đó bạn không phải tạo chuỗi trung gian để thêm vào StringBuilder. Tôi có được cải thiện khoảng 20% ​​bằng cách thay thế này:

sb.Append(new string(replacement, index - old - 1)); 

với:

sb.Append(replacement, index - old - 1); 

và điều này:

sb.Append(new string(replacement, original.Length - (old + 1))); 

với:

sb.Append(replacement, original.Length - (old + 1)); 

(Tôi đã thử nghiệm mã mà bạn nói nhanh gấp bốn lần và tôi tìm thấy chậm hơn khoảng 15 lần ...)

Answer 6

Đây là phiên bản khác dành cho bạn. Thử nghiệm của tôi cho thấy hiệu suất của nó khá tốt.

public static string ReplaceNot(
    this string original, char[] pattern, char replacement) 
{ 
    char[] buffer = new char[original.Length]; 

    for (int i = 0; i < buffer.Length; i++) 
    { 
     bool replace = true; 

     for (int j = 0; j < pattern.Length; j++) 
     { 
      if (original[i] == pattern[j]) 
      { 
       replace = false; 
       break; 
      } 
     } 

     buffer[i] = replace ? replacement : original[i]; 
    } 

    return new string(buffer); 
}