[Language]Structure la + rapide pour recherche et suppr + ancien

Bonjour,

Désolé pour le titre un peu SMS mais c'est dur de faire rentrer l'essentiel la haut :lol:

Je recherche la structure java qui me permet de detecter des doublons.

J'ai des clés (des Strings) que j'insère systématiquement (put) avec une date de timeout (un Long qui est en fait un System.currentMillis() ). Cette structure a une taille limite, quand elle est atteinte elle lâche les plus anciennes clés.

Des qu'une clé est en timeout, elle est effacée, c'est vérifié juste avant l'insertion réelle.

Pour la structure, j'utilise de jakarta common collections la classe LinkedMap.

Peut-on faire plus rapide, pour recherche et accès direct au plus ancien ? Je prends toute suggestion en compte :wink:

Merci d'avance

PS: mon questionnement fait surtout suite à cet article :
http://www.artima.com/weblogs/viewpost.jsp?thread=122295

avec le tableau :

Citation:

---

---------- TreeMap ----------
size put get iterate
10 748 168 100
100 506 264 76
1000 771 450 78
10000 2962 561 83
---------- HashMap ----------
size put get iterate
10 281 76 93
100 179 70 73
1000 267 102 72
10000 1305 265 97
------- LinkedHashMap -------
size put get iterate
10 354 100 72
100 273 89 50
1000 385 222 56
10000 2787 341 56
------ IdentityHashMap ------
size put get iterate
10 290 144 101
100 204 287 132
1000 508 336 77
10000 767 266 56
-------- WeakHashMap --------
size put get iterate
10 484 146 151
100 292 126 117
1000 411 136 152
10000 2165 138 555
--------- Hashtable ---------
size put get iterate
10 264 113 113
100 181 105 76
1000 260 201 80
10000 1245 134 77
*///:~

---

Et une structure liée de forme annulaire ? Un truc qui s'appellerait RingLinkedList ? Tu aurais deux pointeurs : nextput et nextremove qui pointent respectivement sur la prochaine case dans laquelle écrire (et on écrase celle qui était déjà là) et sur le prochain à effacer quand le timeout expire ?

Cela te permettrait d'avoir put et remove en complexité constante (à 1 ou 2 opérations près), et quasi imbattable.

Ca existe surement déjà, mais je ne connais pas trop les API non standard.

fait une recherche sur le forum java général j'ai déjà posté la question :
c'est avec des listes qu'il faut faire cela, puis des interfaces TreeSet... je m'en souviens plus exactement...

FFF -> attention ma structure est dynamique, j'ai par exemples 20 insertions/10ms, quelque chose comme ca, si le post dont tu parles est celui-là : http://www.developpez.net/forums/vie...light=doublon, ca ne convient pas du tout.

xavlours -> là par contre ca semble être une piste intéressante, je regarde :wink:


si vous avez des infos ou si ce que j'ai présenté n'est pas assez clair. Je le repète je ne cherche pas à supprimer les doublons d'un ensemble donné, je cherche à avoir une structure qui insère des clés et qui m'informe quand je cherche à en insérer une qui existe déjà, avec comme grosse contraire que ces clés ont des timeout et donc qu'elles sont à effacer à un moment donné, c'est facile à reconnaitre ce sont les dernières, mais aussi que si la structure déborde, même si le timeout n'a pas encore eu lieu, les clés les plus anciennes sont lâchées.

Citation:

---

Envoyé par guipom

je cherche à avoir une structure qui insère des clés et qui m'informe quand je cherche à en insérer une qui existe déjà,

---

C'est à dire ? Comment veux-tu être informé ?

Citation:

---

Envoyé par guipom

avec comme grosse contraire que ces clés ont des timeout et donc qu'elles sont à effacer à un moment donné,

---

Elle doivent être effacé au moment précis du timeout ou bien lors de l'ajout suivant ?

Sinon une simple LinkedList pourrait faire l'affaire en surchargeant la méthode add() afin de vérifier la taille de la liste et les timeouts...

a++

au départ je m'informais de ca sur exception, mais ca semble être lent comme méchanisme, donc j'ai fait un put qui retourne un booléen

On peut effacer la clé quand on veut, cependant il ne faut pas qu'elle soit encore présente au moment ou on en insère une nouvelle.

En gros si on fait un put, il faut etre sur qu'on est dans les bonnes conditions, qu'aucune clé a dépassée son timeout

Citation:

---

Envoyé par adiGuba

Citation:

---

Envoyé par guipom

je cherche à avoir une structure qui insère des clés et qui m'informe quand je cherche à en insérer une qui existe déjà,

---

Sinon une simple LinkedList pourrait faire l'affaire

---

oui et non

comment chercher efficacement dans cette liste qui pourrait contenir 10000 ou 20000 éléments, il faut l'associer avec une hashmap ou quelque chose dans le genre, et maintenir l'intégrité de la structure.

C'est peut etre tout simplement ce qu'il faut faire, l'avantage de la LinkedMap c'est que forcément les plus anciennes sont à la fin, et que j'ai rien à faire pour les obtenir, du coup le ménage me semble assez efficace, et j'ai aussi l'avantage des HashMap en recherche.

En effet avec une LinkedList, tu prends la dernière entrée, tu vérifies la date, tu supprimes dans la hashmap et la liste, tu prends la nouvelle dernière entrée, ...

avec la LinkedMap, tu prends la dernière, tu vérifies, tu supprimes, tu prends la dernière ....

Tu peux peut-être aussi utiliser LinkedHashSet qui conserve l'ordre d'ajout (via son iterator()) et qui permet d'empecher les doublons efficacement...

je me trompe peut etre, mais ç ressemble fortement à une pile FIFO, donc moi j'utiliserai une liste chainee avec un des structure contenant un pointeur 'dessus'

tu tiens en mémoire le bas(bottom) et le haut(top) de la pile grace à deux pointeurs

quand tu ajoute un élément, tu le fais le lien entre le pointeur dessus du top et la nouvelle structure a ajouter
et tu incremente la taille actuelle

si la taille actuel est la limite de la pile
alors tu fais bottom = bottom.dessus

voila

Une liste chainée represente un FIFO non ?

Pour la LinkedMap, qui a la propriété d'être une liste chainée
getValue(0) renvoie la plus ancienne
getValue(size) la plus récente

et bien sûr les autres méthodes propres aux HashMap

En fait le probleme qui se pose entre une LinkedList + HashMap ou une LinkedMap, c'est principalement que dans la première solution le coup du nettoyage n'est pas constant, et dans la deuxième le coup de l'insertion est supérieur à une simple Hashmap :(

Et un truc comme ca codé en 10 mn chrono (Mais pas compilé) ?
Je me suis appuyé sur les hypothèses suivantes :
- les objets à enlever sont forcément ceux qui ont été ajoutés il y a le plus longtemps
- on ajoute toujours à la fin
- pas thread-safe

La liste a une forme annulaire, et à partir du pointeur nextremove, est triée en dates croissantes de put jusqu'à l'élément précédant celui pointé par nextput.

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40

public class RingMap {   class Element { MonObject val; Element next; }   private Element nextput; private Element nextremove;   public RingMap(int capacity) { nextput = new Element(); nextremove = nextput; Element e = nextput; for(int i = 1; i < capacity; i++) { e.next = new Element(); e = e.next; } e.next = nextput; }   public void put(MonObject o) { removeOld(); nextput.val = o; nextput = nextput.next; if(nextput == nextremove.next && nextput.val != null) nextremove = nextremove.next; }   public void removeOld() { while(isRemovable(nextremove.val)) { nextremove.val = null; nextremove = nextremove.next; } }   private boolean isRemovable(MonObject o) { //vérifier que o n'est pas null et que son timeout est dépassé } }

---

Merci, je vais regarder ca en y ajoutant la fonctionnalité de détection de doublon


pour info avec une jakarta LinkedMap je fais :

150 insertions de clés / seconde, avec un cache de 30 secondes, ce qui fait 4000 clés.
Les clés sont des chaînes de nombres entre 0 et 1000000 pris aléatoirement.
20 threads injecteurs à des fréquences différentes.