26

2 つの文字列の長さが長くなるにつれて比較が遅くなるかどうかを評価しようとしています。私の計算では、文字列の比較には償却定数時間がかかるはずですが、私の Python 実験では奇妙な結果が得られます。

これはミリ秒単位の時間に対する文字列の長さ (1 から 400) のプロットです。自動ガベージ コレクションは無効になっており、gc.collect反復ごとに実行されます。

時間と弦の長さ

毎回 100 万個のランダムな文字列を比較し、次のように一致を数えます。このプロセスは、測定されたすべての時間の最小値を取る前に 50 回繰り返されます。

for index in range(COUNT):
    if v1[index] == v2[index]:
        matches += 1
    else:
        non_matches += 1

長さが 64 付近で急激に増加した理由は何ですか?

注: 次のスニペットを使用して、が長さのランダムな文字列の 2 つのリストであり、COUNT がそれらの長さであると仮定v1して、問題の再現を試みることができます。v2n

timeit.timeit("for i in range(COUNT): v1[i] == v2[i]",
  "from __main__ import COUNT, v1, v2", number=50)

さらに注意: 私は 2 つの追加のテストを行いました:問題を完全isに抑制するのではなく文字列を比較する==と、パフォーマンスは約 210ms/1M の比較になります。インターンが言及されたので、各文字列の後に必ず空白を追加しました。これにより、インターンを防ぐことができます。それは何も変わりません。では、インターン以外の何かですか？

4

2 に答える 2

13

Pythonは短い文字列を「インターン」できます。それらを特別なキャッシュに保存し、そのキャッシュから文字列オブジェクトを再利用します。

次に文字列を比較するとき、最初に同じポインタ (インターンされた文字列など) であるかどうかをテストします。

if (a == b) {
    switch (op) {
    case Py_EQ:case Py_LE:case Py_GE:
        result = Py_True;
        goto out;
// ...

そのポインタ比較が失敗した場合にのみ、サイズ チェックを使用しmemcmpて文字列を比較します。

通常、インターンは識別子 (関数名、引数、属性など) に対してのみ行われますが、実行時に作成される文字列値に対しては行われません。

もう 1 つの考えられる原因は、文字列定数です。コードで使用される文字列リテラルは、コンパイル時に定数として格納され、全体で再利用されます。ここでもオブジェクトが 1 つだけ作成され、それらの ID テストが高速になります。

同じでない文字列オブジェクトの場合、Python は長さが等しいこと、最初の文字が等しいことをテストしてmemcmp()から、内部 C 文字列に対して関数を使用します。文字列がインターンされていないか、同じオブジェクトを再利用している場合、他のすべての速度特性はmemcmp()関数に帰着します。

于 2012-09-28T22:40:30.910 に答える
4

私は大雑把な推測をしているだけですが、あなたは「何ができるのか」ではなく「何ができるのか」と尋ねたので、いくつかの可能性があります:

  • CPU キャッシュ ラインのサイズは 64 バイトで、これより長い文字列はキャッシュ ミスを引き起こします。
  • Python は、64 バイトの文字列を 1 種類の構造に格納し、より長い文字列をより複雑な構造に格納する場合があります。
  • 最後の 1 つに関連して、文字列を 64 バイト配列にゼロで埋め、非常に高速な SSE2 ベクトル命令を使用して 2 つの文字列を一致させることができます。
于 2012-09-28T22:31:24.437 に答える