¿Cuál es el mejor momento y espacio: filtro Bloom, tabla Hash o Diccionario?

Question

Necesito almacenar 4000 cadenas de tamaño fijo (8 caracteres) en C#, pero no sé qué es lo mejor para usar con respecto al espacio y tiempo de agregar y recuperar el elemento: filtro Bloom, tabla Hash o Diccionario? Por favor, si alguien me puede ayudar

Answer 1

En esta pregunta, realmente solo tiene dos estructuras de datos en C# ya que los diccionarios en C# se implementan usando tablas hash. Por lo tanto, nos referiremos a Dictionary y HashTable como tablas hash. Si usa uno de ellos, entonces probablemente desee Diccionario debido a la seguridad y el rendimiento como se describe aquí: Why is Dictionary preferred over hashtable? Pero como un Diccionario se implementa utilizando una tabla hash, no hay una gran diferencia en ambos sentidos.

Pero la verdadera pregunta es la tabla hash (Diccionario) versus el filtro Bloom. Alguien ya ha hecho la pregunta relacionada, What is the advantage to using bloom filters? También enlazan a la página de Wikipedia en los filtros Bloom, que es bastante informativo: https://en.wikipedia.org/wiki/Bloom_filter Las versiones cortas de la respuesta dicen que los filtros Bloom son más pequeños y rápidos. Sin embargo, tienen un costo asociado con esto: no son completamente precisos. En una tabla hash, la cadena original siempre se almacena para una comparación exacta. Primero, hash el valor y esto te dice dónde mirar en la tabla. Una vez que haya buscado en la tabla, luego verifique el valor ubicado allí contra el valor que está buscando. En un filtro Bloom, usa múltiples valores hash para calcular un conjunto de ubicaciones. Si hay 1 en todas esas ubicaciones, entonces considera que se encuentra la cadena. Esto significa que a veces se "encontrarán" cadenas que no se insertaron originalmente. Si la mesa es demasiado pequeña, de hecho, podrías alcanzar un punto de saturación en el que pareciera que cualquier cuerda que probaras estaría en el filtro Bloom. Como sabe cuántas cadenas va a insertar, puede ajustar el tamaño de la tabla de forma adecuada para evitar esto.

Veamos los tamaños involucrados. Para hacer que los números salgan limpiamente, voy a pretender que tienes exactamente 4096 cuerdas. Para tener una tabla hash de colisión relativamente baja, le recomendamos que su tabla sea al menos tan grande como el número de cadenas. Entonces, de manera realista (suponiendo punteros de 32 bits (4 bytes)), en este caso, estaría buscando un tamaño de 4096 * 4 bytes = 16K para la tabla, más 4096 * (4 + 4 + 8) = 64K para los nodos de lista (puntero siguiente + puntero de cadena) y cadenas. Entonces, en total, probablemente alrededor de 80K, que probablemente no sea mucha memoria en la mayoría de las situaciones donde usaría C#.

Para los filtros Bloom, tenemos que decidir la tasa de error que queremos apuntar en nuestros cálculos de tamaño. Cuando hablamos de una tasa de error del 1%, significaría que de cada 100 cadenas que no se insertaron en el filtro Bloom, 1 estaría falsamente indicado como presente. Las cadenas que se insertaron siempre se indicarán correctamente como insertadas. Usando la ecuación m = -n * ln (p)/(ln (2)^2), podemos calcular el tamaño mínimo para darnos una cierta tasa de error. En esa ecuación, m es el número de ranuras en la tabla, p es la tasa de error, y n es el número de cadenas que se insertarán. Entonces, si establecemos que p es 0.01 (error del 1%), obtenemos aproximadamente 9.6 * 4096 bits = 9.6 * 512 bytes = 4.8K, que obviamente es un poco más pequeño. Pero, realmente, el 1% es algo así como una tasa de error. Así que más, de manera realista, probablemente deberíamos buscar algo más como 0.0001% que sale a 28.8 * 4096b bits = 28.8 * 512 bytes = 14.4K. Obviamente, cualquiera de ellos es sustancialmente más pequeño que el 80K que calculamos para la tabla hash. Sin embargo, la tabla hash tiene una tasa de error de 0 que claramente es inferior al 1% o al 0,0001%.

Así que, en realidad, depende de usted si, en su situación, vale la pena perder la precisión para ganar un poco de velocidad y un poco de tiempo. De manera realista, cualquiera de las dos opciones es lo suficientemente pequeña y rápida para la gran mayoría de las situaciones del mundo real.

Answer 2

A System.Collections.Hashtable en .NET 1.0 es realmente lo mismo que System.Collections.Generic.Dictionary, que se presenta en .NET 2.0.

Le sugiero que utilice Dictionary, ya que es type safe especificando su clave y su tipo de valor. Hashtable solo toma un tipo de objeto, tendrá que convertirlo a una cadena cada vez que recupere los datos.

Answer 3

Un diccionario es un tipo de datos abstracto que representa un mapeo de un tipo a otro. No especifica cuál es la implementación del diccionario: podría respaldarse con una tabla hash, un árbol de búsqueda binaria equilibrado, una lista de omisiones o una de muchas otras estructuras. Probablemente no sea apropiado aquí, porque un diccionario asocia un tipo de elementos con otro tipo. No estás haciendo esto, solo te preocupa almacenar elementos, por lo que probablemente sea inapropiado.

Un Bloom filtrar es una estructura de datos probabilístico que es bueno para comprobar si es o no un elemento es, sin duda no en un conjunto, pero no se puede decir con seguridad si algo es en el conjunto. Se usa comúnmente en sistemas distribuidos para evitar lecturas de red innecesarias. Cada computadora puede almacenar un filtro Bloom de las entradas que pueden estar en una base de datos, y puede filtrar llamadas de red obviamente innecesarias al no consultar un sistema remoto si el filtro descarta una entrada. No es muy bueno para lo que estás tratando de hacer, ya que los falsos positivos son probablemente un factor decisivo.

La tabla de hash , sin embargo, es una excelente estructura de datos para lo que usted desea. Admite búsquedas e inserciones rápidas de elementos y, con una buena implementación, puede ser extremadamente eficiente con la memoria. Sin embargo, no almacena los elementos en orden, lo que puede ser un problema según su aplicación.

Si desea orden, hay otras dos estructuras que quizás desee considerar. El primero sería un árbol de búsqueda binaria equilibrada , que admite búsqueda rápida y eliminación y almacena elementos en orden ordenado. Hay muchas implementaciones buenas por ahí; prácticamente todos los buenos lenguajes de programación se entregan con una implementación. El otro es trie, que admite búsquedas y accesos muy rápidos y mantiene el orden ordenado. Puede ser un poco ineficiente en cuanto a espacio dependiendo de la distribución de sus cadenas, pero podría ser exactamente lo que está buscando.

Espero que esto ayude!