高效搜索不區分大小寫的ascii子字符串

我實際上正在優化大字符串的正則表達式轉換。至於Regex.Replace幾個電話把我插入條件調用顯著的時間 - 這是沿線高效搜索不區分大小寫的ascii子字符串

if (str.IndexOf("abc", 0, StringComparison.CurrentCultureIgnoreCase) > 0) 
    str1 = Regex.Replace(str, "abc...", string.Empty, RegexOptions.IgnoreCase);

令我吃驚的結果是沒有說服力的。有時更好，有時候不更好。甚至更糟。所以我測不區分大小寫的IndexOf的性能（我想也StringComparison.OrdinalIgnoreCase），並發現它可能比Regex.Match慢，即本次測試：

if(Regex.Match(str,"abc", RegexOptions.IgnoreCase).Success)...

特別是對於一個大的字符串不匹配（ASCII ）string「abc」我發現Regex.Match速度快了4倍。

即使這個過程比快的IndexOf：

string s1 = str.ToLower(); 
if(s1.IndexOf("abc")) ...

任何人都知道一個更好的解決方案？

來源

2011-10-20 Jan Slodicka

爲什麼你首先檢查字符串是否存在並且比替換？ – Magnus

Regex.Replace是一個非常昂貴的操作，首先做一個簡單的測試是很有意義的 - 主要是在Regex根本找不到任何匹配的情況下。 –

與此同時，我編寫了一個基於ToLower變換的準解決方案。這已經有很大的幫助，因爲有多次Regex調用可以通過這種方式進行有條件的測試。 –

因爲indexOf是O（n * m），其中RegEx可能是O（n + m）（其中n =字符串長度，m =搜索字符串長度）。

如果您認真搜索子字符串，那麼閱讀字符串搜索算法以至少了解預期速度（從http://en.wikipedia.org/wiki/Substring_search開始）將是有用的。

注意：文化敏感度比較可能會比Ordinal慢得多（取決於您的場景，您可能無法使用Ordinal版本）。

與任何性能問題一樣，需要進行測量。在IndexOf中，Regex.isMatch對我來說明確的贏家是Regex。我的確認爲indexOf不應該執行任何預編譯的搜索字符串，而必須使用O（n + m）算法，而Regex必須使用更多的優化實現。

試着測量下面的搜索 - 在100K操作中，我得到了幾乎5倍的正則表達式差異。

static void Main(string[] args) 
    { 
     var stringToSearch = "AAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbb"; 
     Regex regExp = new Regex(stringToSearch, RegexOptions.Compiled | RegexOptions.CultureInvariant | RegexOptions.IgnoreCase); 

     var sourceText = "AAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAbAAAAAAAAAAAAAAAAAAAAAbb"; 

     const int Iterations = 100000; 

     Stopwatch watch = new Stopwatch(); 
     watch.Start(); 
     for (int i = 0; i < Iterations; i++) 
     { 
      regExp.IsMatch(sourceText); 
     } 
     watch.Stop(); 
     Console.WriteLine("RegExp: {0} ms", watch.ElapsedMilliseconds); 

     watch = new Stopwatch(); 
     watch.Start(); 
     for (int i = 0; i < Iterations; i++) 
     { 
      sourceText.IndexOf(stringToSearch, StringComparison.OrdinalIgnoreCase); 
     } 
     watch.Stop(); 
     Console.WriteLine("RegExp: {0} ms", watch.ElapsedMilliseconds); 
     Console.ReadLine(); 
    }

來源

2011-10-20 16:18:10

這是否意味着.Net不提供簡單有效的不區分大小寫的子串搜索？很難相信。 –

正則表達式對重複搜索長字符串表現更好。 –

這可能是我的情況 - 搜索說10K字符串爲一個約5個字符的小字符串。我只是說我測量了5：1的差異。我明天繼續。 –

最後我寫了自己的函數進行匹配測試。這是：

private static bool HasAsciiSubstring(string str, string sub) 
{ 
    char[] ss = sub.ToCharArray(); 

    // Similar stupid small optimizations bring 30% speeding-up. 
    int ss_len = ss.Length; 
    for (int j = 0; j < ss_len; ++j) 
     ss[j] = (char)((byte)ss[j] | 32); 

    byte ss0 = (byte)ss[0]; 
    int len = str.Length - ss_len; 
    for (int i = 0; i < len; ++i) 
    { 
     if ((str[i] | 32) == ss0) 
     { 
      bool bOk = true; 
      for (int j = 1; j < ss_len; ++j) 
      { 
       if ((str[i + j] | 32) != ss[j]) 
       { 
        bOk = false; 
        break; 
       } 
      } 
      if (bOk) 
       return true; 
     } 
    } 

    return false; 
}

此方法在WP7平臺上提供了最佳結果（對於選定的大字符串）。這是比Regex.Match（STR，子，RegexOptions.IgnoreCase）

大致10倍的比str.IndexOf更快（子，0，StringComparison.CurrentCultureIgnoreCase）

str.IndexOf（子更快

2X ，0，StringComparison.OrdinalIgnoreCase）比CurrentCultureIgnoreCase慢了30％。

我需要一個能夠在WP7，MonoDroid/Touch和可能在桌面上滿意工作的代碼。因此，我寫了一個小型WPF應用程序來測試至少桌面：

Regex.Match（）比HasAsciiSubstring（）快2倍。
OrdinalIgnoreCase 2。5倍慢於CurrentCultureIgnoreCase
剩下的就是類似

我是比較新的C＃/。NET（2年只經歷），但編程數十年在其他平臺上（主要是C/C++）。我要打倒，這是一種令人震驚的經歷對我來說：

低效C＃字符串函數
低效C＃作爲一種語言工具。（我非常肯定用C++編寫的代碼會更好。）
這種複雜的文化業務和CurrentCultureIgnoreCase執行得比OrdinalIgnoreCase好得多的事實。（看起來每個有經驗的C＃程序員 - 包括我周圍的人 - 都聲稱恰恰相反）

來源

2011-10-21 10:33:05

您可以通過使用不安全的代碼來提高速度。 – Magnus

當然。使用指針算術必須是一個巨大的節省時間。如果我這樣做，我會報告結果。 –

我給了它一個快速嘗試，但有2件事情讓人失望：a）要獲取字符指針，你需要調用str.ToCharArray，這是一個相對昂貴的調用。 b）你不能做真指針算術 - 我的意思是諸如* ptr ++的表達式是非法的。也許我錯過了一些東西，但是現在我會說不安全的代碼不會有太大的幫助。 –

高效搜索不區分大小寫的ascii子字符串

回答

相關問題