Discussion :

[guillaume07]

Bonjour,

j'utilise unordered map fournit dans le TR1 avec visual 2008

Mes clefs sont de type std::string et mes données stockées sont des structure contenant des std::string, des std::vector un int et un QTime

Puis-je utiliser la hash et fonction equal fournit par défaut ?

J'ai déjà fait ainsi, mais au final , ça s'avère plus lent qu'avec une std::map classique..

LA fonction find doit être en théorie plus rapide avec la hash map , vrai ou faux ?

une idée du problème ?
Merci !

[Lavock]

La complexité d'une table de hachage est inférieur à celle d'une map. Toutefois, dans le cas des string par exemple, la fonction de hachage est assez lourde.

En coséquence, pour n données, tu aura par exemple :

• 10 + log (5n) opération pour une map
• 200 Pour une table de hachage.

Donc il va falloir que tu es une grande table pour compensez le coefficient constant.

[camboui]

Il me semble qu'il existe des fonctions hash pour string plus efficaces que d'autres.
Cherche après djb2 par exemple.

EDIT: la fonction ci-dessous de Guillaume est justement djb2.

[guillaume07]

j'utilise celle ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
struct Hash : std::unary_function<std::string, std::size_t>
{ 
    std::size_t operator()(const std::string & s) const
    {
        int nb = s.length();
        unsigned char *str = new unsigned char [ s.length()+1 ];
        std::stringstream ss;
        ss >> *str;
        str[s.length()]='\0';
 
        std::size_t hash = 5381;
        while(*str!='\0') 
        {
                int c = *str;
                    /* hash = hash*33 + c */
                    hash = ((hash << 5) + hash) + c;
                    str++;
        }
        return hash;
    }
};

[JolyLoic]

Une hash map n'est déjà généralement plus rapide que pour de grandes quantités de données.

Ensuite, elle n'est plus rapide que si la fonction de hash est bonne. Il n'est pas possible de concevoir une fonction bonne pour toutes les chaînes, si tes chaînes ont une forme spécifique, une fonction de hash spécifique est peut-être souhaitable. Il serait intéressant de connaitre le nombre de collisions que tu as dans ta structure.

[guillaume07]

La complexité d'une table de hachage est inférieur à celle d'une map. Toutefois, dans le cas des string par exemple, la fonction de hachage est assez lourde.

En coséquence, pour n données, tu aura par exemple :

• 10 + log (5n) opération pour une map
• 200 Pour une table de hachage.

Donc il va falloir que tu es une grande table pour compensez le coefficient constant.

à partir du moment où 10 + log (5n) > 200 Hash map est plus performante donc?
c'est bien log et pas ln ?

log(5*100000) par exemple me donne un petit chiffre

[camboui]

J'ai le souvenir d'avoir lu quelque part que les URL étaient un type de string souvent difficile à hasher car elles sont souvent longues avec peu de caractères changeant d'une page à l'autre pour un même site.
Il me semble qu'il y a une fonction pour ce cas de figure mais je ne la retrouve pas.

[guillaume07]

Une hash map n'est déjà généralement plus rapide que pour de grandes quantités de données.

Ensuite, elle n'est plus rapide que si la fonction de hash est bonne. Il n'est pas possible de concevoir une fonction bonne pour toutes les chaînes, si tes chaînes ont une forme spécifique, une fonction de hash spécifique est peut-être souhaitable. Il serait intéressant de connaitre le nombre de collisions que tu as dans ta structure.

toutes mes chaines ont cette allure : "B0221800N05CF1C"
Pour les collisions, je n'ai pas le chiffre

[Lavock]

à partir du moment où 10 + log (5n) > 200 Hash map est plus performante donc?

Oui, mais

c'est bien log et pas ln ?

log(5*100000) par exemple me donne un petit chiffre

C'était qu'un exemple. Ne prend pas ces chiffres comme modèle.

[hs] Log ou ln, c'est pareil. Je sais pas pourquoi les calculatrices semble avoir adopté une norme pour log = log base 10 et ln = log base e >< !
Quoi qu'il en soit, selon tes notations, log = ln / ln 10.

[camboui]

j'utilise celle ci :

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
 
struct Hash : std::unary_function<std::string, std::size_t>
{ 
    std::size_t operator()(const std::string & s) const
    {
        int nb = s.length();
        unsigned char *str = new unsigned char [ s.length()+1 ];
        std::stringstream ss;
        ss >> *str;
        str[s.length()]='\0';
 
        std::size_t hash = 5381;
        while(*str!='\0') 
        {
                int c = *str;
                    /* hash = hash*33 + c */
                    hash = ((hash << 5) + hash) + c;
                    str++;
        }
        return hash;
    }
};

Je viens de voir qu'il y a un new et un stringstream là-dedans
Là je ne m'étonne plus si on me dis que ce n'est pas performant !
Ceci est tellement plus simple (et intuitif)

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

const unsigned char *str = s.c_str();

[Goten]

Au delà de ça (et oui t'as raison), le stringstream est... vide là.. donc euh, il va rien ce passer.
ça serait plutôt :
std::stringstream ss(s);
ss >> str;

edit : const char vers const unsigned char, le compilo va pas aimer .

[guillaume07]

oui désolé, erreur dans le C+c C+v du bout de code,
initialement je faisais bien ça

const unsigned char *str = static_cast<const unsigned char *>(s.c_str());



j'avais juste un doute concernant le casting en unsigned, donc j'ai testé avec un stringstream( que j'initialisé bien) voir si ça changer quelquechose

[Goten]

Et accessoirement un delete[] serait pas superflu...

[guillaume07]

[Lightness1024]

La complexité d'une table de hachage est inférieur à celle d'une map. Toutefois, dans le cas des string par exemple, la fonction de hachage est assez lourde.

En coséquence, pour n données, tu aura par exemple :

• 10 + log (5n) opération pour une map
• 200 Pour une table de hachage.

Donc il va falloir que tu es une grande table pour compensez le coefficient constant.

précise les choses:

pour les chaînes il faut raisonner en terme de nombre de caracteres.
les operations pour les map sont: log(inf_comparaison)
et pour les hash_map sont: 1xMakeHash + amortized O1(equality_compare)

faire une comparaison d'infériorité peut être interrompu rapidement si les premiers caracteres des chaines diffèrent.
pour faire un hash il faut forcément lire tous les caracteres, mais UNE fois.

qui sera plus rapide ?

[Lavock]

pour faire un hash il faut forcément lire tous les caracteres, mais UNE fois.

Qu'est-ce qui m'empêche de faire une fonction de hachage en ne regardant que N caractères ?

De manière générale, ont peu remarquer que les map de string "paniquent" un peu lorsqu'on on les soumet à des chaines de caractère longue est semblable... Modulo le fait qu'on puisse aussi passer un comparateur, et que le dit comparateur peut être personnalisé !*

De manière général, on retiens que à même complexité de chaine, utilisé une table de hachage plutôt qu'une map est d'autant plus avantageux qu'il y a d'élément; mais qu'en dessous d'un certain nombre cela ne vaut pas le coup.

* Par exemple, pour des numéros de séries, on peut généralement dégager des "groupes" qui on souvent une valeur identique. On pourra, au lieu de comparer tout, sauter aisément certain caractère, s'il n'est pas nécessaire de pouvoir parcourir une liste classé de la map.

Edit : A y réfléchir, le dernier "si" n'as pas lieu d'être. Je crois pas qu'une map nécessite de pouvoir être parcourue par ordre de grandeur de ces clefs (j'ai mis les balise S pour le jours ou le fofo gérera la balise strike ).