Discussion :

[jcaspar]

B onjour à tous !

Pourriez vous m'expliquer un algorithme de suppression de doublons
dans un tableau

|Nom|Prenom|Adresse|Ville|

Meric d'avance pour vos explications

Jean Marc

[PRomu@ld]

Il faut déjà que tu choisisses le champ que tu désires supprimer.

Alors ensuite, suivant les méthodes, tu as :

-> la bête et méchante, tu regardes chacune des lignes et tu supprimes celles qui sont identiques (au moins sur le champ que tu veux).

-> un peu plus subtil : tu effectues un tri sur le champ que tu veux, puis tu passes en revue toutes tes lignes et les doublons sont forcément à la suite ce qui limite les recherches et permet une opération efficace.

[davcha]

Encore plus subtil : tu crées une clef de hashage sur les colonnes qui doivent être concernées par la suppression des doublons, et tu recopies ton tableau dans une table de hashage en utilisant la clef de hashage créée précédemment.
Ensuite, tu vires les clefs, tu récupères ton tableau, y'a plus de doublons.

[PRomu@ld]

et tu recopies ton tableau dans une table de hashage en utilisant la clef de hashage créée précédemment.

Attention, ça reste difficilement applicable sur de très gros tableaux ce qui risque d'être le cas (l'exemple donné fait penser à une table de base de donnée).

[davcha]

Si c'est une table de base de donnée, dans ce cas, une clef unique sur les champs concernés, pas besoin de plus...

Sinon, je vois pas trop pourquoi ça ne serait pas applicable sur de grosses tables.

[PRomu@ld]

Le problème, c'est l'espace de stockage nécessaire pour ton opération suivante :

et tu recopies ton tableau dans une table de hashage en utilisant la clef de hashage créée précédemment.

Ca ne représente aucun problème si tu as un nombre raisonnable de valeurs. Mais pour un très grand nombre de valeur, ça risque devenir problématique. Les méthodes que j'ai cité (même si elle ne sont pas parfaites), ont la caractéristique principales de travailler sur place. (l'espace nécessaire au tri est négligeable par rapport à la taille de la table).

[davcha]

Tout dépend du taux de collisions.

[Jedai]

Ca ne représente aucun problème si tu as un nombre raisonnable de valeurs. Mais pour un très grand nombre de valeur, ça risque devenir problématique. Les méthodes que j'ai cité (même si elle ne sont pas parfaites), ont la caractéristique principales de travailler sur place. (l'espace nécessaire au tri est négligeable par rapport à la taille de la table).

Certes, mais au pire tu as approximativement un doublement de l'espace requis (la table plus la table de hachage, et s'il y a beaucoup de doublons, ça compense, évidemment il faut également qu'il n'y ait pas trop de collisions, ce qui risque de demander plus qu'un doublement...). Et s'il y a vraiment trop de lignes, alors la meilleure solution est très probablement d'en passer par une base de donnée de toute façon.

--
Jedaï

[PRomu@ld]

Certes, mais au pire tu as approximativement un doublement de l'espace requis

J'aime ton euphémisme, imagine une table contenant admettons 2 Go de données, la doubler me semble irréalisable. D'une part aura t'on la place pour stocker les données temporaires. D'autre part, il est relativement rare d'avoir la place en RAM pour stocker ce doublon, par conséquent, on va être obligé de "swapper" énormément, e là, les temps de calculs sont énormement plus long qu'en RAM. Enfin, quand bien même le temps ne compterait pas, sera t'on sur d'avoir un système permettant un swap aussi grand.

[méphistopheles]

une petite question comme ça: quel est l'ordre du hachage ?

il me semble que quicksort est O(x*ln(x)) donc la méthode subtile doit être en O(x(1+ ln(x)))
la bête et méchante est en O(x²) je pense ...

et le hachage? (d'ailleurs, tous les hachages suppriment les doublons ?)


merci.

[Sivrît]

Calculer un hash nécessite une simple passe (à peine pire que la comparaison) et l'accès doit être directe. Ce cas étant simple la dispertion devrait être bonne et si on néglige les collisions on doit avoir du O(x). Mais comme les données doivent tenir en mémoire il se peut que ça n'aide pas trop par rapport à du O(x*ln(x))... à moins peut-être de ne garder que le hash et un n° d'index.

Ce qui va vraiment compter c'est de savoir si les données sont en RAM ou sur le disque, et si on peut les charger ou ne serait-ce que les indexer en RAM.

[PRomu@ld]

une petite question comme ça: quel est l'ordre du hachage ?

il me semble que quicksort est O(x*ln(x)) donc la méthode subtile doit être en O(x(1+ ln(x)))
la bête et méchante est en O(x²) je pense ...

et le hachage? (d'ailleurs, tous les hachages suppriment les doublons ?)


merci.

Visiblement tu n'as pas compris ma remarque, elle ne concerne absolument pas la complexité en temps mais la complexité en espace.

La table de hachage a une complexisté en temps qui est proportionnelle à ta fonction de hachage, La conplexité de ta fonction de hachage n'apparait pas dans la complexité (on n'affiche pas les constantes). Entre deux algos en n log n, l'un peut être 4 fois plus rapide que l'autre ... .

Pour en revenir à ma remarque, la complexité en espace est relativement importante dans ce cas, et comme l'a dit Sivrît, ce n'est pas parce que la complexité en temps est plus faible que la méthode dans la pratique va être plus rapide.

[méphistopheles]

A vrais dire, je demandais juste dans un cadre purement théorique la fonction de complexité du hachage (vous auriez un algo en exemple ?) car je connais mal ces fonctions là. (et comme ce n'est pas moi qui a posé la question initiale...)

merci.

[Sivrît]

A vrais dire, je demandais juste dans un cadre purement théorique la fonction de complexité du hachage (vous auriez un algo en exemple ?) car je connais mal ces fonctions là. (et comme ce n'est pas moi qui a posé la question initiale...)

merci.

Il me semble que les String Java sont typiques :

Code java :

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

1
2
3
4
5
6
7
8
9
10
11
12
 
public int hashCode()
{
   if (cachedHashCode != 0)
      return cachedHashCode;
   // Compute the hash code using a local variable to be reentrant.
   int hashCode = 0;
   int limit = count + offset;
   for (int i = offset; i < limit; i++)
      hashCode = hashCode * 31 + value[i];
   return cachedHashCode = hashCode;
}

(oui je sais, du code dans ce forum c'est mal )

Si c'est plus complexe on peut jouer avec des XOR ou appliquer la même formule entre les hash des différentes parties.

[PRomu@ld]

Essaie de (re)poser ta question dans le forum, si le sujet t'intéresse, je doute que tu sois le seul, de plus tu devrais avoir plus de réponses si tu crées un nouveau sujet.