Java: La collection triée qui permet les doublons, est efficace en mémoire et fournit une insertion rapide et une mise à jour rapide

Plus précisément j'ai besoin d'une collection qui utilise un champ pour Un accès et un autre (champ S) pour le tri, mais une collection triée qui accepte le double serait suffisant.

Je viens souvent à ce moment-là que j'ai besoin exactement cette collection et TreeMap est pas une option, car elle ne permet pas de doublons. Alors maintenant, il est temps de se demander ici. Il existe plusieurs solutions comme l'a souligné sur stackoverflow ici et ici - à savoir il y a:

  • PriorityQueue: mise à jour lente (remove(Object) + ajouter(Objet)), et de la boxe de la primitive clés
  • Tas de Fibonacci: de la mémoire des déchets (?)
  • TreeMap<Field_S, List<Value>>: problème pour moi, c'est la surcharge de la mémoire de la liste, et de la boxe de la primitive clés
  • triés liste ou d'une matrice: le problème est la lenteur insérer et à retirer -> dois-je mettre en œuvre un segmenté liste triée?
  • TreeMultimap de goyave (docs): dépendance externe et probablement de la mémoire inefficace (?)

Quelqu'un avec de meilleures suggestions? Ou devrais-je rôle de ma propre triés discbased (laquelle?)? Aussi d'autres sources (en Java, open source, avec des tests unitaires et de petites deps), ce serait bien.

Mise à jour

Plus de détails sur mon cas d'utilisation à l'instant (même si je vais avoir une demande similaire à la dernière fois). J'ai une collection (avec des millions) de références où je veux être en mesure

  • d'un sondage ou d'obtenir le plus petit élément de S
  • et mise à jour de champ à l'aide d'Un champ
  • des valeurs identiques de terrain peuvent se produire. champ est en fait un entier pointant vers un autre tableau
  • la seule dépendance je veux, c'est trove4j. Je pourrais utiliser un autre comme le mahout collections, si c'est nécessaire. Mais pas de goyave en tant que bien que d'une belle lib, les collections ne sont pas à l'écoute pour être efficace en terme de mémoire (boxing/unboxing).

Donc tous les cris d'un tas de fibonacci, mais j'ai peur qu'il a trop de frais généraux par element -> c'est la raison j'ai pensé à un plus efficace en terme de mémoire "triés+sectorielle tableau" solution.

source d'informationauteur Karussell

  1. 3

    Lorsque vous avez besoin d'une collection triée, vous devez analyser vos besoins avec soin.

    Si la majorité des opérations est insertion et seuls quelques-uns sont à la recherche puis à l'aide d'une collecte sélective qui consiste à maintenir les éléments triés dans la collection constamment, ne serait pas une bonne option (en raison de la surcharge de garder les éléments triés sur insert qui serait l'opération la plus courante).

    Dans ce cas, il serait préférable de garder un non triés de collecte et de faire le tri uniquement lorsque cela est nécessaire. I. e. avant la recherche. Vous pourriez même utiliser un simple List et de tri (à l'aide de Collections.sort c'est à dire mergesort) en cas de besoin. Mais je recommande cette avec prudence, car pour que ce soit efficace, l'hypothèse est que vous travaillez sur de gros volumes de données. Dans les très petites des données même à la recherche linéaire est assez bon.

    Si la majorité des opérations est recherche alors vous pouvez utiliser un classement qui, de mon point de vue il y a des structures de données à choisir (certains on déjà dit) et vous pourriez benchmark pour voir celui qui correspond le votre besoins.

  2. 2

    Ce sujet goyave TreeMultiset? Ce que vous avez demandé: une collection triée qui accepte les doublons. Ne sais rien à propos de ses performances.

  3. 1

    Vous devez décider si vous voulez dépendances externes ou non. Je ne voudrais pas rouler ma propre mise en œuvre pour quelque chose comme ça.

    Cela dit, vous avez dit que nous presque rien au sujet de ce que vous êtes en utilisant ce pour, et de ce que vous comptez faire avec elle. Sans suffisamment de données, il ya seulement tellement que nous pouvons vous dire -- est-ce que vous avez réellement besoin d'avoir accès aux éléments dans un ordre aléatoire? Comment les grandes attendez-vous de cette collection? Nous n'avons vraiment pas assez de données pour choisir la droite structure de données pour répondre à vos besoins.

    Cela dit, voici quelques options de je considère.

    • ArrayList ou PriorityQueueselon si oui ou non vous avez réellement besoin de soutien remove(Object). Faites-vous? Êtes-vous sûr? (Même si vous avez besoin de soutien remove(Object)je choisirais cette option si la collection est susceptible de rester petit).
    • Pas le TreeList vous lié, mais au lieu de la Apache Commons Collections liste arborescente. Malgré le nom, il n'a pas fait de maintenir l'ordre, mais ce qu'il fait est de soutenir O(log n) d'ajouter, de supprimer et d'obtenir à partir de n'importe où dans la liste. À l'aide de binaires de recherche, vous pourriez potentiellement obtenir O((log n)^2) pour ajouter, de supprimer ou de recherche selon la triés partie de vos valeurs.
    • La TreeList vous êtes associé ou, si vous êtes comme moi, et qui se soucient de la List contrat -- une coutume de Goyave ListMultimapobtenu avec Multimaps.newListMultimap(new TreeMap<K, Collection<V>>, new Supplier<List<V>>() { public List<V> get() { return new ArrayList<V>(); }}).

    Si vous aussi vous souciez primitive de boxe, ou ne peuvent pas tolérer tiers des dépendances, vous allez avoir pas d'autre choix que d'écrire votre propre structure de données. Je venais tout juste de s'adapter l'un des implémentations ci-dessus pour votre type primitif, mais cela va être une douleur royale.

    Enfin: j'avais vraiment à l'écoute de vos cas d'utilisation. Goyave n'ont pas de support pour ce genre de choses parce que nous n'avons pas eu assez de demande, ou vu un cas d'utilisation pour une structure de données sophistiquée vraiment approprié.

  4. 1

    J'ai décidé de rouler mes propres mais pas la solution optimale, juste un TreeMap variante. Je vais garder cette mise à jour si je vais affiner cette collection concernant la mémoire. La vitesse est déjà beaucoup mieux que la précédente PriorityQueue tentative que j'avais besoin de la collection.remove(Object) méthode (pour la mise à jour d'une entrée):

    package com.graphhopper.coll;
import gnu.trove.iterator.TIntIterator;
import gnu.trove.set.hash.TIntHashSet;
import java.util.Map.Entry;
import java.util.TreeMap;
/**
* A priority queue implemented by a treemap to allow fast key update. Or should we use a standard
* b-tree?
*/
public class MySortedCollection {
private int size;
private int slidingMeanValue = 20;
private TreeMap<Integer, TIntHashSet> map;
public MySortedCollection(int size) {
map = new TreeMap<Integer, TIntHashSet>();
}
void remove(int key, int value) {
TIntHashSet set = map.get(value);
if (set == null || !set.remove(key))
throw new IllegalStateException("cannot remove key " + key + " with value " + value
+ " - did you insert " + key + "," + value + " before?");
size--;
if (set.isEmpty())
map.remove(value);
}
public void update(int key, int oldValue, int value) {
remove(key, oldValue);
insert(key, value);
}
public void insert(int key, int value) {
TIntHashSet set = map.get(value);
if (set == null)
map.put(value, set = new TIntHashSet(slidingMeanValue));
//       else
//           slidingMeanValue = Math.max(5, (slidingMeanValue + set.size()) /2);
if (!set.add(key))
throw new IllegalStateException("use update if you want to update " + key);
size++;
}
public int peekValue() {
if (size == 0)
throw new IllegalStateException("collection is already empty!?");
Entry<Integer, TIntHashSet> e = map.firstEntry();
if (e.getValue().isEmpty())
throw new IllegalStateException("internal set is already empty!?");
return map.firstEntry().getKey();
}
public int peekKey() {
if (size == 0)
throw new IllegalStateException("collection is already empty!?");
TIntHashSet set = map.firstEntry().getValue();
if (set.isEmpty())
throw new IllegalStateException("internal set is already empty!?");
return set.iterator().next();
}
public int pollKey() {
size--;
if (size < 0)
throw new IllegalStateException("collection is already empty!?");
Entry<Integer, TIntHashSet> e = map.firstEntry();
TIntHashSet set = e.getValue();
TIntIterator iter = set.iterator();
if (set.isEmpty())
throw new IllegalStateException("internal set is already empty!?");
int val = iter.next();
iter.remove();
if (set.isEmpty())
map.remove(e.getKey());
return val;
}
public int size() {
return size;
}
public boolean isEmpty() {
return size == 0;
}
public int getSlidingMeanValue() {
return slidingMeanValue;
}
@Override
public String toString() {
return "size " + size + " min=(" + peekKey() + "=>" + peekValue() + ")";
}
}
  5. 1

    Je voudrais aller avec skiplist - mémoire plus efficace qu'un arbre, permet de doublons, donne O(logn) pour les insertions et les suppressions. Vous pouvez même mettre en place un indexée skiplist, il vous permettra d'avoir un accès indexé, quelque chose qui est difficile à obtenir avec un arbre.