15

非常に長い文字列 (サイズが60MB ) があり、そこに '<' と '>' のペアがいくつあるかを見つける必要があります。

私は最初に自分の方法を試しました：

        char pre = '!';
        int match1 = 0;
        for (int j = 0; j < html.Length; j++)
        {
            char c = html[j];
            if (pre == '<' && c == '>') //find a match
            {
                pre = '!';
                match1++;
            }
            else if (pre == '!' && c == '<')
                pre = '<';
        }

上記のコードは、私の文字列で約1000 ms実行されます。

それから私は使ってみましたstring.IndexOf

        int match2 = 0;
        int index = -1;
        do
        {
            index = html.IndexOf('<', index + 1);
            if (index != -1) // find a match
            {
                index = html.IndexOf('>', index + 1);
                if (index != -1)
                   match2++;
            }
        } while (index != -1);

上記のコードは約150 ミリ秒しか実行されません。

こんなに速くstring.IndexOf走れる魔法は何だろう？

誰でも私にインスピレーションを与えることができますか？

編集

@BrokenGlassの回答によると、わかりました。ペアリングをチェックしないようにコードを変更しました。代わりに、文字列内の「<」の数をチェックします。

        for (int j = 0; j < html.Length; j++)
        {
            char c = html[j];
            if (c == '>')
            {
                match1++;
            }
        }

上記のコードは約760 ミリ秒実行されます。

使用するIndexOf

        int index = -1;
        do
        {
            index = html.IndexOf('<', index + 1);
            if (index != -1)
            {
                match2++;
            }
        } while (index != -1);

上記のコードは約132 ms実行されます。それでも非常に速い。

編集 2

@Jeffrey Sax のコメントを読んだ後、デバッグ モードで VS を実行していることに気付きました。

次に、リリースモードでビルドして実行しましたIndexOfが、それでも高速ですが、それほど高速ではありません。

結果は次のとおりです。

ペアリング回数：207ms VS 144ms

通常の 1 文字カウントの場合: 141ms VS 111ms。

私自身のコードのパフォーマンスは本当に改善されました。

教訓: ベンチマークを実行するときは、リリース モードで実行してください。

4

5 に答える 5

9

Visual Studio 内からタイミングを実行していますか? その場合、その理由だけでコードの実行が大幅に遅くなります。

それはさておき、あなたはある程度、リンゴとオレンジを比較しています。2 つのアルゴリズムは異なる方法で動作します。

このバージョンでは、開きかっこのみの検索と閉じかっこのみIndexOfの検索が交互に行われます。コードは文字列全体を処理し、開き括弧と閉じ括弧のどちらを探しているかを示すステータス フラグを保持します。これにはより多くの作業が必要であり、遅くなることが予想されます。

メソッドと同じ方法で比較を行うコードを次に示しますIndexOf。

int match3 = 0;
for (int j = 0; j < html.Length; j++) {
    if (html[j] == '<') {
        for (; j < html.Length; j++)
            if (html[j] == '>')
                match3++;
    }
}

IndexOf私のテストでは、これは実際にはメソッドよりも約 3 倍高速です。理由？文字列は、実際には個々の文字のシーケンスほど単純ではありません。マーカー、アクセントなどがあります。String.IndexOf余分な複雑さはすべて適切に処理されますが、コストがかかります。

于 2012-05-09T16:06:52.343 に答える
5

私の頭に浮かぶ唯一のことは、IndexOfiniside 文字列クラスの実際の実装です。

callvirt    System.String.IndexOf

これは、リフレクターの力を（可能な限り）使用すると、最終的に

CompareInfo.IndexOf(..)

代わりに、超高速の Windows ネイティブ関数FindNLSStringを使用します。

ここに画像の説明を入力

于 2012-05-09T16:15:18.920 に答える
4

String.IndexOfマネージド実装とメソッドを直接比較するのは少し誤りです。の実装IndexOfは主にネイティブ コードであるため、マネージ実装とは異なる一連のパフォーマンス特性があります。特に、ネイティブ コードでは、マネージド アルゴリズムの CLR によって挿入されるタイプ セーフティ チェックとそれに対応するオーバーヘッドを回避します。

1 つの例は、配列インデックスの使用です。

char c = html[j];

マネージ コードでは、このステートメントは がj配列への有効なインデックスであることを確認しhtml、値を返します。同等のネイティブ コードは、メモリ オフセットを返すだけで、追加のチェックは必要ありません。このチェックの欠如は、ループの反復ごとに追加の分岐命令を回避できるため、ここでネイティブ コードに固有の利点を提供します。

この利点は絶対的なものではないことに注意してください。JIT はこのループをよく調べてj、無効なインデックスではないことを判断し、生成されたネイティブ コードのチェックを省略します (場合によっては IIRC でこれを行います)。

于 2012-05-09T16:25:42.083 に答える
1

各反復で開始文字と終了文字の両方string.IndexOfをチェックするため、最初のコードサンプルと比較して、(そこで実行される可能性のある他の最適化を除いて) 少なくとも 2 倍の速度で実行されると予想されます。一方、実装は、開始文字が正常に見つかった後にのみ終了文字をチェックします。これにより、各反復での操作の数が大幅に削減されます (比較が 1 つ少なくなります)。string.IndexOf

于 2012-05-09T15:46:14.903 に答える
1

if テストの代わりに switch ステートメントを使用すると、速度も少し速くなります。このコードは、私のマシンの indexof コードよりも優れていることがあります。

        int count = 0;
        bool open = false;
        for (int j = 0; j < testStr.Length; j++)
        {  
            switch (testStr[j])
            {
                case '<':
                    open = true;
                    break;
                case '>':
                    if (open)
                       count++;

                    open = false;
                    break;         
            }
        }
于 2012-05-09T16:32:29.063 に答える