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

python performance arraylist bit-manipulation

857 просмотра

1 ответ

7309 Репутация автора

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

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

Почему это? Я что-то не так написал, "переводя" с Java на Python?

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

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;
}
Автор: Kurt Bourbaki Источник Размещён: 07.01.2016 10:35

Ответы (1)


4 плюса

20459 Репутация автора

Решение

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

checker |= (1 << val)

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

checker = checker | (1 << val)

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

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

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

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

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

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

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

Автор: Tamas Hegedus Размещён: 07.01.2016 12:29
Вопросы из категории :
32x32