Wektor bitowy vs lista wartości boolean wydajność

Question

Próbuję odtworzyć w Pythonie dwa przykłady (pierwotnie napisane w Javie), które znalazłem w książce.

Obie funkcje sprawdzają, czy ciąg zawiera powtarzające się znaki. Pierwsza funkcja używa liczby całkowitej (checker) jako wektora bitowego, podczas gdy druga funkcja po prostu używa listy wartości logicznych. Spodziewałem się lepszej wydajności przy użyciu funkcji z bitami, ale w rzeczywistości działa gorzej.

Dlaczego tak jest? Czy napisałem coś nie tak podczas "tłumaczenia" z Java na Python?

Uwaga: dla uproszczenia używamy tylko małe litery ( do oo), zwłaszcza w przypadku funkcja nieco wektorowych.

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)) 

Wyniki:

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

Oryginalne funkcje Java są następujące:

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

To dlatego, że liczby całkowite są niezmienne Klasy referencyjne w Pythonie. Oznacza to, że operacje na liczbach całkowitych są ogólnie powolne. (Jest to prawdą nawet wskazówki python2) Spójrz na następującą linię:

checker |= (1 << val) 

Jeśli rozszerzymy zadanie otrzymujemy:

checker = checker | (1 << val) 

Ta pojedyncza linia przydziela dwa nowe liczb całkowitych w pamięci. Jeden dla 1 << val i jeden dla bitowego lub.

Z drugiej strony, przypisanie elementu tablicy nie wymaga przydzielania obiektów, i dlatego jest szybsze.

Jeśli szukasz najszybszy sposób, aby ustalić, czy ciąg ma powielać znaków, funkcja ta jest krótszy i szybciej niż poprzednie dwa (wzięte z "check duplicates in list"):

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

timeit pokazuje przyspieszenie 3x (ostatnia linia jest nowy):

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

Uwaga: wyniki mogą różnią się mocno, jeśli używasz innego środowiska wykonawczego Pythona, takiego jak IronPython