Преобразование набора целых чисел в битовый массив для поиска с эффективным использованием памяти

У меня есть набор из 150 миллионов целых чисел в Python, которые я хотел бы использовать для фильтрации данных. Каждое из этих целых чисел является «идентификатором пользователя», хранящимся в 32-битном формате, и я хочу удалить всех пользователей, которые есть в наборе. Набор слишком велик, так как мне нужно передать его множеству воркеров в кластере, где у каждого воркера есть ограниченный объем памяти. Поскольку мне нужно только двоичное значение (пользователь установлен / не установлен), кажется возможным сделать это с помощью битового массива.

Идентификаторы начинаются с 0 и заканчиваются примерно 300M (т.е. половина пользователей входит в набор). Весь битовый массив должен иметь значение False (т.е. 0), за исключением местоположений, содержащихся в наборе целых чисел.

Я просмотрел пакет bitstring и bitarray package, но я не уверен, что лучше для моей цели и как мне это сделать. Может ли кто-нибудь дать руководство или небольшой пример того, как преобразовать мой набор в битовый массив, а затем выполнить поиск с его помощью?


python int bitarray
person pir    schedule 07.06.2017    source источник
comment
Есть ли причина, по которой вы не можете использовать фильтр Блума? Это звучит как точный вариант использования для них.   -  person JacaByte    schedule 07.06.2017

Ответы (1)


arrow_upward
1
arrow_downward

Лично я предпочитаю bitarray и предполагаю, что у вас есть такой набор (только большего размера):

# Just some random set
myset = {5, 27, 142, 824}

Затем вы можете использовать bitarray для создания bitarray (соответствующей длины), содержащего только False:

from bitarray import bitarray
ba = bitarray(1000)  # length 1000
ba.setall(False)     # contains only zeros

Однако нет встроенной поддержки для создания одного из set, поэтому вам понадобится цикл для установки соответствующих значений:

for item in myset:
    ba[item] = True

И вы можете проверить, есть ли значение, индексируя:

print(ba[5])   # True
print(ba[6])   # False
print(ba[27])  # True
person MSeifert    schedule 07.06.2017