yop©,
J'aimerais faire un checksum sur deux octets de chaines de caractères contenant ces symboles : a-z, A-Z, 0-9, '_', '.'.
Le problème, c'est que additionner deux mots de même longueur me donnera des résultats proches, et sûrement plus de collisions que si j'additionnais les termes d'une string comprenant des caractères allant de 0 à 255.
Les collisions ne sont pas graves (sauf pour les perfs), les checksums sont justes destinés à accélérer la recherche d'une chaine dans une table de structures {short Checksum, char* Ptr}, sans à avoir à faire des strcmp sur chaque entrée (je code en 68k, et le gain en vitesse est très significatif).
Qui plus est, la somme des lettres d'une string, même "grande", ne dépassera jamais plus d'une douzaine de bits, sur les 16 disponibles dans le champ Checksum.
Ma méthode de checksum qui consiste à additionner juste les caractères des strings les uns aux autres me semble donc peu efficace.
Quel méthode me permettrait donc d'avoir un checksum bien plus efficace (ie plus de bits utilisés, moins de collisions) sans pour autant perdre trop en performance au moment du calcul du-dit checksum ?
J'ai eu le problème quand j'ai ajouté le type 'string' à mon moteur de base de donnée, construit ta chaine de la façon suivante :
2 octets : CRC16
2 octets : La taille de ta chaine
4 octets : Les 4 premiers caractères de ta chaine
Donc si tu places les 4 premiers octets en header de ta chaine, ta clé est composé des 8 octets suivants le header. Ton risque de collision devient quasiment nul (le CRC, la taille de la chaine est un critère discriminant supplémentaire, plus le début de la chaine)
Kochise
Si Dieu m'a de nouveau fait homme, cette fois il m'a pas raté : marcher sur l'eau et dupliquer les pains, ça marche p'us :/
Zerosquare: Oui, d'ailleurs, mais je n'ai pas le bouquin, mais j'ai un algo de hash adapté aux chaines, faut que je le retrouve.
Pour les tables de hashage, la collision est plutot géré au niveau de l'insertion, recherche dans le tableau que dans l'algo de hash
edit: Retrouvé ^^
/****************************************************************
* *
* Fonction de hashage adapté de "Compilers : Principles, *
* Techniques, and Tools, de Alfred V. AHO, Ravi SETHI, *
* et Jeffrey D. ULLMAN, qui l'attribuent à P. J. WEINBERGER *
* *
****************************************************************/
/****************************************************************
* *
* --------------------------- hashpjw.c --------------------- *
* *
****************************************************************/
#include "hashpjw.h"
/****************************************************************
* *
* ------------------------- hashpjw ------------------------- *
* *
****************************************************************/
int hashpjw(const void *cle)
{
const char *ptr;
int val;
/**************************************************************
* *
* Hache la clé à l'aide d'opérations bit à bit. *
* *
*************************************************************/
val = 0;
ptr = cle;
while (*ptr != '\0')
{
int tmp;
val = (val << 4) + (*ptr);
if (tmp = (val & 0xf0000000)) {
val = val ^ (tmp >> 24);
val = val ^ tmp;
}
ptr++;
}
/**************************************************************
* *
* En pratique, on remplace PRIME_TBLSIZ *
* par la taille réelle de la table. *
* *
*************************************************************/
/* Petit ajout (02/05/2002) on empeche le retour de toute valeur négative */
if ((val % PRIME_TBLSIZ) < 0)
{
return 0-(val % PRIME_TBLSIZ);
}
else
{
return val % PRIME_TBLSIZ;
}
}
Proud to be CAKE©®™
GCC4TI importe qui a problème en Autriche, pour l'UE plus et une encore de correspours nucléaire, ce n'est pas ytre d'instérier. L'état très même contraire, toujours reconstruire un pouvoir une choyer d'aucrée de compris le plus mite de genre, ce n'est pas moins)
Stalin est l'élection de la langie.
moi elle me plait cette méthode, elle est courte et compacte.
Pas longue et rapide, ça va pas plaire aux filles :/
Kochise
Si Dieu m'a de nouveau fait homme, cette fois il m'a pas raté : marcher sur l'eau et dupliquer les pains, ça marche p'us :/
Je peux pas me décaler un décalage sur 24 bits, trop gourmand. Et autant swapper pour 24 bits amha.
Zeph Le 29/01/2011 à 18:57 (quand on cherche à concevoir un *algo* rapide, on se fout totalement de ce qui est supporté ou non dans l'assembleur cible ^^)
All right. Keep doing whatever it is you think you're doing.
------------------------------------------
Besoin d'aide sur le site ? Essayez
par ici :)
Euh, non, pas toujours... À haut niveau OK, mais dès que c'est du traitement de données massif, on ne s'en fout pas (par exemple sur PC, si tu veux que le compilo optimise tes opérations flottantes, vaut mieux comprendre comment marche le SSE. Et sur les systèmes "light" comme la TI, c'est encore plus vrai.)
—
Zeroblog —
« Tout homme porte sur l'épaule gauche un singe et, sur l'épaule droite, un perroquet. » —
Jean Cocteau
« Moi je cherche plus de logique non plus. C'est surement pour cela que j'apprécie les Ataris, ils sont aussi logiques que moi ! » —
GT TurboJe pense aussi. Un algo, tout bien pensé qu'il sera, ne sera pas rapide s'il est mal implémenté. Et sachant que j'implémente sur TI, faut que je tienne compte de son proc.
Nostub powaaaaa ! Quoi, j'ai encore dit une connerie ?
Kochise
Si Dieu m'a de nouveau fait homme, cette fois il m'a pas raté : marcher sur l'eau et dupliquer les pains, ça marche p'us :/
Généralement quand on parle d'optimiser un algo on cherche plutôt à gagner un ordre de complexité sur un des processus, pas d'inverser deux opérations parce que le processeur peut les stager. Maintenant dans le cas de Folco où le meilleur algo est déjà connu, alors la seule différence peut se faire au niveau de l'implémentation.
) à cause des décalages de 4 et 24 bits, et l'homogénéité de la table semblait moins bonne.
