algo pour suppression de lignes en double ds un fichier ??

Recherche :

Dernière réponse
Sujet : algo pour suppression de lignes en double ds un fichier ??
rem5	Merci pour l'eclaircissement, mais bon n'ayant en tete que le quicksort et ayant rarement des fichier gigantesque (au max 1000 lignes d'1 30aine de char chacun) c peu etre pas la peine que je passe trop trop de tps a faire de l'optimisation et comme c pour le boulot et que mon boss a horreur de tt ce que qui ne s'appelle pas VB (pffuuuu....). Mais bon 1 de ces 4 quand meme quand j'aurais un peu de tps je le referais en asm ca n'ira pas plus mal et puis je prefere Merci encore

Dernière réponse

Sujet : algo pour suppression de lignes en double ds un fichier ??

rem5

Merci pour l'eclaircissement, mais bon n'ayant en tete que le quicksort et ayant rarement des fichier gigantesque (au max 1000 lignes d'1 30aine de char chacun) c peu etre pas la peine que je passe trop trop de tps a faire de l'optimisation et comme c pour le boulot et que mon boss a horreur de tt ce que qui ne s'appelle pas VB (pffuuuu....).

Mais bon 1 de ces 4 quand meme quand j'aurais un peu de tps je le referais en asm ca n'ira pas plus mal et puis je prefere

Merci encore

Votre réponse

Nom d'utilisateur

Pour poster, vous devez être inscrit sur ce forum .... si ce n'est pas le cas, cliquez ici !

Le ton de votre message

Votre réponse

Smilies

Liste des smilies perso
Wiki smilies
Chercher un smiley

Options

Activer votre signature
Désactiver les smilies
Activer la notification par email du sujet

Aperçu

Vous avez perdu votre mot de passe ?

Vue Rapide de la discussion

rem5

ça c'est limite de l'optimisation !

:hello:

Requin

En fait l'ago de tri que tu vas utiliser dépend du nombre de résultat à trier...

Un simple tri par bulles prendra bcp de temps, mais pour peu d'éléments il n'est pas pénalisant (nombre de permutation en n^2).

Un tri récursif selon Hoare (quicksort) est assez efficace et simple à mettre en oeuvre (nombre de permutations : n (minimum), n log n (moyenne) et n^2 (maximum))

Le mieux si tu as beaucoup d'éléments est le tri par fusion ou tri par interclassement (n (minimum) et n log n (en moyenne et dans le pire des cas))... mais le code est un peu pénible à écrire.

[edtdd]--Message édité par Requin--[/edtdd]

ben ché pas... à moins que tu aies une autre solution ?

en plus ce fichier ou on veut supprimer les lignes en doubles
c'est quoi ? c'est sur une BDD ?

:hello:

TheNicow

Bah ca c'est presque pire que la premiere méthode.
Il n'a pas besoin de savoir combien de fois la ligne était présente, simplement de les virer. Si tu les comptes, et que tu les vires après, tu vas avoir 2 fois plus de tests.

[:thenicow]

compte le nombre de fois que tu trouves la même ligne
et après tu dégages tout ce qui apparait plus de fois !

:hello:

TheNicow

On va essayer de faire simple.

Ta premiere soluce qui est la plus simple va tourner en n² à tous les coups. 500+499+... ~ 500²
Donc, si t'as un petit fichier, ca va aller, mais des que ca va grossir, ca va exploser...

Donc la parade reviendrait en effet à trier les lignes avant de faire la comparaison. Le quicksort tourne en n.log(n) en moyenne. Ca veut dire que en général il est très performant. Mais tu auras des cas rares ou il va tourner en n² également.

Par exemple, si toutes les lignes sont déjà triées, ou alors triées dans le sens contraire (je ne sais plus).

Pour un algo de tri en n.log(n) en moyenne et au maximum, il faut regarder du coté du tri par tas (HeapSort).

Mais bon, il faut surtout voir sur quel genre de fichier tu vas faire tourner ca.

[:thenicow]

rem5

UP ;)

rem5

Quelle serait la solution la plus rapide entre comparer la 1er ligne avec tte les autres et ainsi de suite ou alors faire un quick-sort sur le fichier puis juste comparer chaque ligne avec la suivante ??? (voire meme faire tt en meme tps au moment du tri)

la premiere nous ferais (sur 500 lignes) : 499+498 (ou - si doublons)+497+... comparaisons

mais la 2eme ??

Je pense que la methode avec le quick-sort serais beaucoup + rapide mais j'ai pas du tt d'ordre d'idée.

Ou alors si qqu'un a encore un algo mieux :wahoo:

Merci d'avance

[edtdd]--Message édité par rem5--[/edtdd]