3

以下は、文字列を逆にするために作成できる最速のコードです

public static void ReverseFast(string x)
{
    string text = x;
    StringBuilder reverse = new StringBuilder();

    for (int i = text.Length - 1; i >= 0; i--)
    {
        reverse.Append(text[i]);
    }
      Console.WriteLine(reverse);
}

この方程式のすべてのボトルネックに対処して、可能な限り高速化したいと考えています。これまでに見つけた唯一のものは、部分的にしか理解していない Array Bounds チェックです。コンパイラを使用して境界をチェックしないことを決定した場合、これを無効にする方法はありますが、ループ内にいる.Lengthときにデクリメントしている場合でも境界チェックを行いますか? for誰かがこれを変換して、境界チェックを回避するポインタを使用することができます.10万文字以上の範囲の文字列の速度差をテストしたいと思います.

以下のコメントと投稿に基づいて、これは私がこれまでに思いついたものです。

public static void ReverseFast(string x)
{
    StringBuilder reverse = new StringBuilder(x.Length);
    for (int i = x.Length - 1; i >= 0; i--)
    {
        reverse.Append(x[i]);
    }
    Console.WriteLine(reverse);
}

この上記の解決策は、提案された重複した質問の回答よりもはるかに高速です。この質問は、実際には 5000 * 26 文字 + の範囲の反転に対処しています。特にこのような大量の文字でボトルネックがないかどうかを実際に確認するために、ポインターを使用してこれをテストしたいと思います。

4

3 に答える 3

14 
var arr = x.ToCharArray();
Array.Reverse(arr);
return new string(arr);

ただし、これにより Unicode 修飾子文字 (アクセントなど) が逆になることに注意してください。

基準：

Array.Reverse: 179ms
StringBuilder: 475ms

と：

static void Main()
{
    string text = new string('x', 100000);
    GC.Collect();
    GC.WaitForPendingFinalizers();
    var watch = Stopwatch.StartNew();
    const int LOOP = 1000;
    for (int i = 0; i < LOOP; i++)
    {
        var arr = text.ToCharArray();
        Array.Reverse(arr);
        string y = new string(arr);
    }
    watch.Stop();
    Console.WriteLine("Array.Reverse: {0}ms", watch.ElapsedMilliseconds);

    GC.Collect();
    GC.WaitForPendingFinalizers();
    watch = Stopwatch.StartNew();
    for (int i = 0; i < LOOP; i++)
    {
        var reverse = new StringBuilder(text.Length);
        for (int j = text.Length - 1; j >= 0; j--)
        {
            reverse.Append(text[j]);
        }
        string y = reverse.ToString();
    }
    watch.Stop();
    Console.WriteLine("StringBuilder: {0}ms", watch.ElapsedMilliseconds);
}

長さ 500 の文字列を試して 500000 回ループすると:

Array.Reverse: 480ms
StringBuilder: 1176ms

私もそれに追加しようとしunsafeました、つまり

fixed (char* c = text)
{
    for (int j = text.Length - 1; j >= 0; j--)
    {
        reverse.Append(c[j]);
    }
}

これは何の違いもありませんでした。

そして、JeffRSonの回答も追加しました。私は得る：

Array.Reverse: 459ms
StringBuilder: 1092ms
Pointer: 513ms

(長さ 500 x 5000 回の反復テストの場合)

于 2013-06-10T07:28:39.510 に答える
4

ポインターベースのソリューションは次のとおりです。

unsafe String Reverse(String s)
        {
            char[] sarr = new char[s.Length];
            int idx = s.Length;
            fixed (char* c = s)
            {
                char* c1 = c;
                while (idx != 0)
                {
                    sarr[--idx] = *c1++;
                }
            }

            return new String(sarr);
        }

配列インデックス (sarr[--idx]) を取り除くと、次の方法がより高速になる可能性があります。

unsafe String Reverse(String s)
        {
            char[] sarr = new char[s.Length];
            fixed (char* c = s)
            fixed (char* d = sarr)
            {
                char* c1 = c;
                char* d1 = d + s.Length;
                while (d1 > d)
                {
                    *--d1 = *c1++;
                }
            }

            return new String(sarr);
        }
于 2013-06-10T07:52:09.830 に答える
2

を作成するときに容量を設定しますStringBuilder。これにより、ループ中に容量が大きくなり、より多くのメモリを割り当てる必要がなくなります。パラメータはすでにローカル変数であるため、ローカル変数へのパラメータの割り当ては不要な手順です。

public static void ReverseFast(string text) {
  StringBuilder reverse = new StringBuilder(text.Length);
  for (int i = text.Length - 1; i >= 0; i--) {
    reverse.Append(text[i]);
  }
}

That is just the basic steps to remove any unneccesary work. If you really have a performance problem with the code, you would need to analyse what the generated code does, and possibly create different versions that do different things depending on the current framework and hardware.

于 2013-06-10T07:35:00.043 に答える