Discussion :

[Array]

Bonjour,

Je me trouve face à un dilemme conçernant le choix d'un algorithme approprié pour une tâche. Mon programme doit recevoir en entrée un tableau de longueur inconnue contenant des chaînes séparées avec des délimiteurs (delimiter separated values). Donc, j'ai une fonction map() qui indexe chaque « string » dans un tableau de pointeurs, remplaçant au passage le délimiteur avec un caractère nul ('\0'). À la fin de la fonction map(), je connais le nombre de chaînes à traiter.

Ce que je dois faire, ensuite, c'est : comparer les chaînes entre elles pour voir si il y a des chaînes redondantes. Or, il se peut bien qu'il y ait 10000 chaînes à traiter, de longueurs variables, comme il pourrait en avoir 10…

J'ai pensé utiliser un algorithme de hash dans la fonction map() pour enregistrer le hash de toutes les chaînes et ensuite comparer uniquement les hash… car je ne peux me résoudre à utiliser le bon vieux strcmp(). Ce serait trop long dans les cas extrêmes.

Donc, quel hash utiliser? J'aimerais que le hashing soit rapide, donc il me faut un algorithme assez rapide et sans trop de collisions. J'avais pensé à CRC32, mais comme on ne connaît pas la longueur des chaînes et que les possibilités du CRC32 sont couvertes que dans un int, j'ai bien peur qu'il y ait des collisions…

S.V.P., aidez-moi.

Merci,

Array.

[Obsidian]

Bonsoir,

J'avais pensé à CRC32, mais comme on ne connaît pas la longueur des chaînes et que les possibilités du CRC32 sont couvertes que dans un int, j'ai bien peur qu'il y ait des collisions...

C'est un peu le principe du hash, cela dit. Une fonction de hachage est une application surjective. Le problème n'est pas tant qu'il y ait des collisions, mais plutôt que celles-ci ne se produisent pas avec des chaînes trop proches, et qu'elles ne soient pas trop fréquentes. Si cette dernière condition est remplie en particulier, alors tu peux te permettre de faire suivre cette opération par une comparaison des chaînes pour voir s'il s'agit ou non d'un faux positif. Tout l'intérêt résidant dans le fait que cela doit demeurer exceptionnel.

S.v.p. Aidez-moi

Je vais peut-être dire une bêtise mais le plus censé ne consisterait-il pas à trier tes chaînes au moment où tu les lis ? Le classement se ferait en une passe et tu saurais immédiatement, à chaque fois, s'il y a des doublons ou pas.

[Array]

Malheuresement, ce serait trop long, de 1, et de deux, il y a une priorité dans les chaînes qui doit absolument être gardée.

Voilà cependant que j'ai pensé à utiliser le CRC32 suivi de Adler32 (qui est plus rapide), et ranger le tous dans une variable long long 64 bit.
Comme en plus, dans la fonction map(), les longueurs des chaînes sont calculées, je pourrais également faire une struct du genre

Code :

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

struct mystruct { int crc32, int adler32, int size, char *strbytes }

[Mac LAK]

Tu peux résoudre le problème de tri très facilement grâce à une LUT : tu initialises un vecteur(N,2) contenant les indices de tes chaînes, et tu tries la deuxième colonne en fonction des chaînes indexées par la valeur contenue dans la cellule. Par contre, du coup, ta map n'est pas forcément le container le plus adapté, il faudra peut-être privilégier un vecteur à la place (il te faut en effet les indices des chaînes pour créer la LUT).

De cette façon, tu vas :

• Conserver l'ordre initial de tes chaînes (ce qui est important dans ton cas).
• Avoir malgré tout une liste correspondante triée.
• Supprimer les doublons avec une liste triée devient trivial, et est en complexité O(N).

Pour le principe de hachage, de toutes façons, tu n'aurais pas été mieux loti (et, au passage, un bête CRC16 serait certainement amplement suffisant de toutes façons). En effet : comment associer la clé à la chaîne ? Via une sorte de LUT, qu'il aurait fallu ... trier de toutes façons !

Certes, tu vas échanger sur ce coup des comparaisons de chaîne avec des calculs de hachage. Il serait étonnant que la solution que je te propose soit plus lente, SAUF si les chaînes sont massivement semblables (ex : chaînes de plusieurs centaines de caractères qui ont toutes des dizaines de caractères en commun).

A ta place, je ferais ceci :

• Lecture des chaînes et rangement dans le container de façon triée (insertion triée, donc), ce qui devrait être moins pénalisant que le tri après chargement complet.
• Maintien de façon simultanée de la LUT correspondante. Le point difficile est là, il faudra penser à utiliser des références / pointeurs dans la 2ème colonne pour ne pas péter le lien.
• Passe de suppression des doublons : pour éviter les nombreux resize du vecteur, tu peux là encore créer une (sorte de) LUT qui ne contiendra QUE les chaînes uniques, dans l'ordre d'arrivée grâce à la LUT primaire.

[Array]

Hmmm,

Cette dernière solution, il est vrai, est la meilleure, à quelques modifications près: En combinant un CRC32 au tri, les chaînes à proximité avec le même CRC seront nécessairement pareilles, et même je peux utiliser dans ce cas Adler32, qui est bcp plus rapide pour un peux moins de résistance.

Donc, tri puis Adler32 au passage.
Pourquoi un hash au passge? Parce que les chaînes, en effet, peuvent varier d'un min de 1 caractère pour 512 caractères.

Mais pour avoir une lookup table, il me faut être en C++ non?
Or je veux un code CPP-free (i.e. en C90 pur, voire C99), donc, serais-ce possible quand même, sans vecteur C++???

J'attends vos rép!

Array


P.S.

Pour le principe de hachage, de toutes façons, tu n'aurais pas été mieux loti (et, au passage, un bête CRC16 serait certainement amplement suffisant de toutes façons). En effet : comment associer la clé à la chaîne ? Via une sorte de LUT, qu'il aurait fallu ... trier de toutes façons !

J'avais pensé à faire un array de structures ayant, de 1, un pointeur sur le début de toutes les chaînes avec, de 2, le crc assoicié à la chaîne pointée.

[Mac LAK]

Cette dernière solution, il est vrai, est la meilleure: En combinant un CRC32 au tri, les chaînes à proximité avec le même CRC seront nécessairement pareilles, et même je peux utiliser dans ce cas Adler32, qui est bcp plus rapide pour un peux moins de résistance.

Inutile : à part si tu as des données en quantité absolument colossale (je parle d'une cardinalité approchant le MILLION, là, avec des problèmes de dispersion largement plus problématiques), un CRC sur un domaine d'au moins quatre fois la cardinalité moyenne est habituellement suffisant. Ici, tu parles de 10.000 chaînes, donc un CRC16 est très certainement amplement suffisant.
De toutes façons, je pense que la solution d'une LUT permettant le tri est supérieure à une comparaison par fonction de hachage, vu le volume et le type des données que tu manipules.

Mais pour avoir une lookup table, il me faut être en C++ non?

Pourquoi donc ?? J'implémentais des LUT en ASM, et sans problèmes, donc je ne pense pas vraiment que le faire en C soit un souci...
C'est un bête tableau dont l'indice correspond à une valeur d'entrée, et le contenu de la cellule à la donnée de sortie, ni plus, ni moins. En général, si l'on veut une double association (pouvoir convertir dans un sens et dans l'autre), on "jointe" logiquement deux vecteurs, mais c'est la seule subtilité possible que je vois dans une LUT...

Le seul problème que tu auras en C, c'est la non-allocation automatique du vecteur. Il te faudra donc jouer avec des realloc de granularité suffisante, et je ne saurais trop te conseiller de rendre cette granularité paramétrable dans ton code (#define de préférence) afin de pouvoir optimiser les perfs sans devenir dingue.

Or je veux un code CPP-free (i.e. en C90 pur, voire C99), donc, serais-ce possible quand même, sans vecteur???

Implémenter un vecteur auto-allouant en C n'est pas très difficile, tout passe par le realloc. Tu n'as pas à te soucier, à priori, de la possibilité de réduire le vecteur (il ne peut que grandir).
Le seul problème "réel" se situe dans l'insertion triée, en fait, faudra faire le code soigneusement. Tu peux toujours, dans un premier temps, faire l'essai en triant après chargement complet, juste histoire de mettre l'algo au point.