Bit vektörü vs boole değerleri performansının listesi

Question

Python'da bir kitapta bulduğum iki örneği (orijinal olarak Java'da yazılmış) çoğaltmaya çalışıyorum.

İki işlev, bir dizenin tekrarlanan karakterler içerip içermediğini kontrol eder. İlk işlev, bir bit vektörü olarak bir tamsayı (checker) kullanır, ikinci işlev ise sadece booleanların bir listesini kullanır. İşlevi bits kullanarak daha iyi bir performansa sahip olmayı beklerdim, ancak aslında daha da kötü performans gösteriyor.

Neden? Java'dan Python'a "çeviri" yaparken yanlış bir şey mi yazdım?

Not: basitlik için yalnızca küçük harfler (bir ziçin), özellikle bit vektör işlevini kullanın.

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

Sonuçlar:

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

orijinal Java işlevleri şunlardır:

tamsayılar Python değişmez referans sınıfları vardır çünkü

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

. Bu tamsayı işlemlerinin genel olarak yavaş olduğu anlamına gelir.

checker |= (1 << val) 

biz almak atama genişletirseniz:

checker = checker | (1 << val) 

Bu tek hat hafızasında iki yeni tamsayılar ayırır şu satırına bakın (Bu hatta python2 ints için de geçerlidir). Biri 1 << val ve biri bit için veya. Diğer taraftan, bir dizi elemanının atanması nesnelerin tahsis edilmesine gerek yoktur ve bu da daha hızlı olmasının sebebidir.

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

sürümüyle gelen timeit:

bir dize karakter çoğaltmak olup olmadığını belirlemek için en hızlı yol arıyorsanız, bu fonksiyon önceki iki ("check duplicates in list" alınan) daha kısa ve hızlı olduğunu

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

Not: sonuçlar olabilecek bir 3x hızlanma (son satır yeni biridir) gösterir Ben sadece yukarıdaki iki Java yöntemleri tercüme beri bunu dikkate almadı, ancak başvuru için yararlı olabilir: Başka bir piton çalışma zamanını kullanırsanız ağır değişir Gibi IronPython olarak