¿Contenedor rápido para configurar bits en un dominio disperso e iterar (C ++)?
https://stackoverflow.com/questions/311297
-
10-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
RussianPregunta
Necesito un contenedor rápido con solo dos operaciones. Insertar claves desde un dominio muy escaso (todos los enteros de 32 bits y aproximadamente 100 se configuran en un momento dado) e iterar sobre las claves insertadas. Debería tratar con muchas inserciones que golpean las mismas entradas (como, 500k, pero solo 100 diferentes).
Actualmente, estoy usando un std :: set (solo insertar y la interfaz iterativa), que es decente, pero aún no lo suficientemente rápido. std :: unordered_set fue el doble de lento, lo mismo para Google Hash Maps. Me pregunto qué estructura de datos está optimizada para este caso.
Solución
Dependiendo de la distribución de la entrada, es posible que pueda obtener alguna mejora sin cambiar la estructura.
Si tiende a obtener muchas ejecuciones de un solo valor, probablemente pueda acelerar las inserciones manteniendo un registro del último valor insertado, y no se moleste en hacer la inserción si coincide. Cuesta una comparación adicional por entrada, pero guarda una búsqueda para cada elemento en una ejecución más allá del primero. Por lo tanto, podría mejorar las cosas sin importar la estructura de datos que esté utilizando, dependiendo de la frecuencia de las repeticiones y el costo relativo de comparación vs inserción.
Si no obtiene ejecuciones, pero tiende a encontrar que los valores no están distribuidos de manera uniforme, entonces un árbol de despliegue hace que el acceso a los elementos más utilizados sea más barato. Funciona creando un árbol deliberadamente desequilibrado con los elementos frecuentes cerca de la parte superior, como un código Huffman.
Otros consejos
No estoy seguro de entender "muchas inserciones que coinciden con las mismas entradas". ¿Quiere decir que solo hay 100 valores que son miembros, pero 500k operaciones en su mayoría duplicadas que insertan uno de esos 100 valores?
Si es así, entonces supongo que el contenedor más rápido sería generar un hash libre de colisión sobre esos 100 valores, luego mantener una matriz (o vector) de banderas (int o bit, según lo que funcione más rápido) en su arquitectura).
Dejo generar el hash como un ejercicio para el lector, ya que es algo que sé que existe como una técnica, pero nunca lo he investigado. El punto es obtener un hash rápido en un rango lo más pequeño posible, de modo que para cada n, m en sus 100 valores, hash (n)! = Hash (m).
Entonces, la inserción se ve como array [hash (value)] = 1; , la eliminación se ve como array [hash (value)] = 0; (aunque no ' t need that), y para enumerarlo, ejecuta sobre la matriz, y para cada valor establecido en el índice n, inverse_hash (n) está en su colección. Para un rango pequeño, puede mantener fácilmente una tabla de búsqueda para realizar el hash inverso, o en lugar de escanear toda la matriz en busca de banderas establecidas, puede ejecutar más de los 100 valores potencialmente verificados a su vez.
Lo siento si he entendido mal la situación y esto es inútil para usted. Y para ser honesto, no es mucho más rápido que una tabla hash normal, ya que de manera realista para 100 valores puede dimensionar fácilmente la tabla de modo que haya pocas o ninguna colisión, sin usar tanta memoria como para volar sus cachés.
Para un conjunto en uso que se espera que sea así de pequeño, una tabla hash no agrupada podría estar bien. Si puede vivir con una operación de expansión ocasional, hágalo crecer en potencias de 2 si se llena más del 70%. El hash de cuco ha sido discutido en Stackoverflow antes y también podría ser un buen enfoque para un conjunto tan pequeño. Si realmente necesita optimizar la velocidad, puede implementar la función de hash y la búsqueda en ensamblador; en estructuras de datos lineales, esto será muy simple, por lo que el esfuerzo de codificación y mantenimiento para una implementación de ensamblador no debería ser demasiado difícil de mantener.
Es posible que desee considerar implementar un HashTree utilizando una función hash de base 10 en cada nivel en lugar de una función hash binaria. Puede hacerlo sin depósito, en cuyo caso su rendimiento sería determinista (log10) o ajustar el tamaño de su depósito en función de su distribución esperada para que solo tenga un par de claves / depósito.
Una estructura de datos aleatoria podría ser perfecta para su trabajo. Eche un vistazo a la lista de omisión , aunque no conozco ninguna implementación descendente de C ++. . Tenía la intención de enviar uno a Boost, pero nunca pude hacerlo.
Tenga en cuenta que si bien la inserción en una tabla hash es rápida, iterar sobre ella no es particularmente rápida, ya que necesita iterar sobre toda la matriz.
¿Qué operación es lenta para usted? ¿Hace más inserciones o más iteraciones?
¿Cuánta memoria tienes? 32 bits toman `` solo '' 4 GB / 8 bytes, que viene a 512 MB, no mucho para un servidor de gama alta. Eso haría sus inserciones O (1). Pero eso podría hacer que la iteración sea lenta. Aunque omitir todas las palabras con solo ceros optimizaría la mayoría de las iteraciones. Si sus 100 números están en un rango relativamente pequeño, puede optimizar aún más manteniendo el mínimo y el máximo alrededor.
Sé que esto es solo fuerza bruta, pero a veces la fuerza bruta es lo suficientemente buena.
Dado que nadie lo ha mencionado explícitamente, ¿ha pensado en la localidad de la memoria? Una estructura de datos realmente excelente con un algoritmo de inserción que causa un error de página no le servirá de nada. De hecho, una estructura de datos con un inserto que simplemente causa una pérdida de caché probablemente sea realmente mala para el rendimiento.
¿Se ha asegurado de que un conjunto ingenuo de elementos desordenados empaquetados en una matriz fija con un simple intercambio al frente cuando una colisión de inserción es demasiado lenta? Es un experimento simple que podría mostrar que tiene problemas de localidad de memoria en lugar de problemas algorítmicos.
