Bit Vektor vs Liste der booleschen Werte Leistung

Question

Ich versuche, in Python zwei Beispiele zu reproduzieren (ursprünglich in Java geschrieben), die ich in einem Buch gefunden habe.

Die zwei Funktionen prüfen, ob eine Zeichenfolge wiederholte Zeichen enthält. Die erste Funktion verwendet eine Ganzzahl (checker) als einen Bitvektor, während die zweite Funktion einfach eine Liste von Booleschen Werten verwendet. Ich hatte erwartet, eine bessere Leistung mit der Funktion mit Bits zu haben, aber eigentlich ist es schlechter.

Warum ist das? Habe ich beim "Übersetzen" von Java nach Python etwas falsch geschrieben?

Hinweis: der Einfachheit halber nur wir Kleinbuchstaben (ein zu z), insbesondere für die Bit-Vektorfunktion.

import sys 
import timeit 

def is_unique_chars_bit(my_str): 
    checker = 0 
    for char in my_str: 
     val = ord(char) - ord('a') 
     if ((checker & (1 << val)) > 0): 
      return False 
     checker |= (1 << val) 
    return True 

def is_unique_chars_list(my_str): 
    if len(my_str) > 128: 
     # Supposing we use ASCII, which only has 128 chars 
     return False 
    char_list = [False] * 128 
    for char in my_str: 
     val = ord(char) 
     if char_list[val]: 
      return False 
     char_list[val] = True 
    return True 

if __name__ == '__main__': 
    alphabet = "abcdefghijklmnopqrstuvwxyz" 
    t_bit = timeit.Timer("is_unique_chars_bit('"+ alphabet +"')", "from __main__ import is_unique_chars_bit") 
    t_list = timeit.Timer("is_unique_chars_list('"+ alphabet +"')", "from __main__ import is_unique_chars_list") 
    print(t_bit.repeat(3, 200000)) 
    print(t_list.repeat(3, 200000)) 

Ergebnisse:

[1.732477278999795, 1.7263494359995093, 1.7404333820004467] 
[0.6785205180003686, 0.6759967380003218, 0.675434408000001] 

Die ursprünglichen Java-Funktionen sind die folgenden:

boolean isUniqueCharsBoolArray(String str) { 
    if (str.length() > 128) return false; 

    boolean[] char_set = new boolean[128]; 
    for (int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i); 
     if (char_set[val]) { 
      return false; 
     } 
     char_set[val] = true; 
    } 
    return true; 
} 

boolean isUniqueCharsBits(String str) { 
    for (int i = 0; i < str.length(); i++) { 
     int val = str.charAt(i) -'a'; 
     if ((checker & (1 << val)) > 0) { 
      return false; 
     } 
     checker |= (1 << val); 
    } 
    return true; 
} 

Answer 1

Das liegt daran, dass ganze Zahlen unveränderlichen Referenz Klassen in Python sind. Dies bedeutet, dass ganzzahlige Operationen im Allgemeinen langsam sind. (Dies gilt auch für python2 Ints) Schauen Sie sich die folgende Zeile ein:

checker |= (1 << val) 

Wenn wir den Auftrag erweitern, erhalten wir:

checker = checker | (1 << val) 

Diese einzelne Zeile weist zwei neue Zahlen im Speicher. Eine für 1 << val und eine für die bitweise oder.

Auf der anderen Seite muss ein Array-Element keine Objekte zuweisen, und das ist der Grund, dass es schneller ist.

Wenn Sie auf dem schnellsten Weg suchen, um zu bestimmen, ob ein String Zeichen duplizieren hat, ist diese Funktion kürzer und schneller als die beiden vorhergehenden (aus "check duplicates in list"):

def is_unique_chars_set(my_str): 
    return len(my_str) != len(set(my_str)) 

timeit zeigt einen 3x Speedup (die letzte Zeile ist die neue):

>python3 test.py 
[2.398782472571393, 2.3595238689519626, 2.37358552995787] 
[1.0055455609592512, 1.007462347465074, 1.012826469701654] 
[0.32564058749026437, 0.3303359144351621, 0.31772896318809885] 

Hinweis: die Ergebnisse können stark variieren, wenn Sie eine andere Python-Laufzeit verwenden, z. B. IronPython