Vectorizar las operaciones de Bloom Filter para numpy.
Cómo puedo utilizar las operaciones vectoriales de numpy para implementar un filtro de Bloom? Empecé desde https://www.geeksforgeeks.org/bloom-filters-introduction-and-python-implementation/ y modifiqué para admitir naive ndrray.
Nota: No estoy limitado a mmh3, esta fue la única biblioteca que me permitió utilizar el hash con semilla para generar múltiples funciones hash.
import numpy as np
import math
import mmh3
from bitarray import bitarray
class BloomFilter(object):
def init(self, items_count: int = 100_000, fp_prob : float = 0.01):
self.fp_prob = fp_prob
self.size = self.get_size(items_count, fp_prob)
self.hash_count = self.get_hash_count(self.size, items_count)
self.bit_array = bitarray(self.size)
self.bit_array.setall(0)
def add(self, item):
if type(item) is np.ndarray:
for i in item.reshape(-1):
self.add(i)
else:
digest = self.digest(item)
for pos in digest:
self.bit_array[pos] = True
def digest(self, item):
return [mmh3.hash(item, seed=i) % self.size for i in range(self.hash_count)]
def contains(self, item):
if type(item) is np.ndarray:
return np.array(
[self.contains(i) for i in item.reshape(-1)],
dtype=np.bool8
).reshape(item.shape)
else:
return all(self.bit_array[pos] for pos in self.digest(item))
@classmethod
def get_size(self, n, p):
return int(-(n * math.log(p))/(math.log(2)**2))
@classmethod
def get_hash_count(self, m, n):
return int((m/n) * math.log(2))
items = np.random.randint(size=1_000_000, low=0, high=2**60, dtype=np.int64)
set_of_items = BloomFilter(items.size, 0.001)
set_of_items.add(items)
items2 = np.random.randint(size=100_000, low=0, high=2**60, dtype=np.int64)
existing = set_of_items.contains(items2)
new_items = items2[~existing]
print(f”#{len(new_items)}”)
davy.ai
Para utilizar las operaciones vectoriales de
numpy
en la implementación de un filtro de Bloom, podemos modificar los métodosadd
ycontains
de la claseBloomFilter
.Para el método
add
, podemos utilizar el métodoreshape
denumpy
para asegurarnos de que el elemento de entrada sea unndarray
, y luego usar las operaciones vectorizadas denumpy
para iterar sobre el array y añadir elementos al filtro de Bloom. Esto mejorará el rendimiento al evitar cualquier iteración explícita utilizando buclesfor
.De manera similar, para el método
contains
, podemos remodelar el elemento de entrada a unndarray
y utilizar las operaciones vectorizadas denumpy
para comprobar si los elementos existen en el filtro de Bloom. Luego podemos remodelar la salida para que coincida con la forma de entrada.Aquí está la implementación modificada de la clase:
En esta implementación, al añadir un array de elementos, primero remodelamos el array utilizando
reshape(-1)
para asegurarnos de que sea un array unidimensional. Luego utilizamos el métodoarray
denumpy
para convertir la salida del métododigest
en un array denumpy
. Podemos usar este array para establecer las posiciones de bits correspondientes utilizandoself.bit_array[pos] = True
.De manera similar, al comprobar si un array de elementos existe en el filtro de Bloom, remodelamos el array de entrada utilizando
reshape(-1)
y utilizamos el métododigest
para obtener las posiciones de los bitsTrue
correspondientes en el filtro de Bloom. Luego convertimos estas posiciones en un array denumpy
y utilizamos este array para obtener los valores de los bits correspondientes enself.bit_array
. Finalmente, remodelamos la salida utilizandoreshape(item.shape)
para que coincida con la forma de entrada.