[1.1] Quelle alternative à Hashtable et ArrayList ?

Version imprimable

09/08/2006, 17h24
maitrebn

[1.1] Quelle alternative à Hashtable et ArrayList ?
Bonjour,

Afin de résoudre un pb, je cherche une collection qui aurait pour répondre au besoin suivants :
- Savoir si un élément est déjà présent,
- Pouvoir boucler dessus dans l'ordre ou je l'ai insérés.
Au début, je n'avais que le premier besoin donc j'étais parti sur la hashtable. Maintenant, il faut que je boucle dans l'ordre d'insertion ... qui n'est pas garantie avec Hashtable.

Là, j'en suis réduit à avoir une hashtable d'un coté et de l'autre une arraylist ... C'est pas terrible ...

Si quelqu'un a une idée ! Merci !
09/08/2006, 17h29
dev01

Salut .

Si tu travailles en dotnet 2.0 je te conseil de laisser tomber les ArrayList au profit des List .

Sinon les ArrayList (et les List<>) ont une méthode Contains qui permet de savoir si un élément est présent dans la liste ou pas ... :roll:
09/08/2006, 18h33
maitrebn

Malheureusement, je suis en 1.1 ... donc j'ai pas les templates ...
09/08/2006, 18h40
Mose

Citation:

Envoyé par dev01

Sinon les ArrayList ont une méthode Contains qui permet de savoir si un élément est présent dans la liste ou pas ...

Bah alors maitrebn ? Faut lire les réponses jusqu'au bout !
09/08/2006, 19h00
maitrebn
Oui, j'avais lu :-) !

Je répondais uniquement sur la partie framework pour exprimer ma détresse :P ;) !

J'ai oublié de mettre la citation ...

Alors pour info : j'ai fait quelque test et pour le moment :
- * Hash + Arl : + mauvais en mémoire (9 Mo) et en temps (234 ms),
  * Arl tout seul : moyen partout (2 Mo & 170 ms),
  * Array typé : meilleur ( 120 Ko & 70 ms).
Bon maintenant faudrait que j'essaye avec mes vrais objets :-) !
09/08/2006, 19h04
Mose

Intéressant tes stats, mais peux-tu préciser un peu :
combien d'éléments tu mets dedans, et que fais-tu en 239 ms ?

Si tu peux poster ton code de test, ça m'intéresserait que qqn l'essaye aussi pour avoir un comparatif avec les List de .Net 2, pour savoir si je dois m'y mettre ou pas :)
09/08/2006, 19h13
cinemania

C'est domage que tu ai besoin de l'ordre dans lequel tu les a introduite plutot qu'un ordre trié, sinon j'taurais conseillé d'implanter un modele de données qui n'est pas présent dans le framework mais qui possède les avantages d'une liste linéaire et d'un arbre de recherche (recherche en temps logarithmiques plutot que linéaire ce qui est un gain énorme pour une liste "énorme")
09/08/2006, 19h53
maitrebn

Citation:

Intéressant tes stats, mais peux-tu préciser un peu :
combien d'éléments tu mets dedans, et que fais-tu en 239 ms ?

--> Pas grand chose :-) (Je ferais plus de test demain) :
J'ai crée 3000 éléments puis je boucle sur chaque et j'ajoute deux fois un même élément 50 fois. C'est pas énorme je sais ...

Citation:

C'est domage que tu ai besoin de l'ordre dans lequel tu les a introduite plutot qu'un ordre trié

--> Je prends quand même ... on sait jamais ...
10/08/2006, 01h36
cinemania

Cette technique ne fonctionne que dans un ordre trié. Et il s'agit d'une implantation particulière des listes

Si tu trouve des documents relatifs, on appel cette structure les SkipList. Si toutefois tu trouve rien dessus, laisse moi un MP je t'expliquerais le principe, meme si l'implantation est un peu plus compliquée que celle d'une vulgaire liste chainée, elle n'en reste pas moins nettement plus rapide lors d'une recherche.
Toutefois, les skiplists ont un intérêts si tu dispose d'un entier numérique comme "clé" ou champ de référence, car c'est là quelles serons les plus interressantes. Donc si tu as un algo qui te donne une valeur numérique pour les types que tu utilise, c'est parfait :)
10/08/2006, 08h49
maitrebn

Malheureusement ma clé est un UID ... donc je pense que cela ne marchera pas mais je vais quand même chercher sur le sujet !

Merci !
10/08/2006, 09h56
neguib

J'avoue que je suis un peu interloqué d'une certaine contradiction entre le déroulement de la discussion ets le titre de départ:

Citation:

[1.1] Entre la hashtable et l'arraylist mais ni l'un ni l'autre

Si c'est une alternative que tu cherches, il reste l'implémentation typée de l'extention de CollectionBase, qui d'ailleurs possède un champ de type ArrayList
10/08/2006, 13h17
maitrebn
En fait, je voulais le beurre et l'argent qui va avec ... C'est à dire l'accès indexé de la hashtable ainsi que l'accès ordonné selon l'ajout de l'arraylist ...

Sinon, effectivement, il reste cette solution.

Ps : pour info, j'ai refait des stats et rien de surprenant :
En augmentant le nombre d'ajout ( 6 millions en gros ):
- La hashtable est plus rapide ( 4 sec) pour en temps mais bouffe bcp plus de mémoire (130 Mo),
- La arrayliste est plus longue en temps ( 20 sec) mais prend moins de mémoire (21 Mo),
- La table est pire en temps (25 secs) et idem en en mémoire (21 Mo) ...
A noter que pendant longtemps dans mon test, le tableau était toujours meilleur en mémoire que l'arraylist ...
10/08/2006, 13h38
Thomas Lebrun

D'après tes derniers tests, je te conseille celui qui est le plus rapide.

En effet, aujourd'hui, ce que tu va demander à ton application, c'est quelle soit rapide.
Pour ce qui concerne la consommation mémoire, de nos jours, il est rare de voir un PC avec moins de 512 Mo de RAM.... ;)
10/08/2006, 18h10
maitrebn

Au départ, je pensais comme toi ... mais depuis j'ai changé :-) !

Donc je suis parti sur une solution intermédiaire (ArrayList) en attendant de faire une collection fortement typée ...

Merci à tous pour votre aide !