Non, rassures toi. Le THashedStringList utilise bien le HashOf pour indéxer les chaînes, mais il vérifie ensuite que la (ou les) chaînes ayant ce hash sont identiques à la chaîne recherchée.Envoyé par Art19
Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter
Non, rassures toi. Le THashedStringList utilise bien le HashOf pour indéxer les chaînes, mais il vérifie ensuite que la (ou les) chaînes ayant ce hash sont identiques à la chaîne recherchée.
En fait c'est un peu plus compliqué. La valeur du hash est utilisée pour l'insertion et la recherche dans un arbre binaire équilibré, donc avec des fonctions d'insertion et de recherche ayant une complexité en O(log2(n)). C'est à dire que lorsque l'on double le nombre de valeurs la recherche et l'insertion augmentent de façon linéaire.
voir par exemple http://fr.wikipedia.org/wiki/Arbre_binaire_de_recherche
alors quel est l'interet de hasher?Non, rassures toi. Le THashedStringList utilise bien le HashOf pour indéxer les chaînes, mais il vérifie ensuite que la (ou les) chaînes ayant ce hash sont identiques à la chaîne recherchée.
ah oui c'est bon j'ai compris (il regarde si les chaines sont identiques que quand le hash est identique.. is that it?)
A Art19 : Mille excuses de t'avoir fait peur à propos de mes constats avec les HashOf.
A Sovitec : : Merci pour ces infos rassurantes / THashedStringList (ruse de Sioux : mais il vérifie ensuite que la (ou les) chaînes ayant ce hash sont identiques à la chaîne recherchée).
Vu Wikipédia/Arbre binaire de recherche : Et dire qu'avec toute cette usine-à-gaz située en arrière-plan des THashedStringList cela ait quand-même permis à Art de multiplier par 1000 la rapidité d'exécution de son code ... ben chapeau!
Au fait c'est quoi la formule du "... hash MD5" histoire de comparer avec la formule du HashOf(string)? (simple curiosité intellectuelle).
A+
bon merci a vous..
Gilbert, j'ai dit 1000 mais c'est un peu une expression parce que je n'ai pas mesure. Mais c'est vraiment beaucoup beaucoup plus rapide.. c'est sur que la Hashed est optimisee pour ce genre de requetes.. il faut juste le savoir.. apres c'est interessant de savoir ce qu'il se passe derriere
Si tu remets une TStringList mais que tu ajoute Sorted := True, est-ce vraiement différent de la THashedStringList ?
Aide via F1 - FAQ - Guide du développeur Delphi devant un problème - Pensez-y !
Attention Troll Méchant !
"Quand un homme a faim, mieux vaut lui apprendre à pêcher que de lui donner un poisson" Confucius
Mieux vaut se taire et paraître idiot, Que l'ouvrir et de le confirmer !
L'ignorance n'excuse pas la médiocrité !
L'expérience, c'est le nom que chacun donne à ses erreurs. (Oscar Wilde)
Il faut avoir le courage de se tromper et d'apprendre de ses erreurs
A Art19 : "il faut juste le savoir.. apres c'est interessant de savoir ce qu'il se passe derriere" : Exact, mais il y a tellement de trucs à savoir! On n'arrête pas de découvrir et je n'en suis qu'à Delphi-5 ...
Je vais faire quand-même faire des tests pour voir s'il n'y a pas moyen de faire un peu plus speed avec une lecture via TFileStream ... et avec chrono à l'appui.
Cela m'occupera demain.
A+
Oui, exactement.
Tu peux trouver le principe là.
La principale différence avec le HashOf de Delphi est que le hash est sur 128 bits et que deux chaînes très proches engendrent des hash très différents. Du fait que le hash est sur 128 bits le paradoxe des anniversaires montre que la probabilité que deux chaînes différentes aient un hash identique est négligeable quand le nombre de chaînes est d'un ordre inférieur à 2^60 (un milliard de milliards). Concrètement la première collision sur des hash MD5 date de moins de trois ans, et résulte d'une construction mathématique très complexe, on n'a jamais réussi à générer une collision "par hasard". De ce fait on peut se contenter de comparer uniquement les hash dans l'application qui nous intéresse, pas besoin de conserver la chaîne elle même.
L'insertion dans un TStringList se fait en O(n) losque Sorted = True (Il faut décaler toutes les chaînes suivant celle que l'on veut insérer). Donc la recherche est rapide, mais l'insertion lente, ce qui est l'opposé du cas Sorted = False où l'insertion est rapide mais la recherche lente.
est-il raisonable de supprimer les doublons en :
* trier le fichier en appliquant un tri a bulles
* comparer chaque ligne a la ligne precedente
?
Le tri à bulle n'est pas forcément adapté à un fichier de grande taille. Autre écueil : si les enregistrements du fichier sont de taille variable, cela va compliquer l'algorithme.
cdlt
M E N S . A G I T A T . M O L E M
Debian 64bit, Lazarus + FPC -> n'oubliez pas de consulter les FAQ Delphi et Pascal ainsi que les cours et tutoriels Delphi et Pascal
"La théorie, c'est quand on sait tout, mais que rien ne marche. La pratique, c'est quand tout marche, mais qu'on ne sait pas pourquoi. En informatique, la théorie et la pratique sont réunies: rien ne marche et on ne sait pas pourquoi!".
Mais Emmanuel Kant disait aussi : "La théorie sans la pratique est inutile, la pratique sans la théorie est aveugle."
le meilleur algo doit etre le quicksort j'imagine. quelqu'un peut me l'expliquer rapidement sur un petit exemple svp?
Pour tout dire, je suis en train de travailler sur le sujet (recherche de doublons en maintenant un fichier d'index triés grâce au QuickSort),
ça avance mais je n'ai pas beaucoup de temps devant moi. La solution sur laquelle je travaille devrait m'affranchir des limites de taille sur les fichiers à 2 Go mais je n'ai pas d'idée précise sur la performance de la solution.
cdlt
M E N S . A G I T A T . M O L E M
Debian 64bit, Lazarus + FPC -> n'oubliez pas de consulter les FAQ Delphi et Pascal ainsi que les cours et tutoriels Delphi et Pascal
"La théorie, c'est quand on sait tout, mais que rien ne marche. La pratique, c'est quand tout marche, mais qu'on ne sait pas pourquoi. En informatique, la théorie et la pratique sont réunies: rien ne marche et on ne sait pas pourquoi!".
Mais Emmanuel Kant disait aussi : "La théorie sans la pratique est inutile, la pratique sans la théorie est aveugle."
Puisque tu as déjà une méthode pour supprimer les doublons pourquoi vouloir faire un tri maintenant ? La problématique à changé ?
Sinon si le quicksort est bien en O(nLog(n)) en moyenne (donc optimal) il est par contre en O(n²) dans le pire des cas (donc pas meilleur qu'un algorithme naïf). Et le pire des cas se produit facilement, il suffit que l'ensemble soit déjà trié.
vu que j'ai 19 000 fichiers qui ne sont pas tries le pire des cas ne risque pas d'arriver...
je n'ai jamais dit que j'avais une methode pour supprimer les doublons.. je sais juste reperer si il y a AU MOINS un doublon dans un fichier c'est toutPuisque tu as déjà une méthode pour supprimer les doublons pourquoi vouloir faire un tri maintenant ? La problématique à changé ?
Ma solution (non encore testée ni publiée) risque de peiner sur 19 000 fichiers mais elle devrait être adaptée à un gros fichiers.
Est-ce que tes fichiers peuvent être fusionnés, en d'autres termes est-ce leur contenu est compatible?
Je rappelle ce que je disais tout à l'heure, un tri Shell est pratique à mettre en oeuvre dans une structure indexée, ce qui n'est pas forcément le cas avec un fichier texte. En outre un tri directe sur les chaînes de caractères risque de plomber les perf.
cdlt
M E N S . A G I T A T . M O L E M
Debian 64bit, Lazarus + FPC -> n'oubliez pas de consulter les FAQ Delphi et Pascal ainsi que les cours et tutoriels Delphi et Pascal
"La théorie, c'est quand on sait tout, mais que rien ne marche. La pratique, c'est quand tout marche, mais qu'on ne sait pas pourquoi. En informatique, la théorie et la pratique sont réunies: rien ne marche et on ne sait pas pourquoi!".
Mais Emmanuel Kant disait aussi : "La théorie sans la pratique est inutile, la pratique sans la théorie est aveugle."
mes fichiers ne doivent surtout pas etre fusionnes looool
personnellement ma preference va vers le tri a bulles car il est nettement plus facile a implemanter que le quick sort.. mais en meme temps le quick sort s'avere etre beaucoup plus rapide dans le meilleur des cas
Oui, mais il est facile d'étendre la méthode de recherche de doublon. Il suffit de ne pas insérer les chaînes qui sont des doublons, puis de réécrire le THashedStringList dans un fichier si des doublons ont été détectés.
c'est vraiment pas bete du tout ca! comment n'y avais-je pas pense.. le seul truc c'est que dans mon algo actuel, je fais un break des que je repere le 1er doublon.
autre inconvenient: je ne sais pas si je pourrais loader tout un fichier dans une THashedStringList..
reste a savoir aussi la performance d'un SaveToFile..
qu'en pensez vous?
Si tu veux un exemple de mise en oeuvre du tri quicksort, étudie le code de la méthode TList.Sort (dans l'unité Classes de la VCL). Il n'y a pas d'explication mais le code est facile à adapter.
cdlt
M E N S . A G I T A T . M O L E M
Debian 64bit, Lazarus + FPC -> n'oubliez pas de consulter les FAQ Delphi et Pascal ainsi que les cours et tutoriels Delphi et Pascal
"La théorie, c'est quand on sait tout, mais que rien ne marche. La pratique, c'est quand tout marche, mais qu'on ne sait pas pourquoi. En informatique, la théorie et la pratique sont réunies: rien ne marche et on ne sait pas pourquoi!".
Mais Emmanuel Kant disait aussi : "La théorie sans la pratique est inutile, la pratique sans la théorie est aveugle."
Vous avez un bloqueur de publicités installé.
Le Club Developpez.com n'affiche que des publicités IT, discrètes et non intrusives.
Afin que nous puissions continuer à vous fournir gratuitement du contenu de qualité, merci de nous soutenir en désactivant votre bloqueur de publicités sur Developpez.com.
Répondre avec citation
Partager