es.davy.ai

Preguntas y respuestas de programación confiables

¿Tienes una pregunta?

Si tienes alguna pregunta, puedes hacerla a continuación o ingresar lo que estás buscando.

  • es.davy.ai/
  • Programación /
  • Estructura de tabla de alto rendimiento para tablas muy pequeñas (<10 elementos generalmente) en las cuales, una vez creada la tabla, no cambia.

Estructura de tabla de alto rendimiento para tablas muy pequeñas (<10 elementos generalmente) en las cuales, una vez creada la tabla, no cambia.

22 Jul, 2023 Programación

Estoy buscando una estructura de alto rendimiento en C++ para una tabla. La tabla tendrá void* como claves y uint32 como valores.

La tabla en sí es muy pequeña y no cambiará después de ser creada. La primera idea que se me ocurrió es usar algo como ska::flat_hash_map<void*, int32_t> o std::unordered_map<void*, int32_t>. Sin embargo, eso sería excesivo y no me proporcionaría el rendimiento que quiero (esas tablas son adecuadas para un alto número de elementos).

Por lo tanto, pensé en usar std::vector<std::pair<void*, int32_t>>, ordenándolo al crearlo y haciendo una búsqueda lineal. Las siguientes ideas serán utilizar instrucciones SIMD, pero es posible con la estructura actual.

Otra solución que evaluaré pronto es esta:

struct Group
{
    void* items[5]; // búsqueda utilizando SIMD
    int32_t items[5]; 
}; // cabe en una línea de caché

struct Table
{
     Group* groups;
     size_t capacity;
};

¿Existen mejores opciones? Solo necesito una operación: encontrar valores por clave, no modificarlos, nada más. ¡Gracias!

EDIT: otra cosa que creo que debo mencionar son los patrones de acceso: supongamos que tengo una matriz de esas tablas hash, cada vez buscaré en una al azar dentro de la matriz.

Tags:  , , , ,

Answer

  1. Avatar for davy.ai
    davy.ai

    Basándonos en los requisitos dados, una posible solución puede ser el uso de una tabla de dispersión perfecta. Este tipo de tabla está diseñado para proporcionar tiempos de acceso rápidos para un conjunto fijo de claves sin resolución de colisiones, lo que la hace adecuada para tablas pequeñas y de tamaño fijo. Una tabla de dispersión perfecta utiliza una función hash que genera un índice único para cada clave, y dado que no hay colisiones, no se necesita una sondea o rehash adicional.

    Una implementación de tablas de dispersión perfectas en C++ es la biblioteca Google Sparsehash, que proporciona la clase google::sparse_hash_map. Esta clase está diseñada para ser eficiente en memoria y puede manejar tanto tablas de dispersión densas como dispersas. En particular, ofrece la opción de utilizar google::dense_hash_map, que está optimizado para tablas pequeñas y utiliza menos memoria.

    Para usar google::dense_hash_map para el problema dado, puedes definir lo siguiente:

    #include <sparsehash dense_hash_map="">

using perfect_table = google::dense_hash_map<void*, uint32_t="">;

auto my_table = perfect_table{};

my_table.set_empty_key(nullptr);

// Llena `my_table` con pares clave-valor
...

    El método set_empty_key establece una clave única que no debe aparecer en la tabla, lo que permite que la tabla de dispersión distinga entre cubos vacíos y claves que están ausentes de la tabla. Esta es una optimización importante para tablas de dispersión perfecta, especialmente cuando se utilizan punteros como claves.

    Con esta implementación, puedes buscar fácilmente valores por claves, sin incurrir en la sobrecarga de la resolución de colisiones. Dado que la tabla es pequeña, debería caber en la memoria caché y proporcionar tiempos de acceso rápidos incluso con patrones de acceso aleatorios. Además, la implementación es proporcionada por una biblioteca bien mantenida, lo que garantiza la corrección y el rendimiento.</void*,>

Comments are closed.