2

私はこのような配列を持っています -

string[] input = new string[] {"bRad", "Charles", "sam", "lukE", "vIctor"}

ここで、各文字列に発生する大文字の位置に従ってこれを並べ替えたいと思いました。最初のオカレンスは、並べ替え中に考慮される唯一のオカレンスです。2 つの文字列の同じ位置に CAP がある場合、それらをアルファベット順に並べ替えます。CAP を持たない文字列にも同じことが当てはまり、アルファベット順に並べ替えます。

私がこれまでやってきたことは、十分に機能していません。私はそれを改善するために数え切れないほど試みましたが、運がありません。これがテストされる膨大な量のデータが存在するでしょう。そのため、パフォーマンスが最も重要です。.NET 2.0 を使用していますが、それ以降のバージョンは使用できません。

public static int q, p, i, s;
public static Dictionary<string, int> a = new Dictionary<string, int>();

Array.Sort(input, delegate (string x, string y) {

    if (x == y)
        return 0;

    if (a.TryGetValue(x + "|" + y, out s))
        return s;

    if (a.TryGetValue(y + "|" + x, out s))
        return -s;

    q = x.Length;
    p = y.Length;

    for (i = 0; i < x.Length; i++)
    {
        if (x[i] < 91)
        {
            q = i;
            break;
        }
    }

    for (i = 0; i < y.Length; i++)
    {
        if (y[i] < 91)
        {
            p = i;
            break;
        }
    }

    if (q == x.Length && p == y.Length)
        s = x.CompareTo(y);
    else if (q > p)
        s = 1;
    else if (q < p)
        s = -1;
    else
        s = x.CompareTo(y);

    a.Add(x + "|" + y, s);

    return s;

});
4

4 に答える 4

2

いくつかの最適化があると思います（すでに高速になっているはずです）。

まず、上で示唆したように、Sortアルゴリズム自体が辞書の必要性を最適化するため、実際には辞書は必要ありません。

2 番目に、x と y を同時にループし、できるだけ早くブレークアウトします (つまり、一方が大文字を見つけ、もう一方が早期に終了しない場合)。ここで小さな節約。

それはほぼそれを行う必要があります（そしてより簡単になります）。あなたは基本的に書き直すだけで効率的であり、残りはにString.CompareTo依存しています。Array.Sort

于 2012-04-26T05:30:39.517 に答える
2

キャッシュのディクショナリを削除するだけで速度が上がりました (値ごとに最大 500 文字の 15000 の値の私の例) は、ディクショナリで 2449.51ms から、削除すると 58.72ms に減少しました

連結を実行するよりも高速な個々の値の位置をキャッシュする「craigmj」のアイデアを試しましたが、ランダムデータではキャッシュがまだ高速ではないようです。

テストするコードは次のとおりです...これは2559ミリ秒（オリジナル）と比較して30ミリ秒で実行されます

Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
Array.Sort(input, delegate(string x, string y)
{
    if (x == y)
        return 0;

    int shortestLength = Math.Min(x.Length, y.Length);

    for (i = 0; i < shortestLength; i++)
    {
        if (x[i] < 91 && y[i] < 91)
            return x.CompareTo(y);
        else if (x[i] < 91)
            return -1;
        else if (y[i] < 91)
            return 1;
    }
    return x.CompareTo(y);
});

stopWatch.Stop();
double ms = (stopWatch.ElapsedTicks * 1000.0) / Stopwatch.Frequency;
Debug.WriteLine("Optimized Time: " + ms);

資本のチェックを続行するコード

Stopwatch stopWatch = new Stopwatch();
stopWatch.Start();
Array.Sort(input, delegate(string x, string y)
{
    if (x == y)
        return 0;

    int xlen = x.Length;
    int ylen = y.Length;
    int longestLength = Math.Max(xlen, ylen);

    for (i = 0; i < longestLength; i++)
    {
        if (i < xlen && i < ylen && x[i] < 91 && y[i] < 91)
            return x.CompareTo(y);
        else if (i < xlen && x[i] < 91)
            return -1;
        else if (i < ylen && y[i] < 91)
            return 1;
    }
    return x.CompareTo(y);
});

stopWatch.Stop();
double ms = (stopWatch.ElapsedTicks * 1000.0) / Stopwatch.Frequency;
Debug.WriteLine("Optimized Time: " + ms);
于 2012-04-26T05:40:46.890 に答える
2

ここでアルゴリズムについて考える必要があります:-)

辞書にはいくつの要素が含まれますか? さて、配列内のすべての要素 x、y の辞書に "{x} | {y}" を入れているので、n 要素の配列では n ^ 2 です。良い考えではありません。

これは必ずしも最善の解決策ではありません (まだ考えていません) が、まずは:

組み合わせではなく、特定の単語の最初の大文字の位置のみを辞書に保存します。

これで、デリゲートは次のようになります。

delegate (string x, string y) {

    if (x == y)   // NOT A GOOD IDEA - 
                  // THE Sort method should not call a string with itself,
                  // and if this is doing string comparison
                  // (I'm rusty on C#), you're
                  // wasting a comparison if there's a mismatch
        return 0;

    int xCapitalPos, yCapitalPos;
    if (!a.TryGetValue(x, out xCapitalPos)) {
        // compute xCapitalPos and add it to dictionary a
    }
    if (!a.TryGetValue(y, out yCapitalPos)) {
        // compute yCapitalPos and add it to dictionary a
    }
    int delta = xCapitalPos - yCapitalPos;
    if (0!=delta) {
        return delta;
    } else {
        return x.compareTo(y);
    }
}

それが私が始めるところです。自分のやり方を見て、そこからどうすればもっとうまくやれるかを考えてください...

--- 5分後、手にはコーヒーカップ

わかりました、私はそれを改善する方法を考えました！

文字列比較を行うcompareToは使用しないでください。2 つの文字列を指定すると、大文字の場所を考慮しながら文字列比較を行う、独自の文字列比較関数を作成します。次に、辞書とその他すべてを削除できます。Sort メソッド (QuickSort または MergeSort または効率的なものとして適切に実装されていると思います) により、必要以上の比較を行わないようにするため、必要ありません。

すべてのベスト、C

于 2012-04-26T05:14:50.713 に答える
1

大文字と文字列の位置の一致を行うデリゲートの (疑似) コードを次に示します。

delegate (string lhs, string rhs) {
    int llength = lhs.Length
    int rlength = rhs.Length

    // The value we will return 
    // <0 => lhs < rhs
    // ==0 => lhs == rhs
    // >0 => lhs > rhs  
    int ret = 0;
    Boolean uppercaseFoundAndEqual = false;

    for (int i=0; i<llength; i++) {
        if (i>=rlength) {
            // We've exhausted the rhs, but not the lhs
            return (0==ret) ? -1 : ret;
        }

        Char l = lhs[i];
        Char r = rhs[i];

        // We only worry about the case position if we've not yet found
        // an uppercase char in either string
        if (!uppercaseFoundAndEqual) {
            Boolean lUpper = (('A'<=l) && ('Z'>=l));
            Boolean rUpper = (('A'<=r) && ('Z'>=r));

            // If we've encountered an upper-lower difference, we return 
            int delta = (lUpper ? 1 : 0) - (rUpper ? 1 : 0);
            if (0!=delta) return delta;

            if (lUpper) {   // Both are upper case - by our delta comparison, we know 
                            // lUpper==rUpper
                if (0!=ret) return ret; // Return based on previous case comparison

                // Otherwise we've found an uppercase, now we're just doing
                // standard string comparison
                uppercaseFoundAndEqual = true;
            }
        }

        if (0==ret) {   // If we're still equal to this point, standard char comparison
            ret = l-r;
        }
        if (uppercaseFoundAndEqual && (0!=ret)) {
            return ret;
        }
    }
    if (i<rlength) {
        // We've exhausted the lhs, but not the rhs
        return (0==ret) ? 1 : ret;
    }
    return 0;   // We exhausted both strings and they're identical
}

注意してください:

  1. 私はこれをテストしていません！（したがって、「疑似コード」コメント）私はC＃を持っていないので、C＃構文のちょっとしたグーグルに基づいています。間違いがあれば訂正してください！
  2. これは国際化を使用していません。つまり、これは非常に基本的な ASCII 比較です。うん！System.Globalization.StringInfoの使用を検討する必要がありますが、グーグルに基づいてコード化するのが怖いです!
  3. あなたの説明は、2 つの文字列の長さが大文字化されていない場合にどうなるかを説明していません。たとえば、「aa」は「aaA」より大きいか小さいか? 「交差」領域外の大文字化は無視するという考えに基づいて実装しましたが、それを変更することは難しくありません。
  4. （強調のために）私はこれをテストしていません！走行距離は異なる場合がありますが、一般的な考え方は良いと思います。
于 2012-04-26T06:04:34.273 に答える