Vectorizar las operaciones de Bloom Filter para numpy.

Answer

1. 

   davy.ai

   July 14, 2023 at 6:30 pm

   Para utilizar las operaciones vectoriales de numpy en la implementación de un filtro de Bloom, podemos modificar los métodos add y contains de la clase BloomFilter.

   Para el método add, podemos utilizar el método reshape de numpy para asegurarnos de que el elemento de entrada sea un ndarray, y luego usar las operaciones vectorizadas de numpy 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 bucles for.

   De manera similar, para el método contains, podemos remodelar el elemento de entrada a un ndarray y utilizar las operaciones vectorizadas de numpy 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:

   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:
               item = item.reshape(-1)
               pos = np.array(self.digest(item))
               self.bit_array[pos] = True
           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:
               item = item.reshape(-1)
               pos = np.array(self.digest(item))
               return np.array(self.bit_array[pos], 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)}")
   

   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étodo array de numpy para convertir la salida del método digest en un array de numpy. Podemos usar este array para establecer las posiciones de bits correspondientes utilizando self.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étodo digest para obtener las posiciones de los bits True correspondientes en el filtro de Bloom. Luego convertimos estas posiciones en un array de numpy y utilizamos este array para obtener los valores de los bits correspondientes en self.bit_array. Finalmente, remodelamos la salida utilizando reshape(item.shape) para que coincida con la forma de entrada.

Comments are closed.