Python. Проверить, входит ли элемент в коллекцию

Предположим, вы ведёте реестр монет. В нём записаны монетки всех времён, стран и достоинств. На вашем сайте любой может проверить, есть ли та или иная монета в реестре, и если нет — добавить её.

Как проверить, есть ли монета в реестре?

Список: очень, очень медленно

Можно так:

coins = ["1 aud", "5 ars", "1 byn", "10 ghs"]

def has(coin):
    return coin in coins

>>> has("1 byn")
True
>>> has("20 cny")
False

Конечно, так делать нехорошо. Операция element in list последовательно проверяет каждый элемент списка, то есть её сложность O(n). Незаметно на маленьких списках, но если у вас в реестре 1 млн монет, а с сайта приходит по тысяче запросов в секунду — начнёт тормозить:

>>> import random
>>> import timeit
>>> list_ = [str(random.random()) for _ in range(1_000_000)]
>>> elem = str(random.random())
>>> timeit.timeit(lambda: elem in list_, number=1000)
11.2

10 секунд на проверку тысячи элементов, пффф. Решение — использовать множества.

Множество: очень быстро, тяжеловесно

>>> set_ = set(str(random.random()) for _ in range(1_000_000))
>>> elem = str(random.random())
>>> timeit.timeit(lambda: elem in set_, number=1000)
0.00014

Операция element in set выполняется за O(1). На множестве проверка отработала в несколько десятков тысяч раз быстрее, чем на списке.

А что с памятью? Проверим:

from pympler import asizeof

def size_mb(obj):
    return round(asizeof.asizeof(obj) / 1024**2)

>>> size_mb(list_)
77
>>> size_mb(set_)
101

Множество оказалось в 1.3 раза тяжелее списка. Ничего, для миллиона монеток хватит. Но что делать, если в коллекции один миллиард объектов, тоже всё в память запихивать?

Фильтр Блума: быстро, легко, неуверенно

Для множества на 1 млн элементов получилось 140 микросекунд на 1000 проверок, 101 Мб в памяти.

Что если элементов будет 1 млрд? Это уже около 100 Гб, не хотелось бы держать их в памяти. Устроил бы компромиссный вариант, который работает медленнее, но занимает меньше места.

И он существует! Это фильтр Блума — специальная вероятностная структура данных. Она отвечает на вопрос «есть ли элемент в коллекции?» одним из двух вариантов:

• точно нет;
• возможно есть.

Вот как это работает:

>>> from bloom_filter import BloomFilter
>>> bloom = BloomFilter(max_elements=1_000_000, error_rate=0.001)
>>> for el in set_:
...   bloom.add(el)
>>> size_mb(bloom)
3

Фильтр Блума на 1 млн элементов с вероятностью ложно-положительного ответа 0.1% занимает всего 3 Мб (вместо 100 Мб «честного» множества). А что со скоростью?

>>> timeit.timeit(lambda: elem in bloom, number=1000)
0.015

15 миллисекунд — в 100 раз медленнее, чем проверка по множеству, но всё ещё достаточно быстро (например, в сотни раз быстрее проверки по списку).

Проверим на 1 млрд:

>>> bloom = BloomFilter(max_elements=1_000_000_000, error_rate=0.001)
>>> size_mb(bloom)
3428

Три с лишним гигабайта, рост линейный. Чудес не бывает, но выигрыш по памяти в 30 раз при сохранении приемлемой скорости иногда может вам пригодиться.