unordered map

Version imprimable

18/01/2010, 07h53
guillaume07

unordered map

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 !
18/01/2010, 09h51
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.
18/01/2010, 09h57
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.

j'utilise celle ci :

Code:

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;
    }
};

18/01/2010, 10h22
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.
18/01/2010, 10h26
guillaume07
Citation:
Envoyé par 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.
à 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
18/01/2010, 10h31
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.
18/01/2010, 10h32
guillaume07

Citation:

Envoyé par 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.

toutes mes chaines ont cette allure : "B0221800N05CF1C"
Pour les collisions, je n'ai pas le chiffre
18/01/2010, 10h35
Lavock

Citation:

Envoyé par guillaume07

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

Oui, mais

Citation:

Envoyé par guillaume07

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.

Citation:

Envoyé par guillaume07

j'utilise celle ci :

Code:

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 8O
Là je ne m'étonne plus si on me dis que ce n'est pas performant !
Ceci est tellement plus simple (et intuitif)

Code:

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

18/01/2010, 12h03
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 :).
18/01/2010, 12h07
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
18/01/2010, 12h08
Goten

Et accessoirement un delete[] serait pas superflu...
18/01/2010, 12h21
guillaume07

:oops:
18/01/2010, 15h30
Lightness1024
Citation:
Envoyé par 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.
:) 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 ? :)
18/01/2010, 16h12
Lavock

Citation:

Envoyé par Lightness1024

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 :P ).