在字符串数组的自定义排序中提高性能

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); 
    } 
}