Recherches sur un ensemble connu de clés entières

Gperf sous-performe systématiquement un tableau Judy dans mon environnement, et je me demande s’il existe une autre bibliothèque de hachage parfaite spécialement conçue pour les clés de nombre entier. Je connais l’ensemble des clés à l’avance et j’aimerais en tirer parti pour améliorer les performances et la taille.

Il y a environ 1 000 clés et les extractions ne sont pas dans un ordre séquentiel. Les paires de clés sont des entiers. Les clés sont en 32 bits et les valeurs extraites en 8 bits. La taille est le facteur le plus important.

S’il existe un moyen de modifier Gperf pour les clés entières, ou simplement une autre approche en général, je suis tout ouïe aussi. 🙂

(Sidenote: … En tapant cette question, je me suis rendu compte qu’une recherche binary prenait probablement le gâteau et j’ai tout simplement réfléchi au problème. J’aimerais quand même avoir vos idées pour apprendre, bien que!)

Edit: Les clés ne sont pas dissortingbuées uniformément. La plupart sont regroupés de manière aléatoire dans toute la plage possible.

Edit 2: Les recherches binarys dans le pire des cas étaient trop lentes à mon goût, alors j’ai fini par jouer avec les touches jusqu’à trouver 8 bits à utiliser pour créer 256 compartiments bien dissortingbués. J’ai tenu le min & max de chaque compartiment (24 bits pour chaque entrée de compartiment) et créé un grand tableau struct pour les paires de clés. Sur-pair / plus rapide et plus petit que tout ce que j’ai testé pour mon cas particulier, je suppose que je vais y aller pour le moment. 🙂

Gardez vos clés sortingées et utilisez un arbre M pour récupérer les clés.

Un arbre multiple a une entrée M par noeud, au lieu de 2 pour les fichiers binarys. Cela aidera énormément pour la performance. Utilisez une taille de ligne de cache comme base de la taille de votre nœud, soit 64 octets. Vous pouvez stocker 16 valeurs 32 bits dans cette taille.

Puisque vous avez 1000 valeurs, 3 niveaux suffiront pour récupérer la bonne clé (par opposition à 10 niveaux pour un arbre binary).

Une autre idée serait de hacher vos clés dans une petite table de hachage, telle qu’une table 12 bits (4K entrées), et de résoudre les collisions potentielles avec une simple chaîne. Vous obtiendrez très probablement la plupart de vos clés en une seule recherche.

Avez-vous essayé les tableaux de judy ? Peut-être exactement ce dont vous avez besoin.

/* ** Proof of concept for constructing a {fixed-size,lookup-only} hashtable ** needing only (2*N* sizeof(int)) additional storage for storing N num=value pairs. ** The key is supposed to be an int, ** the 'value' is a char. ** Note: some people would like to include  and replace all the ints by {uint32_t,uint16_t,uint8_t}. ** ** (c)opyright Wildplasser, 2011-11-12 ** href = http://stackoverflow.com/questions/8059591/lookups-on-known-set-of-integer-keys */ #include  #include  #include  #include  struct tinyhash { unsigned key; unsigned short link; unsigned char value; unsigned is_linked :1; }; #define LINK_DEAD ((unsigned short)-1) /* A hashtable with N slots for N ensortinges (100% full) */ #define THE_SIZE 1000 struct tinyhash table[THE_SIZE] ; void tiny_fill(void); void tiny_init(void); int tiny_find(unsigned key); void tiny_print(void); void tiny_count(void); static int tiny_cmp( const void *l, const void *r); static unsigned short * tiny_hnd(unsigned key); static unsigned tiny_hash(unsigned key); int main (void) { assert(sizeof table == 2 * THE_SIZE * sizeof(int)); fprintf (stderr, "Size=%u\n", (unsigned int) sizeof table); tiny_fill(); tiny_init(); tiny_print(); tiny_count(); return 0; } /* Perform a table lookup. ** Return the "value" that belongs to "key".. ** If not found -1 is returned. */ int tiny_find(unsigned key) { unsigned short *ptr; ptr = tiny_hnd(key); return *ptr==LINK_DEAD ? -1 : table[*ptr].value ; } /* Find the place where key is located, or ** (if not found) where it should be appendend. ** The returned value is a pointer to the parent's .link field. */ static unsigned short * tiny_hnd(unsigned key) { unsigned hash; unsigned short slot, *ptr; hash = tiny_hash(key); slot = hash % THE_SIZE; for (ptr = &table[slot].link; *ptr != LINK_DEAD; ptr = &table[*ptr].link ) { if ( !table[*ptr].is_linked ) break; if ( table[*ptr].key == key) break; } return ptr; } /* For testing: fill hashtable with garbage */ void tiny_fill(void) { unsigned idx; for (idx=0; idx < THE_SIZE; idx++ ) { table[idx].key = rand() + 543 * rand(); table[idx].value = rand() ; table[idx].link = LINK_DEAD; table[idx].is_linked = 0; } } /* Build hashtable, that is: ** shuffle the entries and build linked list. */ void tiny_init(void) { unsigned idx; /* Phase 0: set all to unused. ** The link field is temporaly abused to store the intended ** slotnumber. */ for (idx=0; idx < THE_SIZE; idx++ ) { table[idx].link = tiny_hash(table[idx].key) % THE_SIZE; table[idx].is_linked = 0; } /* Phase 0a: sort on (intended) slotnumber. */ qsort (table, THE_SIZE, sizeof table[0] , tiny_cmp); /* Phase 1: put enties at their intended slotnumber ** but only if the entry that lives there does not belong there ** (is uninitialized). */ for (idx=0; idx < THE_SIZE; idx++) { unsigned slot; /* [idx] has allready been placed */ if (table[idx].is_linked) continue; slot = table[idx].link; /* [idx] belongs here. freeze it */ if (slot==idx) { table[idx].link = LINK_DEAD; table[idx].is_linked = 1; } /* try to swap [idx] with the item at its intended slot */ else { struct tinyhash tmp; /* item[slot] belongs there: keep off */ if (table[slot].is_linked) continue; tmp = table[idx]; table[idx] = table[slot]; table[slot] = tmp; table[slot].is_linked = 1; table[slot].link = LINK_DEAD; /* Don't bump idx: [idx] and [slot] have been swapped, ** we need to inspect the new item[idx] at the next cycle. */ idx--; /* idx will be re-incremented in the loop; */ } } /* Phase 2: link any remaining unplaced item to its ** parent in the LL-chain. */ for (idx=0; idx < THE_SIZE; idx++ ) { unsigned short *parent; if (table[idx].is_linked) continue; parent = tiny_hnd(table[idx].key); if (*parent != LINK_DEAD) continue; /* duplicate */ *parent = idx; table[idx].is_linked = 1; table[idx].link = LINK_DEAD; } } /* Compare function for qsort() */ static int tiny_cmp( const void *vl, const void *vr) { struct tinyhash *l = (struct tinyhash *)vl; struct tinyhash *r = (struct tinyhash *)vr; #if 0 unsigned slot_l, slot_r; slot_l = tiny_hash(l->key) %THE_SIZE; slot_r = tiny_hash(r->key) %THE_SIZE; if (slot_l < slot_r ) return -3; if (slot_l > slot_r ) return 3; #else if (l->link < r->link ) return -3; if (l->link > r->link ) return 3; #endif if (l->key < r->key) return -2; if (l->key > r->key) return 2; if (l < r) return -1; if (l > r) return 1; return 0; } /* Stupid hashfunction, to be replaced with something usefull.. ** (works good for random ints) Use at your own risk. */ static unsigned tiny_hash(unsigned key) { return key * 98765; } void tiny_print(void) { unsigned idx; for (idx=0; idx < THE_SIZE; idx++ ) { unsigned slot; int dir; slot = tiny_hash(table[idx].key) % THE_SIZE; dir = (slot==idx) ? '=' : (slot>idx) ? '<': '>'; fprintf(stderr, "[%4x] %c %4x: %4x %c %10u->%3u\n" , idx, dir, 0xffff & slot , 0xffff & table[idx].link , table[idx].is_linked ? '*' : '.' , table[idx].key,table[idx].value ); } } /* For testing: print the hashchains, construct a histogram of chainlengths, ** and calculate the "total cost of resortingeval". */ void tiny_count(void) { unsigned idx, cnt, len, tothops, slot; unsigned histogram[THE_SIZE]; memset(histogram, 0, sizeof histogram); cnt=tothops=0; for (slot =0; slot < THE_SIZE; slot++ ) { idx = tiny_hash(table[slot].key) % THE_SIZE; if (slot!=idx) continue; /* this is not the start of a chain */ for (len=0 ; idx != LINK_DEAD; idx = table[idx].link) { if (!table[idx].is_linked) continue; if (len==0) fprintf(stderr, "[%u]:", slot); fprintf(stderr, " %u", table[idx].key); len++; } fprintf(stderr, "(=%u)\n", len); cnt += len; histogram[len] += 1; tothops += (((len+1) *len)/2); } fprintf(stderr, "Histogram of chainlengths:\n"); for (len=0; len < THE_SIZE; len++) { if (!histogram[len]) continue; fprintf(stderr, "[%u]: %u\n", len, histogram[len]); } fprintf(stderr, "tothops=%u/%u (%f hops per node)\n" , tothops, cnt, (double)tothops/cnt); } 

Le résultat: (enfin: une partie)

 .... [978]: 1794172570(=1) [980]: 642121828(=1) [983]: 2674104091(=1) [985]: 547527125(=1) [986]: 2383911594(=1) [988]: 4254837348(=1) [989]: 1860851825 1990214465 1766290905(=3) [990]: 3793608270 469685686(=2) [992]: 1189958296 872917240(=2) [994]: 1999781290 1501026482(=2) [995]: 520334159 211600319(=2) [997]: 177583921(=1) [998]: 1173163646 1013572158(=2) [999]: 1705614211 3460318251(=2) Histogram of chainlengths: [1]: 369 [2]: 190 [3]: 57 [4]: 15 [5]: 4 tothops=1491/1000 (1.491000 hops per node) 

Remarque: en raison du sorting effectué lors de l'initialisation de la table de hachage, les entrées sont très proches de l'endroit où elles sont attendues. Cela augmente la localité de référence.