Bit vettoriale vs elenco di valori booleani prestazioni

Question

Sto cercando di riprodurre in Python due esempi (originariamente scritti in Java) che ho trovato in un libro.

Le due funzioni verificano se una stringa contiene caratteri ripetuti. La prima funzione utilizza un numero intero (checker) come vettore di bit, mentre la seconda funzione utilizza semplicemente un elenco di valori booleani. Mi aspettavo di ottenere prestazioni migliori usando la funzione con i bit, ma in realtà peggiora.

Perché è quello? Ho scritto qualcosa di sbagliato mentre "traducevo" da Java a Python?

Nota: per semplicità usiamo solo lettere minuscole (un per z), soprattutto per la funzione di vettore di bit.

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

Risultati:

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

Le funzioni Java originali sono i seguenti:

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

Questo è perché gli interi sono classi di riferimento immutabili in pitone. Ciò significa che le operazioni su interi sono lente in generale. (Questo è vero anche per interi python2) Guardate la seguente riga:

checker |= (1 << val) 

Se ci espandiamo l'assegnazione otteniamo:

checker = checker | (1 << val) 

Questa singola linea assegna due nuovi numeri interi in memoria. Uno per 1 << val e uno per bit per bit o.

D'altra parte, l'assegnazione di un elemento di matrice non ha bisogno di allocare oggetti, e questo è il motivo per cui è più veloce.

Se stai cercando il modo più veloce per determinare se una stringa ha duplicato caratteri, questa funzione è più breve e veloce rispetto alle due precedenti (tratto da "check duplicates in list"):

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

timeit mostra un aumento di velocità 3x (l'ultima riga è il nuovo):

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

Nota: I risultati possono varia notevolmente se si utilizza un altro runtime python, come IronPython