在字符串數組的自定義排序中提高性能

Question

我正試圖找到一種有效的方法來基於數組的每個字符串元素中的數值對字符串數組進行排序。我目前使用的Array.Sort（陣列，customComparer）靜態方法（快速排序），與我的自定義比較器類的存在（在按降序排序）：

class StringComparer : IComparer<string> 
{ 
    public int Compare(string a, string b) 
    { 
     string s1 = a; 
     string s2 = b; 

     Match matchA = Regex.Match(s1, @"\d+$"); 
     Match matchB = Regex.Match(s2, @"\d+$"); 

     long numberA = long.Parse(matchA.Value); 
     long numberB = long.Parse(matchB.Value); 

     if (numberB - numberA < 0) 
     { 
      return -1; 
     } 
     else 
     { 
      return 1; 
     } 
    } 
} 

這工作得很好，但有時需要太有很多時間需要排序，在2.4Ghz處理器上使用100 000個字符串的陣列需要一分多秒。我想知道是否有更有效的方法來實現這一點。例如，實現不同的排序算法或採用另一種方法，如使用字典和對值進行排序（值是字符串的數字部分）。有什麼建議麼？提前致謝！

Answer 1

首先，你不必要地一遍又一遍地解析相同的字符串（都與正則表達式匹配，然後解析匹配）。相反，將自己的內容封裝到自定義類型中，以便只需解析一次。

public class FooString { 
    private readonly string foo; 
    private readonly long bar; 

    public FooString(string foo) { 
     this.foo = foo; 
     Match match = Regex.Match(foo, @"\d+$"); 
     this.bar = Int64.Parse(match.Value); 
    } 

    public string Foo { get { return this.foo; } } 
    public long Bar { get { return this.bar; } } 
} 

我甚加一個Contract.Requires這個類，指出foo必須滿足的正則表達式。

其次，你有一個IComparer<T>上的T某些值死（在你的情況下，不匹配正則表達式，並且不能被解析到一個longstring S）。這通常是一個壞主意。

因此，使比較器的FooString：

public FooStringComparer : IComparer<FooString> { 
    public int Compare(FooString a, FooString b) { 
     Contract.Requires(a != null); 
     Contract.Requires(b != null); 
     return a.Bar.CompareTo(b.Bar); 
    } 
} 

現在，你的排序將是極快的，因爲你已經停止了一遍又一遍解析相同的字符串。

Answer 2

您正在解析每個比較的值。我建議你解析一次，得到一個字符串/長對，排序，然後提取字符串部分。

請注意，您現有的代碼有一個bug：它會從不返回0，兩個字符串比較相等。

下面是使用LINQ另一種方法（這是不是就地排序，但很簡單。）

var sorted = unsorted.OrderBy(x => long.Parse(Regex.Match(x, @"\d+$").Value)); 
        .ToList(); 

（一次OrderBy項目拿到鑰匙，然後比較鍵。）

Answer 3

您現在正在執行Regexes O（n log n）次。

考慮以上所有字符串循環一次，提取數值和它添加到SortedDictionary<long, string>

這僅需要O（N）的註冊表達的處決。其餘的分類應該是可比的。

Answer 4

僅使用Compiled選項創建Regex一次。這會增加速度。

class StringComparer : IComparer<string> 
{ 
    private static Regex _regex = new Regex(@"\d+$", RegexOptions.Compiled); 

    public int Compare(string a, string b) 
    { 
     long numberA = Int64.Parse(_regex.Match(a).Value); 
     long numberB = Int64.Parse(_regex.Match(b).Value); 
     return numberA.CompareTo(numberB); 
    } 
}