pb de tri de liste dynamique

bonjour,

Je voudrais créer une classe qui possède une methode add pour ajouter un élément à sa propre liste dynamique. Chaque élément est issu d'une même classe qui possède plusieurs attributs.

Je voudrais que lorsque j'ajoute un élément via la methode add, que celui-ci soit automatiquement trié par orde croissant en fonction de l'un de ses attributs (un int => nous appellerons cet attribut myAttr).
=> je veux le trier pour accélérer mes méthodes de recherche d'élément : je veux récupérer le plus rapidement possible le premier élément de la liste où myAttr est inférieur à une valeur donnée.

Ne connaissant pas trop tous les types de liste sous Java, pouvez-vous me conseillez quelle est la meilleure méthode à utiliser ?
=> a priori il semblerait que les TreeMap soit bien adapté à ce genre d'application...

Je peux comprendre ta demande de deux façons :
- tu souhaites stocker les éléments dans une liste (concrètement, une collection qui implémente java.util.List<E>). Les éléments doivent être ordonnés suivant un critère que tu définis. Il est possible de définir la manière d'ordonner les éléments en leur faisant implémenter java.lang.Comparable<E> et en triant la liste grâce à java.util.Collections.sort().
- tu souhaites stocker les éléments dans une collection non ordonnée qui te permet de retrouver rapidement un élément à partir d'une clé. Si tu utilises une collection qui implément java.util.Map<K,V>, ça devrait faire ce que tu souhaites.

Si ces conseils ne te suffisent pas, essaie de préciser ta demande.

Bon courage !

En gros mes éléments représentent des zones mémoires tampons désignées par une plage d'adresse

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15

public class MemoryZoneStruct {   ByteArrayOutputStream bos = new ByteArrayOutputStream(); int currentAddr;   public void write(int val){...} // écrit dans bos public void jumpTo(int addr){...} // saut d'adresse (remplit bos avec une valeur "vide" jusqu'a arriver a l'adresse désirée) => le saut ne peut être que positif   ... ...   // permet de savoir sur quelle plage d'adresse on travaille public int getFirstAddr(){...} public int getSize(){...} }

---

Je voudrais donc créer une liste de plusieurs de ces éléments

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

class ClassList{   List myList = new List()l; int myAddr = 0;   public void add(MemoryZoneStruct mz){ list.add(mz); }   public void write(int val){ // recherche de l'élément correspondant à l'adresse MemoryZoneStruct mz = .... ????? ;   mz.write(val) myAddr++; }   // saut d'adresse public void jumpTo(int addr){ myAddr = addr;   // recherche de l'élément correspondant à l'adresse MemoryZoneStruct mz = .... ????? ;   mz.jumpTo(myAddr); }   }

---

=> le but étant que mes méthodes .write() et .jumpTo() soient éxécutées le plus rapidement possible.

Le but de mon application est d'écrire des valeurs dans une zone mémoire virtuelle dont je défini différentes zones qui ne se suivent pas forcément => peut-être que je suis parti sans une mauvaise direction sur l'architecture de mon projet...
Donc j'ai deux méthodes pour le remplissage de ma zone mémoire
- .write(int val) : écrit à l'emplacement mémoire sélectionné (puis pointe automatiquement sur l'élément suivant)
- .jumpTo(int addr) : déplace le pointeur d'adresse

Le plus simple dans ce cas est d'utiliser une Hashtable<int, MemoryZoneStruct> qui associera à une position mémoire (l'entier) un objet MemoryZoneStruct :

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

class ClassList{   Hashtable<int,MemoryZoneStruct> myList = new Hashtable<int,MemoryZoneStruct>(); int myAddr = 0;   public void add(MemoryZoneStruct mz){ list.put(mz.getFirstAddr(), mz); // Range mz en l'associant à une adresse pour le retrouver plus tard. }   public void write(int val){ // recherche de l'élément correspondant à l'adresse MemoryZoneStruct mz = myList.get(val);   mz.write(val) myAddr++; }   // saut d'adresse public void jumpTo(int addr){ myAddr = addr;   // recherche de l'élément correspondant à l'adresse MemoryZoneStruct mz = myList.get(val);   mz.jumpTo(myAddr); }   }

---

merci pour ta réponse

mais il y a un petit problème me semble t-il :

la zone d'adresse est défini avec deux paramètres

Code:

---

1 2	public int getFirstAddr(){...} public int getSize(){...}

---

Donc il n'y pas une seule valeur d'adresse à gérer mais plusieurs pour un élément donc ceci ne fonctionnera pas me semble t-il :

Code:

---

myList.get(val);

---

.

Ensuite il me semblait judicieux de trier par ordre croissante la liste car ça permettrait d'éviter de reparcourir complétement la liste à chaque fois => je pensais sauvegarder à chaque fois la position du dernier élément lu et de repartir de celui-ci lors de la prochaine recherche : mais je ne vois pas comment faire pour parcourir une liste en repartant d'un élément donné...

Remarque : Lors de la phase de remplissage de mes buffers, j'écris toujours en partant de l'adresse la plus petite et les sauts d'adresse sont toujours positifs.

Je croyais avoir compris que tu souhaitais retrouver rapidement un MemoryZoneStruct à partir de son adresse de début. Si ce n'est pas le cas, l'utilisation d'une map ne convient pas.

Tu évoques ensuite la possibilité d'ordonner par adresses de début croissantes les MemoryZoneStruct. L'idée est bonne mais elle n'a aucun sens avec une map, encore une fois.
Peux-tu décrire clairement la requête que tu souhaites que la méthode write effectue ? Si tu veux retourner le MemoryZoneStruct qui "contient" l'adresse donnée, alors range tes MemoryZoneStruct dans une simple liste ordonnée. Implémente Comparator<E> sur MemoryZoneStruct et utilise Collections.sort.

Citation:

---

Envoyé par cdefranoux

Si tu veux retourner le MemoryZoneStruct qui "contient" l'adresse donnée, alors range tes MemoryZoneStruct dans une simple liste ordonnée. Implémente Comparator<E> sur MemoryZoneStruct et utilise Collections.sort.

---

Oui c'est sur quoi je suis finalement parti. Par contre au moment d'une saut d'adresse pour rechercher la struture suivante, je fais comme ça :

Code:

---

1 2 3 4 5 6 7 8

for(MemoryZoneStruct mz : myList){ if (mz.getFirstAddr() <= addr){ if (mz.getFirstAddr() + mz.getSize() > addr){ mz_current = mz; // sauvegarde de l'element selectionné break; } } }

---

=> le problème est qu'a chaque fois je re-parcours toute la liste : vu que les zones sont triées par ordre croissant et que les sauts d'adresse sont toujours positifs, ne puis-je pas parcourir ma liste en repartant de l'élément mz_current pour gagner en rapidité ?




Entre :

Code:

---

1 2 3

mz_index++; mz_current= myList.get(mz_index); // ça parcours la liste chainée depuis le début élément par élément ?

---

Et

Code:

---

1 2 3 4 5 6 7 8 9 10 11 12

mz_index++;   int i =0; for(MemoryZoneStruct mz : myList){     if (i == mz_index){ mz_current = mz; // sauvegarde de l'element selectionné break; } i++; }

---

Est-ce qu'il y a réellement une grosse différence de perf où les deux codes sont similaires ?

Je n'ai pas tout compris à ton besoin.

Toutefois si tu as besoin d'un ensemble dont les élément sont ordonnés, tu peux aller voir l'interface SortedSet, elle est implémentée par la classe TreeSet (si c'est une Map qui doit être ordonnée, tu peux aller voir l'interface SortedMap implémenté par la classe TreeMap).

Après il faut fournir un comparator ou il faut que tes classes à trier implémente l'interface comparable.

Si tel est le cas, les données seront triés après chaque ajout en s'appuyant sur la méthode de comparaison que tu auras implémenté.

Bon courage

Arnaud

L'utilisation de SortedSet ou SortedMap me paraît exagérée pour le besoin.

Pour reprendre les questions relatives aux performances posées par boboss123, il n'y a aucune différence de performance entre les deux solutions proposées si la liste est une LinkedList puisque comme tu l'as écrit dans le commentaire, accéder au ième élement demande de parcourir la liste depuis le début. Si c'est une ArrayList, l'accès par index est immédiat et donc plus rapide que la solution avec un for qui saute les i premiers éléments.

Toutefois, la différence de performance ne sera pas visible si ta liste ne contient pas beaucoup d'éléments et/ou si ces recherches ne sont pas fréquentes. Malgré cela, l'usage d'une ArrayList est plus appropriée ici.

ok merci pour vos information.

Donc la ArrayList me semble effectivement le plus judicieux