c++ - example - ¿La forma más rápida de recuperar 16k pares clave-valor?
hashing c++ code (6)
Std :: pair es mejor que cualquiera de mapa para la velocidad.
pero si yo fuera usted, en primer lugar, utilizar un std :: lista para almacenar los datos, después de que les dieron todo, los muevo en un vector simple, entonces la recuperación va muy rápido si se implementa una simple búsqueda en árbol binario por sí mismo.
OK, esta es mi situación:
- Tengo una función, digamos
U64 calc (U64 x), que toma un parámetro entero de 64 bits, realiza una operación intensiva de CPU y devuelve un valor de 64 bits - Ahora, dado que conozco TODAS las posibles entradas (las
xs) de esa función de antemano (aunque hay 16000), pensé que sería mejor precalcularlas y luego buscarlas a demanda (a partir de una estructura similar a una matriz ) - La situación ideal sería almacenarlos todos en alguna matriz
U64 CALC[]y recuperarlos por índice (laxotra vez) - Y este es el problema: puedo saber cuáles son las posibles entradas para mi función calc, pero definitivamente NO son consecutivas (por ejemplo, no de 1 a 16000, pero los valores pueden ser tan bajos como 0 y tan altos como algunos trillones, siempre dentro de un rango de 64 bits)
P.EJ
X CALC[X]
-----------------------
123123 123123123
12312 12312312
897523 986123
etc.
Y aquí viene mi pregunta:
- ¿Cómo los almacenarías?
- ¿Qué solución preferirías?
- Ahora, dado que estos valores (de
CALC) tendrán que ser accedidos algunos miles o millones de veces, por segundo , ¿cuál sería la mejor solución para el rendimiento?
Nota : No menciono nada que haya pensado o intentado para no convertir las respuestas en un debate de tipo A versus B, y sobre todo no influir en nadie ...
Realizar memonization, o en términos simples, almacenar en caché los valores que ha computada ya y calcular los nuevos. Usted debe hash de la entrada y comprobar la memoria caché para ese resultado. Incluso puede comenzar con un conjunto de valores de caché que usted piensa que la función sería llamará más a menudo para. Además de eso, no creo que necesita para ir a cualquier extremo como la otra respuesta sugiere. Hacer las cosas simples y cuando haya terminado con su aplicación se puede utilizar una herramienta de perfilado para encontrar los cuellos de botella.
EDIT: Algunos código
#include <iostream>
#include <ctime>
using namespace std;
const int MAX_SIZE = 16000;
int preCalcData[MAX_SIZE] = {};
int getPrecalculatedResult(int x){
return preCalcData[x];
}
void setupPreCalcDataCache(){
for(int i = 0; i < MAX_SIZE; ++i){
preCalcData[i] = i*i; //or whatever calculation
}
}
int main(){
setupPreCalcDataCache();
cout << getPrecalculatedResult(0) << endl;
cout << getPrecalculatedResult(15999) << endl;
return 0;
}
Haz una matriz de estructuras de pares val clave.
Ordenar la matriz por clave, poner esto en su programa como matriz estática, sería de 128 kbytes.
Luego, en su programa, una simple búsqueda binaria por clave necesitará, en promedio, solo 14 comparaciones clave para encontrar el valor correcto. Debería ser capaz de alcanzar velocidades de 300 millones de búsquedas por segundo en la PC moderna.
Puede ordenar con qsort y buscar con bsearch, ambas funciones de std lib.
Necesita almacenar 16 mil valores de manera eficiente, preferiblemente en la memoria. Estamos asumiendo que el cálculo de estos valores consume más tiempo que acceder a ellos desde el almacenamiento.
Tiene a su disposición muchas estructuras de datos diferentes para realizar el trabajo, incluidas las bases de datos. Si accede a estos valores en fragmentos consultables, la carga de DB puede muy bien absorberse y propagarse a través de su procesamiento.
Usted mencionó map y hashmap (o hashtable) ya en sus etiquetas de pregunta, pero estas probablemente no sean las mejores respuestas posibles para su problema, aunque podrían hacer un buen trabajo, siempre que la función hash no sea más costosa que el cálculo directo del valor UINT64 objetivo, que tiene que ser su punto de referencia de referencia.
- Árboles de Van Emde Boas
- Muchas variantes de B-Trees (usadas ampliamente en motores de base de datos, sistemas de archivos de alto rendimiento),
- Intentos
Probablemente sean mucho más adecuados. Tener algo de experiencia con él, probablemente iría por un árbol B: admiten la serialización bastante bien. Eso debería permitirle preparar su conjunto de datos por adelantado en un programa diferente. Los árboles VEB tienen un tiempo de acceso muy bueno (O (log log (n)), pero no sé con qué facilidad se pueden serializar.
Más adelante, si necesita aún más rendimiento, también sería interesante conocer los patrones de uso de su "base de datos" para descubrir qué técnicas de almacenamiento en caché podría implementar en la parte superior de la tienda.
No me preocuparía demasiado por el rendimiento. Este ejemplo simple, usa una matriz y búsqueda binaria lower_bound
#include <stdint.h>
#include <algorithm>
#include <cstdlib>
#include <iostream>
#include <memory>
const int N = 16000;
typedef std::pair<uint64_t, uint64_t> CALC;
CALC calc[N];
static inline bool cmp_calcs(const CALC &c1, const CALC &c2)
{
return c1.first < c2.first;
}
int main(int argc, char **argv)
{
std::iostream::sync_with_stdio(false);
for (int i = 0; i < N; ++i)
calc[i] = std::make_pair(i, i);
std::sort(&calc[0], &calc[N], cmp_calcs);
for (long i = 0; i < 10000000; ++i) {
int r = rand() % 16000;
CALC *p = std::lower_bound(&calc[0], &calc[N], std::make_pair(r, 0), cmp_calcs);
if (p->first == r)
std::cout << "found/n";
}
return 0;
}
y compilado con
g++ -O2 example.cpp
lo hace, incluida la configuración, 10.000.000 búsquedas en aproximadamente 2 segundos en mi PC de 5 años.
Usaría algún tipo de función hash que creara un índice para un par u64 donde uno es el valor desde el cual se creó la clave y el otro el valor de reemplazo. Técnicamente, el índice podría tener tres bytes de longitud (suponiendo 16 millones - "16000 mil" - pares) si necesita ahorrar espacio pero yo usaría u32s. Si el valor almacenado no coincide con el valor calculado en (colisión hash), debe ingresar un controlador de desbordamiento.
- Debe determinar un algoritmo hash personalizado para adaptarse a sus datos
- Como conoce el tamaño de los datos, no necesita algoritmos que permitan que crezcan los datos.
- Sería cauteloso de usar algún algoritmo estándar porque rara vez se ajustan a datos específicos
- Desearía utilizar un método C ++ a menos que esté seguro de que el código es WYSIWYG (no genera muchas llamadas invisibles)
- Su índice debe ser un 25% más grande que el número de pares
Analice todas las entradas posibles y determine la desviación mínima, máxima, media y estándar para el número de colisiones y úselas para determinar el nivel de rendimiento aceptable. Luego perfil para lograr el mejor código posible.
El espacio de memoria requerido (usando un índice u32) sale a (4 * 1.25) + 8 + 8 = 21 bytes por par o 336 MeB, no hay problema en una PC típica.
________ EDIT________
Fui desafiado por "RocketRoy" para poner mi dinero donde está mi boca. Aquí va:
El problema tiene que ver con el manejo de colisiones en un índice de hash (tamaño fijo). Para establecer el escenario:
- Tengo una lista de n entradas donde un campo en la entrada contiene el valor v que calcula el hash desde
- Tengo un vector de n * 1.25 (aproximadamente) indeces tal que el número de indeces x es un número primo
- Se calcula un número primo y que es una fracción de x
- El vector se inicializa para decir -1 para denotar desocupado
Bastante estándar, creo que estarás de acuerdo.
Las entradas en la lista se procesan y el valor hash h se calcula y se modula y se utiliza como un índice en el vector y el índice de la entrada se coloca allí.
Eventualmente me encuentro con la situación en la que está ocupada la entrada vectorial apuntada por el índice (no contiene -1) - voilà, una colisión.
¿Entonces qué hago? Mantengo la h original ho, agrego y a hy tomo el módulo x y obtengo un nuevo índice en el vector. Si la entrada está desocupada, la uso; de lo contrario, continúo con agregar y módulo x hasta que llegue a ho. En teoría, esto sucederá porque tanto x como y son números primos. En la práctica, x es mayor que n, por lo que no lo hará.
Entonces, el "re-hash" que afirma RocketRoy es muy costoso no es tal cosa.
La parte difícil de este método, como con todos los métodos de hash, es:
- Determine un valor adecuado para x (se vuelve menos complicado cuanto mayor x finalmente se usa)
- Determine el algoritmo a para h = a (v)% x tal que a el índice de h sea razonablemente uniforme ("aleatoriamente") en el vector de índice con el menor número posible de colisiones
- Determine un valor adecuado para y de manera que las colisiones indexen razonablemente uniformemente ("aleatoriamente") en el vector de índice
________ EDIT________
Lamento haber tardado tanto en producir este código ... otras cosas han tenido mayores prioridades.
De todos modos, aquí está el código que demuestra que el hashing tiene mejores perspectivas para búsquedas rápidas que un árbol binario. Se ejecuta a través de un conjunto de algoritmos y tamaños de índice hash para ayudar a encontrar el combo más adecuado para los datos específicos. Para cada algoritmo, el código imprimirá el primer tamaño de índice de modo que ninguna búsqueda tarde más de catorce búsquedas (el peor caso para la búsqueda binaria) y una búsqueda promedio requiera menos de 1.5 búsquedas.
Tengo una afición por los números primos en este tipo de aplicaciones, en caso de que no lo hayas notado.
Hay muchas formas de crear un algoritmo hash con su manejo obligatorio de desbordamiento. Opté por la simplicidad, suponiendo que se traduzca en velocidad ... y lo hace. En mi computadora portátil con un i5 M 480 a 2.67 GHz, una búsqueda promedio requiere entre 55 y 60 ciclos de reloj (aproximadamente 45 millones de búsquedas por segundo). Implementé una operación de obtención especial con un número constante de indeces y un valor de réplica de ídem y el recuento de ciclos se redujo a 40 (65 millones de búsquedas por segundo). Si observa la línea que llama a getOpSpec, el índice i se xor''ed con 0x444 para ejercitar los cachés y así obtener más resultados de tipo "mundo real".
Debo señalar nuevamente que el programa sugiere combinaciones adecuadas para los datos específicos . Otros datos pueden requerir un combo diferente.
El código fuente contiene tanto el código para generar los 16000 pares largos largos sin firmar como para probar diferentes constantes (tamaños de índice y valores de repetición):
#include <windows.h>
#define i8 signed char
#define i16 short
#define i32 long
#define i64 long long
#define id i64
#define u8 char
#define u16 unsigned short
#define u32 unsigned long
#define u64 unsigned long long
#define ud u64
#include <string.h>
#include <stdio.h>
u64 prime_find_next (const u64 value);
u64 prime_find_previous (const u64 value);
static inline volatile unsigned long long rdtsc_to_rax (void)
{
unsigned long long lower,upper;
asm volatile( "rdtsc/n"
: "=a"(lower), "=d"(upper));
return lower|(upper<<32);
}
static u16 index[65536];
static u64 nindeces,rehshFactor;
static struct PAIRS {u64 oval,rval;} pairs[16000] = {
#include "pairs.h"
};
struct HASH_STATS
{
u64 ninvocs,nrhshs,nworst;
} getOpStats,putOpStats;
i8 putOp (u16 index[], const struct PAIRS data[], const u64 oval, const u64 ci)
{
u64 nworst=1,ho,h,i;
i8 success=1;
++putOpStats.ninvocs;
ho=oval%nindeces;
h=ho;
do
{
i=index[h];
if (i==0xffff) /* unused position */
{
index[h]=(u16)ci;
goto added;
}
if (oval==data[i].oval) goto duplicate;
++putOpStats.nrhshs;
++nworst;
h+=rehshFactor;
if (h>=nindeces) h-=nindeces;
} while (h!=ho);
exhausted: /* should not happen */
duplicate:
success=0;
added:
if (nworst>putOpStats.nworst) putOpStats.nworst=nworst;
return success;
}
i8 getOp (u16 index[], const struct PAIRS data[], const u64 oval, u64 *rval)
{
u64 ho,h,i;
i8 success=1;
ho=oval%nindeces;
h=ho;
do
{
i=index[h];
if (i==0xffffu) goto not_found; /* unused position */
if (oval==data[i].oval)
{
*rval=data[i].rval; /* fetch the replacement value */
goto found;
}
h+=rehshFactor;
if (h>=nindeces) h-=nindeces;
} while (h!=ho);
exhausted:
not_found: /* should not happen */
success=0;
found:
return success;
}
volatile i8 stop = 0;
int main (int argc, char *argv[])
{
u64 i,rval,mulup,divdown,start;
double ave;
SetThreadAffinityMask (GetCurrentThread(), 0x00000004ull);
divdown=5; //5
while (divdown<=100)
{
mulup=3; // 3
while (mulup<divdown)
{
nindeces=16000;
while (nindeces<65500)
{
nindeces= prime_find_next (nindeces);
rehshFactor=nindeces*mulup/divdown;
rehshFactor=prime_find_previous (rehshFactor);
memset (index, 0xff, sizeof(index));
memset (&putOpStats, 0, sizeof(struct HASH_STATS));
i=0;
while (i<16000)
{
if (!putOp (index, pairs, pairs[i].oval, (u16) i)) stop=1;
++i;
}
ave=(double)(putOpStats.ninvocs+putOpStats.nrhshs)/(double)putOpStats.ninvocs;
if (ave<1.5 && putOpStats.nworst<15)
{
start=rdtsc_to_rax ();
i=0;
while (i<16000)
{
if (!getOp (index, pairs, pairs[i^0x0444]. oval, &rval)) stop=1;
++i;
}
start=rdtsc_to_rax ()-start+8000; /* 8000 is half of 16000 (pairs), for rounding */
printf ("%u;%u;%u;%u;%1.3f;%u;%u/n", (u32)mulup, (u32)divdown, (u32)nindeces, (u32)rehshFactor, ave, (u32) putOpStats.nworst, (u32) (start/16000ull));
goto found;
}
nindeces+=2;
}
printf ("%u;%u/n", (u32)mulup, (u32)divdown);
found:
mulup=prime_find_next (mulup);
}
divdown=prime_find_next (divdown);
}
SetThreadAffinityMask (GetCurrentThread(), 0x0000000fu);
return 0;
}
No fue posible incluir el archivo de pares generado (una respuesta aparentemente está limitada a 30000 caracteres). Pero envíe un mensaje a mi bandeja de entrada y lo enviaré por correo.
Y estos son los resultados:
3;5;35569;21323;1.390;14;73
3;7;33577;14389;1.435;14;60
5;7;32069;22901;1.474;14;61
3;11;35107;9551;1.412;14;59
5;11;33967;15427;1.446;14;61
7;11;34583;22003;1.422;14;59
3;13;34253;7901;1.439;14;61
5;13;34039;13063;1.443;14;60
7;13;32801;17659;1.456;14;60
11;13;33791;28591;1.436;14;59
3;17;34337;6053;1.413;14;59
5;17;32341;9511;1.470;14;61
7;17;32507;13381;1.474;14;62
11;17;33301;21529;1.454;14;60
13;17;34981;26737;1.403;13;59
3;19;33791;5333;1.437;14;60
5;19;35149;9241;1.403;14;59
7;19;33377;12289;1.439;14;97
11;19;34337;19867;1.417;14;59
13;19;34403;23537;1.430;14;61
17;19;33923;30347;1.467;14;61
3;23;33857;4409;1.425;14;60
5;23;34729;7547;1.429;14;60
7;23;32801;9973;1.456;14;61
11;23;33911;16127;1.445;14;60
13;23;33637;19009;1.435;13;60
17;23;34439;25453;1.426;13;60
19;23;33329;27529;1.468;14;62
3;29;32939;3391;1.474;14;62
5;29;34543;5953;1.437;13;60
7;29;34259;8263;1.414;13;59
11;29;34367;13033;1.409;14;60
13;29;33049;14813;1.444;14;60
17;29;34511;20219;1.422;14;60
19;29;33893;22193;1.445;13;61
23;29;34693;27509;1.412;13;92
3;31;34019;3271;1.441;14;60
5;31;33923;5449;1.460;14;61
7;31;33049;7459;1.442;14;60
11;31;35897;12721;1.389;14;59
13;31;35393;14831;1.397;14;59
17;31;33773;18517;1.425;14;60
19;31;33997;20809;1.442;14;60
23;31;34841;25847;1.417;14;59
29;31;33857;31667;1.426;14;60
3;37;32569;2633;1.476;14;61
5;37;34729;4691;1.419;14;59
7;37;34141;6451;1.439;14;60
11;37;34549;10267;1.410;13;60
13;37;35117;12329;1.423;14;60
17;37;34631;15907;1.429;14;63
19;37;34253;17581;1.435;14;60
23;37;32909;20443;1.453;14;61
29;37;33403;26177;1.445;14;60
31;37;34361;28771;1.413;14;59
3;41;34297;2503;1.424;14;60
5;41;33587;4093;1.430;14;60
7;41;34583;5903;1.404;13;59
11;41;32687;8761;1.440;14;60
13;41;34457;10909;1.439;14;60
17;41;34337;14221;1.425;14;59
19;41;32843;15217;1.476;14;62
23;41;35339;19819;1.423;14;59
29;41;34273;24239;1.436;14;60
31;41;34703;26237;1.414;14;60
37;41;33343;30089;1.456;14;61
3;43;34807;2423;1.417;14;59
5;43;35527;4129;1.413;14;60
7;43;33287;5417;1.467;14;61
11;43;33863;8647;1.436;14;60
13;43;34499;10427;1.418;14;78
17;43;34549;13649;1.431;14;60
19;43;33749;14897;1.429;13;60
23;43;34361;18371;1.409;14;59
29;43;33149;22349;1.452;14;61
31;43;34457;24821;1.428;14;60
37;43;32377;27851;1.482;14;81
41;43;33623;32057;1.424;13;59
3;47;33757;2153;1.459;14;61
5;47;33353;3547;1.445;14;61
7;47;34687;5153;1.414;13;59
11;47;34519;8069;1.417;14;60
13;47;34549;9551;1.412;13;59
17;47;33613;12149;1.461;14;61
19;47;33863;13687;1.443;14;60
23;47;35393;17317;1.402;14;59
29;47;34747;21433;1.432;13;60
31;47;34871;22993;1.409;14;59
37;47;34729;27337;1.425;14;59
41;47;33773;29453;1.438;14;60
43;47;31253;28591;1.487;14;62
3;53;33623;1901;1.430;14;59
5;53;34469;3229;1.430;13;60
7;53;34883;4603;1.408;14;59
11;53;34511;7159;1.412;13;59
13;53;32587;7963;1.453;14;60
17;53;34297;10993;1.432;13;80
19;53;33599;12043;1.443;14;64
23;53;34337;14897;1.415;14;59
29;53;34877;19081;1.424;14;61
31;53;34913;20411;1.406;13;59
37;53;34429;24029;1.417;13;60
41;53;34499;26683;1.418;14;59
43;53;32261;26171;1.488;14;62
47;53;34253;30367;1.437;14;79
3;59;33503;1699;1.432;14;61
5;59;34781;2939;1.424;14;60
7;59;35531;4211;1.403;14;59
11;59;34487;6427;1.420;14;59
13;59;33563;7393;1.453;14;61
17;59;34019;9791;1.440;14;60
19;59;33967;10937;1.447;14;60
23;59;33637;13109;1.438;14;60
29;59;34487;16943;1.424;14;59
31;59;32687;17167;1.480;14;61
37;59;35353;22159;1.404;14;59
41;59;34499;23971;1.431;14;60
43;59;34039;24799;1.445;14;60
47;59;32027;25471;1.499;14;62
53;59;34019;30557;1.449;14;61
3;61;35059;1723;1.418;14;60
5;61;34351;2803;1.416;13;60
7;61;35099;4021;1.412;14;59
11;61;34019;6133;1.442;14;60
13;61;35023;7459;1.406;14;88
17;61;35201;9803;1.414;14;61
19;61;34679;10799;1.425;14;101
23;61;34039;12829;1.441;13;60
29;61;33871;16097;1.446;14;60
31;61;34147;17351;1.427;14;61
37;61;34583;20963;1.412;14;59
41;61;32999;22171;1.452;14;62
43;61;33857;23857;1.431;14;98
47;61;34897;26881;1.431;14;60
53;61;33647;29231;1.434;14;60
59;61;32999;31907;1.454;14;60
3;67;32999;1471;1.455;14;61
5;67;35171;2621;1.403;14;59
7;67;33851;3533;1.463;14;61
11;67;34607;5669;1.437;14;60
13;67;35081;6803;1.416;14;61
17;67;33941;8609;1.417;14;60
19;67;34673;9829;1.427;14;60
23;67;35099;12043;1.415;14;60
29;67;33679;14563;1.452;14;61
31;67;34283;15859;1.437;14;60
37;67;32917;18169;1.460;13;61
41;67;33461;20443;1.441;14;61
43;67;34313;22013;1.426;14;60
47;67;33347;23371;1.452;14;61
53;67;33773;26713;1.434;14;60
59;67;35911;31607;1.395;14;58
61;67;34157;31091;1.431;14;63
3;71;34483;1453;1.423;14;59
5;71;34537;2423;1.428;14;59
7;71;33637;3313;1.428;13;60
11;71;32507;5023;1.465;14;79
13;71;35753;6529;1.403;14;59
17;71;33347;7963;1.444;14;61
19;71;35141;9397;1.410;14;59
23;71;32621;10559;1.475;14;61
29;71;33637;13729;1.429;14;60
31;71;33599;14657;1.443;14;60
37;71;34361;17903;1.396;14;59
41;71;33757;19489;1.435;14;61
43;71;34583;20939;1.413;14;59
47;71;34589;22877;1.441;14;60
53;71;35353;26387;1.418;14;59
59;71;35323;29347;1.406;14;59
61;71;35597;30577;1.401;14;59
67;71;34537;32587;1.425;14;59
3;73;34613;1409;1.418;14;59
5;73;32969;2251;1.453;14;62
7;73;33049;3167;1.448;14;61
11;73;33863;5101;1.435;14;60
13;73;34439;6131;1.456;14;60
17;73;33629;7829;1.455;14;61
19;73;34739;9029;1.421;14;60
23;73;33071;10399;1.469;14;61
29;73;33359;13249;1.460;14;61
31;73;33767;14327;1.422;14;59
37;73;32939;16693;1.490;14;62
41;73;33739;18947;1.438;14;60
43;73;33937;19979;1.432;14;61
47;73;33767;21739;1.422;14;59
53;73;33359;24203;1.435;14;60
59;73;34361;27767;1.401;13;59
61;73;33827;28229;1.443;14;60
67;73;34421;31583;1.423;14;71
71;73;33053;32143;1.447;14;60
3;79;35027;1327;1.410;14;60
5;79;34283;2161;1.432;14;60
7;79;34439;3049;1.432;14;60
11;79;34679;4817;1.416;14;59
13;79;34667;5701;1.405;14;59
17;79;33637;7237;1.428;14;60
19;79;34469;8287;1.417;14;60
23;79;34439;10009;1.433;14;60
29;79;33427;12269;1.448;13;61
31;79;33893;13297;1.445;14;61
37;79;33863;15823;1.439;14;60
41;79;32983;17107;1.450;14;60
43;79;34613;18803;1.431;14;60
47;79;33457;19891;1.457;14;61
53;79;33961;22777;1.435;14;61
59;79;32983;24631;1.465;14;60
61;79;34337;26501;1.428;14;60
67;79;33547;28447;1.458;14;61
71;79;32653;29339;1.473;14;61
73;79;34679;32029;1.429;14;64
3;83;35407;1277;1.405;14;59
5;83;32797;1973;1.451;14;60
7;83;33049;2777;1.443;14;61
11;83;33889;4483;1.431;14;60
13;83;35159;5503;1.409;14;59
17;83;34949;7151;1.412;14;59
19;83;32957;7541;1.467;14;61
23;83;32569;9013;1.470;14;61
29;83;33287;11621;1.474;14;61
31;83;33911;12659;1.448;13;60
37;83;33487;14923;1.456;14;62
41;83;33587;16573;1.438;13;60
43;83;34019;17623;1.435;14;60
47;83;31769;17987;1.483;14;62
53;83;33049;21101;1.451;14;61
59;83;32369;23003;1.465;14;61
61;83;32653;23993;1.469;14;61
67;83;33599;27109;1.437;14;61
71;83;33713;28837;1.452;14;61
73;83;33703;29641;1.454;14;61
79;83;34583;32911;1.417;14;59
3;89;34147;1129;1.415;13;60
5;89;32797;1831;1.461;14;61
7;89;33679;2647;1.443;14;73
11;89;34543;4261;1.427;13;60
13;89;34603;5051;1.419;14;60
17;89;34061;6491;1.444;14;60
19;89;34457;7351;1.422;14;79
23;89;33529;8663;1.450;14;61
29;89;34283;11161;1.431;14;60
31;89;35027;12197;1.411;13;59
37;89;34259;14221;1.403;14;59
41;89;33997;15649;1.434;14;60
43;89;33911;16127;1.445;14;60
47;89;34949;18451;1.419;14;59
53;89;34367;20443;1.434;14;60
59;89;33791;22397;1.430;14;59
61;89;34961;23957;1.404;14;59
67;89;33863;25471;1.433;13;60
71;89;35149;28031;1.414;14;79
73;89;33113;27143;1.447;14;60
79;89;32909;29209;1.458;14;61
83;89;33617;31337;1.400;14;59
3;97;34211;1051;1.448;14;60
5;97;34807;1789;1.430;14;60
7;97;33547;2417;1.446;14;60
11;97;35171;3967;1.407;14;89
13;97;32479;4349;1.474;14;61
17;97;34319;6011;1.444;14;60
19;97;32381;6337;1.491;14;64
23;97;33617;7963;1.421;14;59
29;97;33767;10093;1.423;14;59
31;97;33641;10739;1.447;14;60
37;97;34589;13187;1.425;13;60
41;97;34171;14437;1.451;14;60
43;97;31973;14159;1.484;14;62
47;97;33911;16127;1.445;14;61
53;97;34031;18593;1.448;14;80
59;97;32579;19813;1.457;14;61
61;97;34421;21617;1.417;13;60
67;97;33739;23297;1.448;14;60
71;97;33739;24691;1.435;14;60
73;97;33863;25471;1.433;13;60
79;97;34381;27997;1.419;14;59
83;97;33967;29063;1.446;14;60
89;97;33521;30727;1.441;14;60
Las columnas 1 y 2 se usan para calcular una relación aproximada entre el valor de repetición y el tamaño del índice. Las dos siguientes son la primera combinación de tamaño de índice / factor de repetición que promedia menos de 1,5 búsquedas para una búsqueda con el peor de los casos de 14 búsquedas. Luego el promedio y el peor caso. Finalmente, la última columna es el número promedio de ciclos de reloj por búsqueda. No tiene en cuenta el tiempo requerido para leer el registro de marca de tiempo.
El espacio de memoria real para las mejores constantes (# de indeces = 31253 y factor de repetición = 28591) sale a más de lo que inicialmente indiqué (16000 * 2 * 8 + 1,25 * 16000 * 2 => 296000 bytes). El tamaño real es 16000 * 2 * 8 + 31253 * 2 => 318506.
La combinación más rápida es una proporción aproximada de 11/31 con un tamaño de índice de 35897 y un valor de réplica de 12721. Esto promediará 1.389 (1 hash inicial + 0.389 repeticiones) con un máximo de 14 (1 + 13).
________ EDIT________
Eliminé el "goto found"; en main () para mostrar todas las combinaciones y muestra que es posible un rendimiento mucho mejor, por supuesto a expensas de un tamaño de índice mayor. Por ejemplo, la combinación 57667 y 33797 produce un promedio de 1.192 y una repetición máxima de 6. La combinación 44543 y 23399 produce un promedio de 1.249 y 10 reinicios máximos (ahorra (57667-44543) * 2 = 26468 bytes de tabla de índice en comparación con 57667/33797).
Las funciones especializadas con tamaño de índice de hash codificado y factor de repetición se ejecutarán en un 60-70% del tiempo en comparación con las variables. Esto probablemente se deba al compilador (gcc de 64 bits) que sustituye el módulo por multiplicaciones y no tiene que recuperar los valores de las ubicaciones de la memoria, ya que se codificarán como valores inmediatos.
________ EDIT________
Sobre el tema de los cachés veo dos problemas.
El primero es la caché de datos que no creo que sea posible porque la búsqueda será solo un pequeño paso en un proceso más grande y se corre el riesgo de que las líneas de caché de los datos de la tabla comiencen a invalidarse a un grado menor o (probablemente) mayor - si no del todo, por otros accesos de datos en otros pasos del proceso más grande. Cuantos más códigos se ejecuten y más datos se accedan en el proceso como un todo, menos probable será que los datos de búsqueda pertinentes permanezcan en las memorias caché (esto puede o no ser pertinente para la situación del OP). Para encontrar una entrada usando (my) hash, encontrará dos fallos de caché (uno para cargar la parte correcta del índice y el otro para cargar el área que contiene la entrada misma) para cada comparación que deba realizarse. Encontrar una entrada en el primer intento le habrá costado dos errores, el segundo intento cuatro, etc. En mi ejemplo, el costo promedio por ciclo de 60 relojes implica que la tabla probablemente residía completamente en la memoria caché L2 y que L1 no tenía que ir allí la mayoría de los casos. Mi CPU x86-64 tiene L1-3, la RAM espera estados de aproximadamente 4, 10, 40 y 100, lo que para mí muestra que la RAM se mantuvo completamente fuera y L3 en su mayoría.
El segundo es la caché de código que tendrá un impacto más significativo si es pequeño, ajustado, alineado y con pocas transferencias de control (saltos y llamadas). Mi rutina hash probablemente reside completamente en el caché del código L1. Para casos más normales, cuanto menor sea el número de líneas de caché de código, más rápido será.