2

別のコードで 2 番目のものを見たことがありますが、この長さの比較はコードの生産性を高めるために行われたと思います。特定の辞書を持つスクリプト言語のパーサーで使用されました。単語は 4 ～ 24 文字で平均 7 ～ 8 文字で、アルファベットには 26 文字のラテン文字と "@"、"$"、"_" が含まれます。

長さの比較は、STL 文字列を操作する == 演算子をエスケープするために使用されました。これには、単純な整数比較よりも明らかに時間がかかります。しかし同時に、与えられた辞書の最初の文字の分布は単語サイズの分布より単純に広いため、文字列を比較する際の最初の 2 文字は、通常、その文字列のサイズよりも異なることがよくあります。これにより、長さの比較が不要になります。

私はいくつかのテストを実行しましたが、それが私が見つけたものです.2つのランダムな文字列の比較を何百万回もテストしていますが、2番目の方法ははるかに高速であるため、長さの比較が役立つようです. しかし、実際のプロジェクトでは、デバッグ モードではさらに遅くなり、リリース モードでは不十分なほど速くなります。

だから、私の質問は、なぜ長さの比較が比較を速くすることができ、なぜそれを遅くすることができるのですか?

UPD: 私はその 2 番目の方法も好きではありませんが、それには理由があると思います。

UPD2: 真剣に、問題は最善を尽くす方法ではありません。この場合、STL 文字列はもう使用していません。長さの比較が不必要で間違っていることなども不思議ではありません。これはどのように可能ですか？

4

9 に答える 9

32

それが重要な場合は、ライブラリが既にそれを行っていると想定してください。本当に重要でない限り、マイクロ最適化のためにこのようにコードを台無しにしないでください。

于 2008-10-09T09:18:00.617 に答える
12

短絡が有益になるのはいつですか

短絡の最適化は、次の場合にのみ役立ちます。

  • 比較のコストは、完全なテストのコストに比べて低い
  • 比較はしばしば短絡につながります

数学的に、S を短絡状態のコスト、F を完全な状態のコスト、P を短絡が発生するケースの割合 (完全な状態は必要ありません) とします。

元のケース (短絡なし) の平均コストは F

短絡最適化の平均コストは S + F * (1-P) です。

したがって、最適化によって何らかのメリットが得られるようにするには、以下を適用する必要があります。

S + F * (1-P) < F

すなわち

S < F*P

文字列比較コスト

さらにあなたは書いた：

これは明らかに単純な整数比較よりも時間がかかります。

これはまったく明らかではありません。文字列比較は、最初の相違点が見つかった時点で終了するため、処理する文字列によっては、ほとんどの場合、最初または 2 番目の文字で終了する場合があります。さらに、両方の文字列に十分なデータがある限り、最初に DWORDS (一度に 4 文字) を比較することにより、長い文字列の場合でも比較を最適化できます。

あなたの場合

ランダム テスト データとスクリプト解析の主な違いは、実際のデータがランダムではないことです。パーサーは決定論的である可能性が高く、一致するとそれ以上比較しません。スクリプト データでさえランダムではありません。一部のキーワードは、他のキーワードよりも多く使用される可能性があります。パーサーが、最も一般的に使用されるキーワードを最初にチェックするように構築されている場合、文字列が一致する場合は常に完全な比較を行う必要があるため、驚くほど多くの比較で完全な比較を行う必要があります。

于 2008-10-09T11:17:25.447 に答える
5

通常、これは STL に任せるべきであり、気にする必要はありません。

ただし、これが最適化する必要がある領域である場合 (私は真剣に疑っています)、かつ文字列の文字分布/長さ分布を理解している場合は、文字列から新しいクラスを派生させ、== 演算子をオーバーロードして実行することができます。アプリケーションにとって最も効率的な方法で等価性テストを行います。(長さが最初、最初の文字が最初、前方、後方など)。

これは、「最適化」をコード全体に分散させるよりも優れています。

于 2008-10-09T09:29:43.150 に答える
4

ランダム テストでは、文字列はゲインを示すのに十分な長さであった可能性がありますが、実際のケースでは、より短い文字列を処理することができ、テストの文字列比較部分を実行しないことによるゲインによって 2 の定数係数が相殺されることはありません。

于 2008-10-09T09:19:06.510 に答える
4

std::string operator== の実装では、最初に長さをチェックするか、文字のチェックを開始するかを知る方法がありません。明らかに長さをチェックするのは、同じ長さの文字列に対して無駄です。したがって、STL の実装が異なれば、パフォーマンスも異なる可能性があります。

プロファイラーが利点を確認した場合にのみ、明示的な長さチェックを最終的な最適化 (そのように明確にコメントされています) として入れてください。

于 2008-10-09T09:22:07.940 に答える
1

長さの比較は私には意味がありません..比較演算子を使用するだけで十分です

于 2008-10-09T09:39:05.707 に答える
0

STL の実装を起動します。それは問題ではありません

于 2008-10-09T09:15:48.063 に答える
0

長さの比較は、短絡の最適化を試みるためにあります。

長さの比較は完全な文字列の比較よりも高速であると想定しているため、99% の不一致を排除できれば、毎回完全な文字列の比較を行うよりも高速になります。

コードは長さの比較を実行しますが、失敗し、完全な文字列の比較を無視してコードをスキップします。

于 2008-10-09T10:51:16.217 に答える
0

std::string の長さは、おそらく std::string オブジェクトのメンバーです。それに比べて、最初の文字はヒープ上にある可能性が非常に高いです。つまり、文字列の長さを比較すると、参照の局所性が向上します。もちろん、短い文字列の最適化では、これはさらに複雑になります。スタック上にあるLhs[0]ときにヒープ上にある可能性があります。Rhs[0]

于 2008-10-14T11:51:05.473 に答える