Pythonの低レベルと高水準のパフォーマンス（回文関数の実行時間解析）

Question

与えられた文字列が回文かどうかをチェックする最も効率的な方法を見つけようとしています。
まず、私はオーダーO（N）のランニングタイムを持つブルートフォースを試みました。次に、nの代わりにn/2の比較だけを行うことで、コードを少し最適化しました。ここ

コードである：

def palindrome(a): 
    length=len(a) 
    iterator=0 
    while iterator <= length/2: 
     if a[iterator]==a[length-iterator-1]: 
      iterator+=1 
     else: 
      return False 

    return True 

これは強引に比べて半分の時間を要するが、それは、（N）Oを注文依然としてあります。

一方、私はスライス演算子を使用する解も考えました。ここ
はコードです：

def palindrome_py(a): 
    return a==a[::-1] 

それから私は、両方の時間分析を実行しました。私が使用したコードはここにアクセスすることができ Running time

Length of string used is 50 
Length multiplier indicates length of new string(50*multiplier) 
Running time for 100000 iterations 

For palindrome For palindrome_py Length Multiplier 
0.6559998989  0.5309998989  1 
1.2970001698  0.5939998627  2 
3.5149998665  0.7820000648  3 
13.4249999523  1.5310001373  4 
65.5319998264  5.2660000324  5 

：Running Time Table Generator

は今、私はスライス演算子（palindrome_py）の時間を実行している間に差がある理由を知りたいと回文ここでの結果でありますなぜ私はこのタイプのランニングタイムを取得していますか？
なぜスライス演算子が回文関数と比較して効率が良いのですか？舞台裏で何が起こっていますか？

私の所見： 実行時間は乗数に比例します。 case（n-1）の実行時間を乗算することにより、乗数が2のときの走行時間を得ることができる。 （n）は、乗算、我々は（N-1）*乗数に（n）の上映時間=時間を走らie.2

一般化することによって、この場合の第一

Answer 1

あなたのスライスベースのソリューションは依然としてO（N）で、定数は小さくなりました（それはあなたの乗数です）。 Pythonでは処理量が少なく、C言語ではより多くの処理が行われるため、処理速度が向上します。バイトコードはすべてを示しています。

In [1]: import dis 

In [2]: %paste 
def palindrome(a): 
    length=len(a) 
    iterator=0 
    while iterator <= length/2: 
     if a[iterator]==a[length-iterator-1]: 
      iterator+=1 
     else: 
      return False 

    return True 

## -- End pasted text -- 

In [3]: dis.dis(palindrome) 
    2   0 LOAD_GLOBAL    0 (len) 
       3 LOAD_FAST    0 (a) 
       6 CALL_FUNCTION   1 (1 positional, 0 keyword pair) 
       9 STORE_FAST    1 (length) 

    3   12 LOAD_CONST    1 (0) 
      15 STORE_FAST    2 (iterator) 

    4   18 SETUP_LOOP    65 (to 86) 
     >> 21 LOAD_FAST    2 (iterator) 
      24 LOAD_FAST    1 (length) 
      27 LOAD_CONST    2 (2) 
      30 BINARY_TRUE_DIVIDE 
      31 COMPARE_OP    1 (<=) 
      34 POP_JUMP_IF_FALSE  85 

    5   37 LOAD_FAST    0 (a) 
      40 LOAD_FAST    2 (iterator) 
      43 BINARY_SUBSCR 
      44 LOAD_FAST    0 (a) 
      47 LOAD_FAST    1 (length) 
      50 LOAD_FAST    2 (iterator) 
      53 BINARY_SUBTRACT 
      54 LOAD_CONST    3 (1) 
      57 BINARY_SUBTRACT 
      58 BINARY_SUBSCR 
      59 COMPARE_OP    2 (==) 
      62 POP_JUMP_IF_FALSE  78 

    6   65 LOAD_FAST    2 (iterator) 
      68 LOAD_CONST    3 (1) 
      71 INPLACE_ADD 
      72 STORE_FAST    2 (iterator) 
      75 JUMP_ABSOLUTE   21 

    8  >> 78 LOAD_CONST    4 (False) 
      81 RETURN_VALUE 
      82 JUMP_ABSOLUTE   21 
     >> 85 POP_BLOCK 

10  >> 86 LOAD_CONST    5 (True) 
      89 RETURN_VALUE 

基本的にPythonで非常に高価な呼び出しを、機能しているPythonの仮想マシンレベルの命令、の地獄がたくさんあります。

ここで、2番目の機能は何ですか。ここに関与

In [4]: %paste 
def palindrome_py(a): 
    return a==a[::-1] 

## -- End pasted text -- 

    In [5]: dis.dis(palindrome_py) 
     2   0 LOAD_FAST    0 (a) 
        3 LOAD_FAST    0 (a) 
        6 LOAD_CONST    0 (None) 
        9 LOAD_CONST    0 (None) 
       12 LOAD_CONST    2 (-1) 
       15 BUILD_SLICE    3 
       18 BINARY_SUBSCR 
       19 COMPARE_OP    2 (==) 
       22 RETURN_VALUE 

ませんPythonの反復（ジャンパ）とあなただけの3つのコール（これらの命令は、メソッドを呼び出す）を取得：strは、すべてのメソッドを持つビルトインタイプですので、BUILD_SLICE、BINARY_SUBSCR、COMPARE_OP、Cで行われ、すべてを公平になるために、最初の関数では（ほかの多くの命令と同様に）同じ命令が見られましたが、メソッド呼び出しのオーバーヘッドにnを掛けて各文字ごとに繰り返します。ここでは、Pythonの関数呼び出しのオーバーヘッドを一度だけ支払っています。残りはC言語で行われます。

ボトムライン。 Pythonで低レベルの処理を手動で行うべきではありません。これは、高レベルのものよりも遅く実行されるためです（文字通り低レベルの魔法を必要とする漸近的に高速な代替手段がない限り）。 Pythonは、他の多くの言語とは異なり、ほとんどの場合、抽象化を使用することを推奨し、より高いパフォーマンスであなたに報酬を与えます。