Déjame intentar darle una oportunidad a esto para ver cuánto puedo matarlo. :-)
Entonces, para comenzar, debe poder crear un filtro de floración regular que permita un número finito de elementos con una probabilidad máxima de un falso positivo. Se requiere la adición de estas características a su filtro básico antes de intentar construir una implementación escalable.
Antes de que intentemos controlar y optimizar cuál es la probabilidad, podemos determinar cuál es la probabilidad para un tamaño de filtro de floración dado.
Primero dividimos el campo de bits según la cantidad de funciones hash (número total de bits / número de funciones hash = segmentos) para obtener k segmentos de bits que representan cada función hash, de modo que k bits siempre describe cada elemento.
Si aumenta el número de segmentos o el número de bits por segmento, la probabilidad de falsos positivos disminuirá.
También se deduce que a medida que se agregan elementos, más bits se establecen en 1, por lo que aumentan los falsos positivos. Nos referimos a esto como la "proporción de relleno" de cada sector.
Cuando el filtro contiene una gran cantidad de datos, podemos suponer que la probabilidad de falsos positivos para este filtro es la proporción de relleno elevada al número de segmentos (si tuviéramos que contar los bits en lugar de utilizar una relación, esto se simplifica en una permutación con problema de repetición).
Entonces, ¿cómo podemos averiguar cómo elegir una probabilidad de falsos positivos en un filtro de floración? Podemos modificar la cantidad de segmentos (que afectarán la proporción de relleno).
Para averiguar cuántas rebanadas deberíamos tener, comenzamos por averiguar la proporción de relleno óptima para una rebanada. Dado que la proporción de relleno se determina por el número de bits en un segmento que son 1 versus el número de bits que son 0, podemos determinar que cada bit permanecerá sin establecer con probabilidad de (100% - (1 / bits en un segmento) ). Ya que vamos a tener varios elementos insertados, tenemos otra permutación con problemas de reputación y expandimos los elementos a la proporción de relleno esperada, que es (100% - ((100% - (1 / bits en una porción)) ^ "elementos insertados")). Bueno, resulta que esto es muy similar a otra ecuación. En el documento, relacionan la proporción de relleno con otra ecuación, por lo que encaja perfectamente en una serie de taylor (1-e ^ (- n / m)). Después de un poco de esfuerzo con esto, resulta que la proporción de relleno óptima es siempre alrededor del 50%, independientemente de cualquiera de las variables que cambies.
Entonces, como la probabilidad de un filtro es la proporción de relleno elevada al número de cortes, podemos completar el 50% y obtener P = (50%) ^ k o k = log_2 (1 / P). Luego podemos usar esta función para calcular la cantidad de segmentos que deberíamos generar para un filtro dado en la lista de filtros para un filtro de floración escalable.
def slices_count(false_positive_probability):
return math.ceil(math.log(1 / false_positive_probability, 2))
Editar: Después de escribir esto, encontré una mención de la "regla del cincuenta por ciento" al leer sobre la asignación de memoria dinámica basada en el sistema Buddy en TAoCP Vol 1, pp 442-445 con un razonamiento mucho más limpio versus ajuste de la curva a (1-e ^ (- n / m)). Knuth también hace referencia a un documento "La regla del cincuenta por ciento revisado" con un poco de antecedentes sobre el concepto ( pdf disponible aquí ).