Implémentation de liste qui maintient l'ordre

Question

Existe-t-il un List implémentation en Java qui maintient l'ordre en fonction des éléments fournis Comparator?

Quelque chose qui peut être utilisé de la manière suivante :

Comparator<T> cmp = new MyComparator<T>();
List<T> l = new OrderedList<T>(cmp);
l.add(someT);

de sorte que someT est inséré de telle sorte que l'ordre dans la liste soit maintenu selon cmp

(Sur la suggestion de @andersoj, je complète ma question avec une demande supplémentaire)

Je veux également pouvoir parcourir la liste dans l'ordre trié sans supprimer les éléments, c'est-à-dire :

T min = Const.SMALLEST_T;
for (T e: l) {
  assertTrue(cmp.compare(min, e) >= 0);
  min = e;
}

devrait passer.

Toutes les suggestions sont les bienvenues (sauf me dire d'utiliser Collections.sort sur la liste complète non ordonnée), cependant, je préférerais quelque chose dans java.* ou éventuellement org.apache.* car il serait difficile d'introduire de nouvelles bibliothèques pour le moment.

Note:(MISE À JOUR4) J'ai réalisé que les implémentations de ce type de liste auraient des performances insuffisantes.Il existe deux approches générales :

1. Utiliser une structure liée (en quelque sorte) B-tree ou similaire
2. Utiliser le tableau et l'insertion (avec recherche binaire)

N°1.a un problème avec le cache CPU manque le n ° 2.a un problème avec le déplacement des éléments dans le tableau.

MISE À JOUR2 : TreeSet ne fonctionne pas car il utilise le comparateur fourni (MyComparator) pour vérifier l'égalité et, sur cette base, suppose que les éléments sont égaux et les exclut.J'ai besoin de ce comparateur uniquement pour l'ordre, pas pour le filtrage "unicité" (puisque les éléments par leur ordre naturel ne sont pas égaux)

MISE À JOUR3 : PriorityQueue ne fonctionne pas comme List (comme j'en ai besoin) car il n'y a aucun moyen de le parcourir dans l'ordre dans lequel il est "trié", pour obtenir les éléments dans l'ordre trié, vous devez les supprimer de la collection.

MISE À JOUR:

Question similaire :
Une bonne liste triée pour Java
Liste de tableaux triés en Java

Answer 1

Réponse à une nouvelle exigence.Je vois deux potentiels :

• Faire à quoi sert JavaDoc PriorityQueue dit:

  Cette classe et son itérateur implémentent toutes les méthodes facultatives des interfaces Collection et Iterator.L'itérateur fourni dans la méthode iterator() n'est pas garanti de parcourir les éléments de la file d'attente prioritaire dans un ordre particulier.Si vous avez besoin d'un parcours ordonné, envisagez d'utiliser Arrays.sort(pq.toArray()).

  Je pense que cela donnera les meilleures performances compte tenu de vos besoins.Si cela n'est pas acceptable, vous devrez mieux expliquer ce que vous essayez d'accomplir.

• Construire un Liste qui se trie simplement lors de l'ajout de nouveaux éléments.C'est une vraie douleur...si vous avez utilisé une structure liée, vous pouvez effectuer un tri par insertion efficace, mais la localité est mauvaise.Si vous avez utilisé une structure basée sur un tableau, le tri par insertion est pénible mais le parcours est meilleur.Si les itérations/traversées sont peu fréquentes, vous pouvez conserver le contenu de la liste non trié et le trier uniquement à la demande.

• Pensez à utiliser un File d'attente de priorité comme je l'ai suggéré, et si vous avez besoin d'itérer dans l'ordre, écrivez un itérateur wrapper :

  class PqIter implements Iterator<T>
  {
     final PriorityQueue<T> pq;
     public PqIter(PriorityQueue <T> source)
     {
       pq = new PriorityQueue(source); 
     }
  
     @Override
     public boolean hasNext()
     {
       return pq.peek() != null
     }
  
     @Override
     public T next()
     { return pq.poll(); }
  
     @Override
     public void remove()
     { throw new UnsupportedOperationException(""); }
  }
  

• Utilisez des goyaves TreeMultiSet.J'ai testé le code suivant avec Integer et cela semble faire la bonne chose.

  import com.google.common.collect.TreeMultiset;
  
  public class TreeMultiSetTest { 
    public static void main(String[] args) {
      TreeMultiset<Integer> ts = TreeMultiset.create();
      ts.add(1);  ts.add(0); ts.add(2);
      ts.add(-1); ts.add(5); ts.add(2);
  
      for (Integer i : ts) {
        System.out.println(i);
      } 
    } 
  }
  

Ce qui suit répond au problème d'unicité/filtrage que vous rencontriez lors de l'utilisation d'un SortedSet.Je vois que vous voulez aussi un itérateur, donc cela ne fonctionnera pas.

Si ce que vous voulez vraiment, c'est un ordre en forme de liste chose, vous pouvez utiliser un PriorityQueue.

Comparator<T> cmp = new MyComparator<T>();
PriorityQueue<T> pq = new PriorityQueue<T>(cmp);
pq.add(someT);

Prenez note de ce que dit la documentation de l'API sur les propriétés temporelles de diverses opérations :

Note de mise en œuvre :cette implémentation fournit O(log(n)) temps pour les méthodes d'enqueing et de dequeing (offer, poll, remove() et add); linéaire le temps pour le remove(Object) et contains(Object) méthodes;et constante temps pour les méthodes de récupération (peek, element, et size).

Vous devez également savoir que les itérateurs produits par PriorityQueue ne vous comportez pas comme on pourrait s’y attendre :

Le Iterator fourni dans la méthode iterator() n'est pas garanti de parcourir les éléments de la file d'attente prioritaire dans un ordre particulier.Si vous avez besoin d'un parcours ordonné, envisagez d'utiliser Arrays.sort(pq.toArray()).

Je viens de remarquer que Guava fournit un MinMaxPriorityQueue.Cette implémentation est basée sur un tableau, plutôt que sur la forme liée fournie dans le JDK. PriorityQueue, et a donc probablement un comportement de synchronisation différent.Si vous faites quelque chose de sensible aux performances, vous souhaiterez peut-être y jeter un œil.Bien que les notes donnent des temps big-O légèrement différents (linéaires et logarithmiques), tous ces temps doivent également être délimités, ce qui peut être utile.

Il n'y a pas de List implémentation en soi qui maintient l'ordre, mais ce que vous recherchez probablement, ce sont des implémentations de SortedSet.UN TreeSet est le plus courant.L'autre implémentation, un ConcurrentSkipListSet est destiné à des usages plus spécifiques.Notez qu'un SortedSet fournit un classement, mais n'autorise pas les entrées en double, comme le fait un List.

Réfs :

• Article de blog PriorityQueue l'itérateur n'est pas ordonné
• Alors question sur Itérateur ordonné PQ

Answer 2

Vous devriez probablement utiliser un Ensemble d'arbres:

Les éléments sont classés en utilisant leur ordre naturel ou par un comparateur fourni au moment de la création définie, en fonction du constructeur utilisé.

Exemple:

Comparator<T> cmp = new MyComparator<T>();
TreeSet<T> t = new TreeSet<T>(cmp);
l.add(someT);

Notez qu'il s'agit d'un ensemble, donc aucune entrée en double n'est autorisée.Cela peut fonctionner ou non pour votre cas d'utilisation spécifique.

Answer 3

J'ai un problème similaire et je pense utiliser un TreeSet.Pour éviter d'exclure des éléments "égaux", je modifierai le comparateur donc au lieu de renvoyer 0, il renverra un nombre aléatoire entre (-1,1) ou il renverra toujours 1.

Si vous n'avez aucun contrôle sur le comparateur ou si vous l'utilisez pour autre chose que l'insertion, cette solution ne fonctionnera pas pour vous.