文字列配列のカスタム並べ替えのパフォーマンスを向上

Question

配列の各文字列要素内の数値に基づいて文字列の配列を並べ替える効率的な方法を見つけようとしています。これは非常にうまく動作しますが、時にはそれがあまりにもかかる

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

：私は現在、（降順でソート）私のカスタムの比較子クラスでのArray.sort（配列、customComparer）静的メソッド（クイックソート）は、ビーイングを使用しています2.4Ghzプロセッサで1分以上かかる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; } } 
} 

私もfooは、正規表現を満たさなければならないことを言って、このクラスにContract.Requiresを追加すると思います。

第二に、あなたは（あなたの場合には、正規表現と一致しないとlongに解析できないstring秒）Tの特定の値に死ぬIComparer<T>を持っています。これは一般的には悪い考えです。

ので、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

各比較の値を解析しています。 を一度のように解析して、文字列/ロングペアを取得してソートし、その後に文字列部分を抽出することをお勧めします。

既存のコードにはバグがあります。はありませんは2つの文字列が等しいと比較して0を返します。

ここでLINQ使用して別のアプローチです（ソートでは、場所ではなく、シンプルである。）

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

（OrderByプロジェクトに一度のキーを取得するには、その後、キーを比較します。）

Answer 3

Regexes O（n log n）回実行しています。

は、O（n）のレッグ式の実行を必要とする数値を抽出し、SortedDictionary<long, string>

これに追加し、すべての文字列の上に一度ループを検討してください。残りの並べ替えは同等でなければなりません。

Answer 4

Compiledオプションを使用してRegexを1回だけ作成します。これにより速度が向上します。

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