Бит-вектор против списка значений логических значений

Question

Я пытаюсь воспроизвести в Python два примера (изначально написанных на Java), которые я нашел в книге.

Две функции проверяют, содержит ли строка повторяющиеся символы. Первая функция использует целое число (checker) в качестве битового вектора, а вторая функция просто использует список логических элементов. Я ожидал лучшей производительности, используя функцию с битами, но на самом деле она хуже работает.

Почему? Я написал что-то неправильно во время «перевода» с Java на Python?

Примечание: для простоты мы используем только строчные буквы ( к г), особенно для функции битового вектора.

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

Результаты:

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

Оригинальные Java функции являются следующие:

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

Это потому, что целые числа являются неизменные ссылки на классы в Python. Это означает, что операции с целым числом в целом медленны. (Это справедливо даже для python2 Интс) Посмотрите на следующую строку:

checker |= (1 << val) 

Если мы расширим задание мы получаем:

checker = checker | (1 << val) 

Это одна строка выделяет два новых целых чисел в памяти. Один для 1 << val и один для поразрядного или.

С другой стороны, назначение элемента массива не требует выделения объектов, и это причина, по которой это происходит быстрее.

Если вы ищете самый быстрый способ, чтобы определить, является ли строка содержит повторяющиеся символы, эта функция короче и быстрее, чем предыдущие два (взято из "check duplicates in list"):

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

Timeit показывает 3x ускорение (последняя линия является новый):

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

Примечание: результаты могут сильно отличаются, если вы используете другую среду исполнения python, такую ​​как IronPython