24

このページには、興味深いものがあります。

(実際には) str キーのみを扱う dict の高速パスがあることに注意してください。これはアルゴリズムの複雑さには影響しませんが、一定の要因 (典型的なプログラムの終了速度) に大きな影響を与える可能性があります。

では、それは正確にはどういう意味ですか？

キーとして文字列を使用すると常に高速になるということですか?

はいの場合、なぜですか?

アップデート：

最適化についての提案をありがとう! しかし、私は実際には、最適化を行うべきかどうか、またはいつ行うべきかよりも、明白な真実に関心があります。

更新 2:

すばらしい回答をありがとうございます。@DaveWebb が提供するリンクの内容をここで引用します。

" ...

ma_lookupは、最初はlookdict_string関数 ( 3.0 でlookdict_unicodeに名前が変更されました) に設定されており、辞書内のキーと検索対象のキーの両方が標準の PyStringObject のものであると想定しています。文字列間の比較では例外が発生しないため、さまざまなエラー チェックを軽減するなど、いくつかの最適化を行うことができます。また、リッチ オブジェクトの比較も必要ありません。つまり、 PyObject_RichCompareBoolの呼び出しを避け、常に_PyString_Eqを直接使用します。

... "

また、実験数値については、int から string への変換がなければ、その差はさらに大きくなると思います

4

2 に答える 2

23

Python dict の基礎となる C コードは、String キーに対して最適化されています。 これについては、こちら(およびブログが参照している本) で読むことができます。

Python ランタイムは、辞書に文字列キーのみが含まれていることを認識している場合、文字列と文字列の比較では発生しないエラーに対応せず、豊富な比較演算子を無視するなどの操作を実行できます。これにより、文字列キーの一般的なケースがdict少しだけ速くなります。（更新：タイミングはそれが少し以上であることを示しています。）

ただし、これがほとんどの Python プログラムの実行時間に大きな変化をもたらす可能性は低いです。この最適化について心配する必要がdictあるのは、ルックアップを測定してコードのボトルネックであることが判明した場合のみです。 「時期尚早の最適化は諸悪の根源である」という有名な言葉があります。

物事が実際にどれだけ速いかを確認する唯一の方法は、時間を計ることです:

>>> timeit.timeit('a["500"]','a ={}\nfor i in range(1000): a[str(i)] = i')
0.06659698486328125
>>> timeit.timeit('a[500]','a ={}\nfor i in range(1000): a[i] = i')
0.09005999565124512

したがって、文字列キーを使用すると、キーと比較しても約 30% 高速でintあり、違いの大きさに驚いたことを認めざるを得ません。

于 2012-06-22T18:47:58.503 に答える
9

これは一定時間にのみ影響するため、まったく問題にならない可能性があります。本当に最適化する必要があるのは、非常に大きなデータセットを操作しているときだけです。これは何の影響も及ぼしません。

これが意味するのは、文字列をキーとして持つ小さな辞書がある場合、Pythonは高速になるということです。これは一般的な使用法であるため、最適化されています。

Ignacio Vazquez-Abramsが指摘しているように、キーを文字列に変換することは、それがdictの文字列であることから得られるわずかなブーストよりも（はるかに）コストがかかる可能性があります。

簡単に言うと、状況に関連するものを使用します。最適化は、必要がある場合にのみ実行する必要があります。以前は実行しないでください。

いくつかのテスト：

python -m timeit -s "a={key: 1 for key in range(1000)}" "a[500]"
10000000 loops, best of 3: 0.0773 usec per loop

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[\"500\"]"
10000000 loops, best of 3: 0.0452 usec per loop

python -m timeit -s "a={str(key): 1 for key in range(1000)}" "a[str(500)]"
1000000 loops, best of 3: 0.244 usec per loop

ご覧のとおり、文字列ベースのdictは高速ですが、キーの変換は比較すると非常にコストがかかり、ゲイン（および一部）が完全に軽減されます。

そうです、使用しているデータが辞書のキーとしてのみ使用されており、それらをどの形式で保存するかは重要ではない場合は、小さな辞書で文字列を使用することをお勧めします。実際には、これは非常にまれなケースです（おそらく、すでに文字列を使用しているでしょう）。

于 2012-06-22T18:43:58.463 に答える