Pythonの2回のif-testよりもはるかに早い検索が辞書でなぜですか？

Question

私はコードを最適化しようとしているので、私はギガバイトのテキストを読む必要があります。これを行うと、私の問題では辞書を使うのがif-testよりも早いことがわかりました。 ipythongの％はtimeitを使用して

check = {'R':'-', 'F':'+'} 
seqs = ['R', 'F']*100 

def check1(): 
    for entry in seqs: 
     if entry == 'R': 
      strand = '-' 
     if entry == 'F': 
      strand = '+' 

def check2(): 
    for entry in seqs: 
     strand = check[entry] 

私は辞書で調べることは2であれば、テスト使用しての2倍の速さよりもわずかであることを確認：テストがあれば、とても基本的なもの、私がしたので

In [63]: %timeit check1() 
10000 loops, best of 3: 38.8 us per loop 

In [64]: %timeit check2() 
100000 loops, best of 3: 16.2 us per loop 

をパフォーマンスの違いは期待できません。これはよく知られていますか？なぜこれがそうだと誰が説明できますか？

UPDATE私は2つの以上の機能だけでなく、check3（）は以下の私の実際のコードの実行時間に影響を与える、との合計時間には影響がありませんどのようにチェック

。だから、辞書で得られたブーストは、実世界の例では「R」と「F」の値をファイルから絶えず読み直す必要があります。このコードはボトルネックの一部ではありません。

とにかく答えてくれてありがとう！

Answer 1

多くのVMコードと同様に、ほとんどの場合、関連するVMオペコードの数になります。

あなたがdisで組み立ての機能を調べることができる：2.6.4において

import dis 
dis.dis(func) 

を、CHECK1は各比較と分岐するため、（コードパスに応じて）の周り15-20オペコードをとります。 check2はちょうど7（グローバルに宣言された、欠けているchedict辞書を追加した後）です。

def check3(): 
    for entry in seqs: 
     if entry == 'R': 
      strand = '-' 
     else: 
      strand = '+' 

それは私のコンピュータ上のcheck2()よりも実際に高速です：

Answer 2

辞書はPythonで大幅に最適化されています。参照はO(1)です。これはハッシュテーブルのルックアップに過ぎず、テスト（O(n)）のシーケンスで得られる操作の数の半分の1つの「操作」だけです。

Answer 3

はこの何かを明らかにするだろう。

Answer 4

辞書での検索が2つのテストより速いことが実際に証明されていません。ifあなたが示していることは、その特定の辞書を見上げることは、その2つのテストよりも速いことです。

通常、辞書の検索にはいくつかのステップが必要です。一致するものを見つけるためにキーからハッシュを生成し、次にキーを比較して一致するものをテストします。場合によっては、ハッシュテーブルの衝突がある場合に複数の比較を行う必要があります。これらのステップは両方とも遅いかもしれませんが、一般的には文字列の方が高速ですが、ある特定のケースでは本当に高速で、その場合はヒットしました。

辞書は、コンパイル時に既知の識別子の形式に一致する短い文字列のキーを使用します。 Pythonは有用にあなたの文字列 'R'と 'F'を「インターン」します。テストで使用する文字列もコンパイル時に認識されるため、まったく同じインスタンスになります。これは、検索ルックアップの意味は、文字列キーだけを持つ辞書に特殊なバージョンの参照が使用され、ハッシュは常に事前計算されており、キー比較はアドレスを比較することによって行われます（少なくとも成功したときと、 2つのキーは決して失敗しません）。

あなたの実際のコードは、入力から文字列を読み込んでいると仮定しているので、 'R'の内部コピーはありません。つまり、各入力行のハッシュを計算する必要があります。アドレスは一致しないので、各テストの文字列比較関数を呼び出す必要があります。あなたはまだ文字列キーだけを持つためのいくつかの最適化を行い、少なくとも文字列ではないオブジェクトの汎用比較を行う必要はありません。

ifステートメントはオブジェクトタイプについて何も知らないため、毎回汎用の比較を行います。