Discussion :

[nouknouk]

Salut,

j'ai un petit doute sur les possibilités des ListIterator.

Voilà mon besoin: j'ai une LinkedList contenant beaucoup d'instances d'Item et je dois souvent ajouter / enlever ces éléments dans ma liste de la façon efficace possible.

La première implémentation qui vient à l'esprit:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
 
public class Item {
    public Object unPeuDeContenu;
}
 
public class ListOwner {
    LinkedList<Item> list;
 
    public void addItem(item i) { list.add(i); }
    public void removeItem(item i) { list.remove(i); }
}

Mon problème est que les suppressions vont être trop lentes, car la fonction remove() parcourt de façon linéaire la liste.

Je me demande donc s'il ne serait pas possible de faire que chaque instance d'Item ait son propre itérateur comme donnée membre de la classe (pas besoin de me rappeler que 'designement parlant' c'est pas bôô, mais mes besoins en perfs sont critiques et l'utilisation d'une liste chaînée impérative).

D'où l'idée de la deuxième solution:

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 
public class Item {
    public Object unPeuDeContenu;
    public ListIterator<Item> it;
}
public class ListOwner {
    LinkedList<Item> list;
 
    public void addItem(Item item) {
        list.add(item);
        item.it = list.listIterator(list.size() - 1);
    }
    public void removeItem(Item item) {
        item.it.remove();
    }
}

Ici, la fonction LinkedList::remove() est remplacée par le remove de l'itérateur, ce qui me paraît bien plus rapide.

MAIS (ma question, enfin ) je me demande si cette approche est correcte. En effet, lorsque je vais faire ListIterator.remove() sur mon item 'x', cela va-t-il invalider les itérateurs de tous mes autres items présent dans cette liste ?

La doc étant souvent notre amie, j'ai fouiné et j'ai trouvé deux phrases dans la description de LinkedList:

D'une part:

Note that this implementation is not synchronized. If multiple threads access a list concurrently, and at least one of the threads modifies the list structurally, it must be synchronized externally

Mais également:

The iterators returned by the this class's iterator and listIterator methods are fail-fast: if the list is structurally modified at any time after the iterator is created, in any way except through the Iterator's own remove or add methods, the iterator will throw a ConcurrentModificationException. Thus, in the face of concurrent modification, the iterator fails quickly and cleanly, rather than risking arbitrary, non-deterministic behavior at an undetermined time in the future.

Donc j'ai bien compris que pour des accès concurrents (multi-threads) j'oublie (mais c'est pas mon cas). Mais cela fonctionnerait-il pour des accès séquentiels avec plusieurs instances de ListIterator pointant sur des élements d'une même liste ?

Intuitivement, je pense que la réponse est négative parce que j'imagine mal que lorsqu'un iterateur pointant sur l'item 'n' fait un remove(), il aille signifier à tous les itérateurs pointant sur 'n-1' et 'n+1' que (respectivement) leur next() et previous() ont changé. Mais peut-être auriez-vous une réponse définitive ?

Merci d'avance pour vos éclaircissements

[dinobogan]

Tu ne peux pas conserver une instance de l'itérateur pour ces remove. Comme tu le dis, il y aura une désynchronisation.
Laisse tomber la LinkedList. Il te faut une HashMap : le remove est en complexité constante. Pour conserver la séquentialité, utilise une LinkedHashMap. Le seul petit soucis est la génération de la clé pour chaque élément à ajouter.
Les items à supprimer, est-ce que ce sont les vraies instances des objets déjà contenus dans la liste, ou bien une copie représentant les données de l'item à supprimer ?

[nouknouk]

Merci pour ces infos.

Pour la LinkedHashMap, j'ai malheureusement peur que la recherch reste trop coûteuse et ce :
- etant donné le grand nombre d'items dans la collection (de l'ordre plusieurs milliers)
- de par la divertisité des items possibles, le hashcode sera relativement 'gros'. Entendre par là que je ne pourrai pas limiter ma clef à un Integer mais vraisemblablement à un type de clef plus lourd, qui pénalisera donc les comparaisons pour les lookup.

Pour les instances, je ne manipulerai effectivement que les mêmes instances que celles de la liste (en d'autres termes, pas de besoin d'equal() surchargé ici).

[woodwai]

Hello,

Pour les problèmes de synchronisation, il est préférable d'utiliser des Collections déjà synchronisée telle que celle du package java.util.concurent de Java (depuis la version 5): ConcurrentHashMap ou CopyOnWriteArrayList. Ou alors se pencher vers les collections synchronisées des jackarta commons-collections.

[nouknouk]

Hello,

Pour les problèmes de synchronisation, il est préférable d'utiliser des Collections déjà synchronisée telle que celle du package java.util.concurent de Java (depuis la version 5): ConcurrentHashMap ou CopyOnWriteArrayList. Ou alors se pencher vers les collections synchronisées des jackarta commons-collections.

Hem hem ... oui, mais la synchronisation inter-thread n'est absolument pas le problème soulevé ici...

... a moins que les 'synchronized iterators' gèrent également ce dont je parle ci-dessus. Je vais fouiner, mais même en admettant que la solution soit fonctionnelle, n'aurai-je pas une grosse perte de perfs à vouloir systématiquement locker ma liste (alors que c'est inutile puisque j'ai là qu'un seul thread) dès que j'y fais quelque chose ?

[dinobogan]

Pour les instances, je ne manipulerai effectivement que les mêmes instances que celles de la liste (en d'autres termes, pas de besoin d'equal() surchargé ici).

Ca c'est une excellente nouvelle
Je m'explique : il ne faut pas gérer une liste contenant des item, mais avoir des items qui simulent une liste. Tu aura une sorte de liste chaînée virtuelle, et tu conserves toujours le premier élément de la liste.
Chaque items possède une référence "previous" et "next" pour simuler une liste doublement chaînée. Et le début de ta liste est toujours dans root.
Lorsque tu veux faire un remove, puisque tu possèdes l'instance à supprimer, il te suffit de faire :

Code :

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

1
2
3
4
5
6
7
8
9
10
11
12
13
 
if( item.previous != null )
{
  item.previous.next = item.next;
}
if( item.next != null )
{
  item.next.previous = item.previous;
}
if( root == item )
{
  root = item.next;
}

Ton item est donc supprimé de ta "liste virtuel" immédiatement, sans recherche nécessaire.
Pour les recherches, tu as aussi un pseudo-iterator inclue dans tes items. Tu commences avec "root" et tu utilises la données membre "next". Ca fonctionne comme un Iterator de la LinkedList.
Pour faire l'ajout, c'est similaire au remove avec les previous et next des items encadrant celui à ajouter.

[elmor]

Pourquoi ne pas utiliser un java.util.TreeSet

Car toutes les operations add, remove, contains ont un cout de log(n).

Les données dans ta table sont toujours triées et la recherche est faite par dichotomie (pas d'utilisation de hashcode)

[nouknouk]

Ca c'est une excellente nouvelle
Je m'explique : il ne faut pas gérer une liste contenant des item, mais avoir des items qui simulent une liste.

Ah ... ben ... oui ... évidemment ...
Il est vrai qu'il me suffit en fait d'implémenter ma propre liste chaînée 'comme à l'école' plutôt que d'essayer de passer par les collections de Java.

Je me sens un peu con là.
Le pire c'est que j'étais parti dans la bonne direction en voulant embarquer des itérateurs dans mon item, mais je me suis arrêté en cours de route. Comme dirait Michel Blanc: "J'étais à deux doigts de conclure"
On va mettre ça sur l'heure à laquelle j'ai posté, histoire de se rassurer un peu

Pour la petite histoire: l'objet du bidule est de gérer des listes d'objets animés dans un moteur 2D isométrique pour une applet Java.
Le gros enjeu en termes de performances est d'être capable à chaque rendu de connaître le plus vite possible les objets à (ré)afficher et l'ordre dans lequel le faire. Les objets se déplaçant sur la 'carte', les ordres relatifs ont tendance à évoluer un peu tout le temps (d'où la nécessité d'avoir des add/remove/swap rapides et de pouvoir itérer seulement sur une sous-partie de la liste en fonction de la 'zone de la carte' actuellement affichée).

Pour ceux que ça intéresse, une démo du moteur en pré-alpha est dispo ici.

Merci beaucoup en tout cas