La caché importa: ¡MUCHO!
Según el análisis big-O, elegiría una lista vinculada sobre una matriz para insertarla en el medio. En la práctica, casi siempre es más rápido usar una matriz y tomar el golpe de copia en lugar de “punteros de persecución” en toda la memoria.
Nuevamente, basado en el análisis big-O, debe preferir el sondeo lineal o cuadrático en una tabla hash de direccionamiento abierto para evitar la agrupación y las búsquedas lineales cuando hay colisiones. En la práctica, el uso del sondeo +1 es más rápido porque el controlador de caché puede detectar cuándo sigue solicitando la siguiente dirección y precarga el caché por usted.
- ¿Es una mala decisión tomar electricidad incluso si puede obtener CS en BITS / IIT?
- ¿Cuáles son algunos virus informáticos?
- En el algoritmo de bosque aleatorio, ¿por qué el árbol seleccionado al azar supera al árbol de decisión de mejor pensamiento?
- ¿Qué hace que ML en Biología Computacional sea especialmente difícil?
- ¿Debo aprender japonés o chino como estudiante de informática?
Tiempo de búsqueda de clave aleatoria por elemento utilizando una matriz asociativa con mil millones de elementos donde tanto la clave como el valor son enteros de 32 bits. En x64 con Linux con Intel C ++ Professional 2017 XE
Mapa de árbol rojo-negro 3 microsegundos
Mapa de hash, direccionamiento cerrado con cubos unordered_hash 300 nanosegundos
Mapa de hash, direccionamiento abierto con sondeo +1 (biblioteca de Moodycamel) 85 nanosegundos
