Python Low-Level-vs High-Level-Performance (Laufzeitanalyse von Palindrom-Funktionen)

Question

Ich versuche, den effizientesten Weg zu finden, um zu überprüfen, ob die angegebene Zeichenfolge Palindrom ist oder nicht.
Zuerst versuchte ich Brute Force, die Laufzeit der Ordnung O (N) hat. Dann habe ich den Code ein wenig optimiert, indem ich nur n/2 Vergleiche anstelle von n gemacht habe. Hier

ist der Code:

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 

Es dauert eine halbe Zeit, als auf rohe Gewalt verglichen, aber es ist immer noch bestellen O (N).

Inzwischen dachte ich auch an eine Lösung, die Slice-Operator verwendet.
Hier ist der Code:

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

Dann habe ich Zeit Analyse der beiden läuft. Hier ist das Ergebnis: 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 

Der Code, den ich hier zugegriffen verwendet werden kann: Running Time Table Generator

Nun, ich möchte wissen, warum es einen Unterschied zwischen der Zeit der Schicht Bediener läuft (palindrome_py) und dem Palindrom Funktion.Warum bekomme ich diese Art von Laufzeit?
Warum ist der Slice-Operator so effizient wie im Vergleich zur Palindrome-Funktion? Was passiert hinter den Kulissen?

Meine Beobachtungen-: Laufzeit ist proportional zum Multiplikator dh. Laufzeit, wenn der Multiplikator 2 ist, kann durch Multiplizieren der Laufzeit des Falls (n-1) erhalten werden, dh. 1. in diesem Fall durch den Multiplizierer (n) ie.2

Verallgemeinern uns Zeit zum Laufen bringen (n) = Laufzeit (n-1) * Multiplikator

Answer 1

Ihre Slicing-basierte Lösung ist immer noch O (n) , die Konstante wurde kleiner (das ist dein Multiplikator). Es ist schneller, weil in Python weniger und in C mehr erledigt wird. Der Bytecode zeigt alles.

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 

Es gibt eine Hölle vielen Python virtuellen Maschine-Level-Befehle, die im Grunde Funktionsaufrufe, die in Python sehr teuer sind.

Nun, was ist mit der zweiten Funktion.

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 

Keine Python Iteration (Jumper) hier beteiligt und Sie bekommen nur drei Anrufe (diese Anweisungen rufen Methoden): BUILD_SLICE, BINARY_SUBSCR, COMPARE_OP, alle in C getan, weil str ein Typ mit allen Methoden in Einbau ist geschrieben C. Um fair zu sein, haben wir die gleichen Anweisungen in der ersten Funktion (zusammen mit vielen anderen Anweisungen) gesehen, aber dort werden sie für jedes Zeichen wiederholt, wobei der Methodenaufruf-Overhead mit n multipliziert wird. Hier bezahlen Sie nur den Funktionsaufruf-Overhead von Python, der Rest ist in C erledigt.

Die Quintessenz. Du solltest keine Low-Level-Sachen in Python manuell machen, weil es langsamer läuft als ein High-Level-Gegenstück (es sei denn, du hast eine asymptotisch schnellere Alternative, die buchstäblich Low-Level-Magie erfordert). Im Gegensatz zu vielen anderen Sprachen ermutigt Python die meiste Zeit dazu, Abstraktionen zu verwenden und Sie mit höherer Leistung zu belohnen.