Java: colección ordenada que permite duplicados, es eficiente desde el punto de vista de la memoria y proporciona inserción rápida + actualización

Question

Específicamente necesito una colección que utiliza un campo A para acceder y uno diferente (campo S) para ordenar pero una colección ordenada que acepta duplicados Ser suficiente.

A menudo llego a este punto en el que necesito exactamente esta colección y TreeMap no es una opción, ya que no permite duplicados. Entonces ahora es el momento de preguntar aquí. Hay varias soluciones como señaló en StackOverflow here y here - es decir, existen:

• PriorityQueue: actualización lenta (remove (Object) + añadir (Objeto)), y el boxeo de llaves primitivos
• Fibonacci montón: (?) de residuos de memoria
• TreeMap<Field_S, List<Value>>: problema para mí es la sobrecarga de la memoria de la lista, y el boxeo de llaves primitivos
• lista o matriz ordenada: el problema es la inserción y eliminación lenta -> ¿Debería implementar una lista ordenada segmentada?
• TreeMultimap de guayaba (docs): (?) La dependencia externa y probablemente ineficaz memoria

Cualquier persona con mejores sugerencias? ¿O debería implementar mi propia estructura de datos (¿cuál?)? También otras fuentes (en Java, código abierto, con pruebas unitarias y pequeñas deps) serían agradables.

---

actualización

Más detalles en mi caso de uso en el momento (a pesar de que estoy teniendo una solicitud similar en el último momento). Tengo una colección (con millones) de las referencias en el que necesito para poder

• al voto u obtener el elemento más pequeño en relación con el campo S
• y actualización de campo S con la ayuda de campo A
• valores idénticos del campo S puede suceder. el campo A es en realidad un entero que apunta a otra matriz
• la única dependencia que deseo es trove4j. Podría usar una colección diferente como la de mahout si fuera necesario. Pero no es guayaba, aunque es una buena lib, las colecciones no están ajustadas para ser eficientes en memoria (boxeo/unboxing).

Así que llora por un montón de Fibonacci, pero me temo que tiene demasiados gastos indirectos por elemento -> esa fue la razón por la que pensé en una forma más eficiente de la memoria "ordenados + matriz segmentada" solución.

Answer 1

Decidí rodar mi propia solución pero no la óptima solo una variante TreeMap. Mantendré esto actualizado si voy a ajustar esta colección con respecto a la memoria. La velocidad ya es mucho mejor que el intento anterior de PriorityQueue ya que necesitaba la colección.eliminar método (Objeto) (para actualizar una entrada):

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() + ")"; 
    } 
} 

Answer 2

¿Qué hay de la guayaba TreeMultiset? Lo que solicitó: una colección ordenada que acepta duplicados. Aunque no sé nada sobre su rendimiento.

Answer 3

Cuando necesite una colección ordenada, debe analizar sus necesidades cuidadosamente.
Si la mayoría de las operaciones es insertando y solo unas pocas son para buscar y luego usar una colección ordenada, es decirmantener los elementos ordenados en la colección constantemente, no sería una buena opción (debido a la sobrecarga de mantener los elementos ordenados en la inserción que sería la operación más común).
En este caso, sería mejor mantener una colección sin clasificar y hacer la clasificación solo cuando sea necesario. Es decir. antes de la búsqueda. Incluso podría usar un simple List y ordenarlo (usando Collections.sort, es decir, mergesort) cuando sea necesario. Pero lo recomiendo con precaución, ya que para que esto sea eficiente, la suposición es que trabajas con datos de gran tamaño. En datos realmente pequeños, incluso la búsqueda lineal es lo suficientemente buena.

Si la mayoría de las operaciones se buscando entonces se podría usar una colección ordenada que desde mi punto de vista hay estructuras de datos para elegir (algunos ya se mencionan) y se podía referencia para ver cuál se ajusta sus necesidades.

Answer 4

que tienen buena experiencia con TreeMultimap http://guava-libraries.googlecode.com/svn/tags/release05/javadoc/com/google/common/collect/TreeMultimap.html

Answer 5

Es necesario decidir si desea o no dependencias externas. No implementaría mi propia implementación para algo como esto.

Dicho esto, no nos ha dicho casi nada sobre para qué está utilizando esto y qué piensa hacer con él. Sin suficientes datos, solo podemos decirte algo: ¿realmente necesitas acceder a los elementos en orden aleatorio? ¿Qué tan grande espera que sea esta colección? Realmente no tenemos suficientes datos para elegir la estructura de datos correcta para sus necesidades.

Dicho esto, aquí hay algunas opciones que consideraría.

• ArrayListPriorityQueue o, dependiendo de si o no que realmente se necesita para apoyar remove(Object). ¿Vos si? ¿Eres seguro? (Incluso si necesita admitir remove(Object), elegiría esta opción si es probable que la colección se quede pequeña.)
• No es el TreeList al que se ha vinculado, sino el Apache Commons Collections TreeList. A pesar del nombre, en realidad no mantiene el orden ordenado, pero lo que hace es soportar O (log n) agregar, eliminar y obtener desde cualquier lugar en la lista. Al utilizar la búsqueda binaria, podría lograr O ((log n)^2) tiempo para agregar, eliminar o buscar según la parte ordenada de sus valores.
• El TreeList vinculado, o - si es como yo, y se preocupa por el contrato List - una Guava personalizada ListMultimap, obtenida con .

Si también se preocupa por el boxeo primitivo, o no puede tolerar las dependencias de terceros, no tendrá más remedio que escribir su propia estructura de datos. Solo adaptaría una de las implementaciones anteriores a tu tipo primitivo, pero esto será un dolor real.

Finalmente: me gustaría realmente me gusta escuchar su caso de uso. Guava no tiene soporte para este tipo de cosas porque no hemos tenido suficiente demanda o hemos visto un caso de uso para el cual una estructura de datos más sofisticada sea realmente apropiada.

Answer 6

Me gustaría ir con skiplist - más eficiente de la memoria que un árbol, permite duplicados, proporciona O (log n) para las inserciones y eliminaciones. Incluso puede implementar una lista de reproducción indexada, que le permitirá tener acceso indexado, algo que es difícil de conseguir con un árbol.