Estoy desconcertado que no puedo encontrar una respuesta rápida a esta. Estoy esencialmente buscando un discbased en Java que implementa la java.util.List de la interfaz, sino que almacena sus miembros ordenados. Yo sé que usted puede utilizar un normal ArrayList y uso Collections.sort() en ella, pero tengo un escenario donde estoy ocasionalmente agregar y, a menudo, la recuperación de los miembros de mi lista y no quiero tener que ordenar cada vez que puedo recuperar un miembro en caso de que se ha añadido uno nuevo. Puede alguien me apunte hacia una cosa que existe en el JDK o incluso la 3ª parte de las bibliotecas?

EDITAR: El discbased necesidad de preservar los duplicados.

RESPUESTA del RESUMEN: he encontrado todo esto muy interesante y he aprendido mucho. Aioobe en particular, merece mención por su perseverancia en el intento de lograr mis requisitos anteriores (principalmente de un criterio de java.util.Lista la aplicación que admite duplicados). He aceptado su respuesta como el más preciso de lo que pedí y la mayoría de la reflexión sobre las implicaciones de lo que yo estaba buscando, incluso si lo que te pedí no era exactamente lo que necesitaba.

El problema con lo que me pidió que se encuentra en la Lista de la interfaz de sí mismo y el concepto de métodos opcionales en una interfaz. Para citar el javadoc:

El usuario de esta interfaz tiene un control preciso de donde en la lista de cada elemento se inserta.

Insertar en una lista ordenada no tener un control preciso sobre el punto de inserción. Entonces, usted tiene que pensar cómo va a manejar algunos de los métodos. Tomar add por ejemplo:

public boolean add(Object o)

 Appends the specified element to the end of this list (optional operation).

Ahora se ha quedado en la incómoda situación de
1) Romper el contrato y la aplicación de una versión ordenada de agregar
2) Dejar add agregar un elemento al final de la lista, rompiendo su orden
3) Dejando add (como opcional) al lanzar un UnsupportedOperationException y la aplicación de otro método que agrega elementos ordenados.

La opción 3 es probablemente el mejor, pero me resulta desagradable tener un complemento método no se puede usar y la otra sortedAdd método que no está en la interfaz.

Otras soluciones relacionadas (en ningún orden en particular):

  • java.util.PriorityQueue que es probablemente más cercano a lo que yo necesitaba, que lo que me pidió. Una cola no es la más precisa definición de una colección de objetos en mi caso, pero funcionalmente es todo lo que se necesita.
  • net.sourceforge.nite.util.SortedList. Sin embargo, esta implementación se rompe el contrato de la interfaz de Lista por la aplicación de la clasificación de la add(Object obj) método y curiosamente tiene un efecto método para add(int index, Object obj). El consenso General sugiere throw new UnsupportedOperationException() podría ser una mejor opción en este escenario.
  • La guayaba es TreeMultiSet Un conjunto de aplicación que admite duplicados
  • ca.odell.glazedlists.SortedList Esta clase viene con la advertencia de que en su javadoc: Warning: This class breaks the contract required by List
  • Si usted insertar de vez en cuando y leer con frecuencia ¿por qué no acaba de ordenar que durante la inserción?
InformationsquelleAutor Chris Knight | 2010-10-27

11 Comentarios

  1. 62

    Minimalista Solución

    Aquí es un «mínimo» de la solución.

    class SortedArrayList<T> extends ArrayList<T> {
    
        @SuppressWarnings("unchecked")
        public void insertSorted(T value) {
            add(value);
            Comparable<T> cmp = (Comparable<T>) value;
            for (int i = size()-1; i > 0 && cmp.compareTo(get(i-1)) < 0; i--)
                Collections.swap(this, i, i-1);
        }
    }

    La inserción se ejecuta en el tiempo lineal, sino que sería el que obtendría el uso de un ArrayList de todos modos (todos los elementos a la derecha del elemento insertado tendría que ser cambiado de una manera o de otra).

    Insertar algo no comparable de los resultados en una ClassCastException. (Este es el enfoque adoptado por PriorityQueue así: Una cola de prioridad depender natural de pedidos también no permite la inserción de los no-objetos comparables (hacerlo puede resultar en una ClassCastException).)

    Primordial List.add

    Nota que reemplazar Lista.agregar (o Lista.addAll para que la materia) para insertar elementos en función de un criterio de la moda sería un violación directa de la especificación de interfaz de. Lo que podría hacer, es invalidar este método para deshacerse de un UnsupportedOperationException.

    De la documentación de List.add:

    boolean add(E e)

        Agrega el elemento especificado para el final de esta lista (opcional operación).

    Mismo razonamiento se aplica para ambas versiones de add, ambas versiones de addAll y set. (Todos los cuales son opcionales operaciones de acuerdo a la lista de la interfaz.)

    Algunas pruebas

    SortedArrayList<String> test = new SortedArrayList<String>();
    
    test.insertSorted("ddd");    System.out.println(test);
    test.insertSorted("aaa");    System.out.println(test);
    test.insertSorted("ccc");    System.out.println(test);
    test.insertSorted("bbb");    System.out.println(test);
    test.insertSorted("eee");    System.out.println(test);

    ….imprime:

    [ddd]
    [aaa, ddd]
    [aaa, ccc, ddd]
    [aaa, bbb, ccc, ddd]
    [aaa, bbb, ccc, ddd, eee]
    • Un buen comienzo, pero las llamadas a agregar, o addall habría que añadir los miembros seleccionados de la moda.
    • Sí. Nada pero añadiéndolos a la lista sería una violación directa de la Lista de la interfaz. Ver mi respuesta actualizada.
    • Buen punto. Pero no es compatible el funcionamiento de un método de interfaz de un código de olor? La manera adecuada podría ser la de no extender ArrayList pero implementar la Lista, pero incluso entonces, tal vez Lista simplemente no estaba destinado para este propósito. Desde el Javadoc de Lista: The user of this interface has precise control over where in the list each element is inserted que no es la mejor descripción para la inserción de elementos en función de un criterio de moda y usted todavía tiene que lidiar con la add(int index, Object obj) método de interfaz. Estas cuestiones probablemente explique por qué la Lista no ha sido implementada en función de un criterio de la moda.
    • Así, la operación es opcional por una razón. No me sorprendería si tengo un UnsupportedExceptionOperation al hacer .add en un SortedArrayList. Sí, el mismo razonamiento se aplica para ambas versiones de agregar, ambas versiones de addAll y conjunto. (Todos los cuales son opcionales operaciones de acuerdo a la lista de la interfaz.)
    • Ah, no me di cuenta de que eran opcionales operaciones. La cosa se complica… 😉
    • Jejeje, sí. Al principio estaba en contra de toda idea y upvoted la PriorityQueue-respuesta. Sin embargo, si uno simplemente agrega un insertSorted (y posiblemente no permitir add) creo que uno sería «correcto» en todos los aspectos, y aún así tener una List que tiene elementos ordenados 🙂
    • Como siempre con stackoverflow, aunque, no siempre es formalmente respuesta «correcta» que el OP quiere 🙂
    • Por supuesto, el problema con insertSorted() es que no se puede pasar alrededor de la estructura de datos como un List y agregar nuevos miembros. Pero tal vez eso es lo mejor de ambos mundos. Donde agregar elementos de trabajar con la aplicación concreta, y, a continuación, pasar alrededor de sólo lectura List interfaz para el resto del código.
    • Bueno, que no estaría a salvo de todos modos… dicen que le pasa a una función que hace list.add("x"); if (!list.get(list.size()-1).equals("x")) formatHarddrive();. Es seguro de acuerdo a las especificaciones, así que realmente no se puede culpar al método-escritor del accidente 😛
    • ¿Hay alguna razón usted no puede (o no debe) hacer class SortedArrayList<T extends Comparable<T>> extends ArrayList<T>? Que permitiría hacer valer el hecho de que sólo se puede poner en las cosas que son comparables a sí mismos, en lugar de forma implícita a través de un molde.
    • No en mi fragmento del ejemplo, pero en un ejemplo más completo que se desea incluir personalizado órdenes a través de un Comparador.
    • Esta es una gran respuesta. Yo sugiero utilizar la composición a través de herencia (en.wikipedia.org/wiki/Composition_over_inheritance). Yo a mi la aplicación me defina una clase SortedList<T> implementa Iterable<T> que implementa todos los métodos necesito delegando a un objeto de la Lista (que no expuestos). De esa manera usted no se quede en cualquiera de los problemas mencionados en otros comentarios.
    • buena sugerencia, pero no se aplica para esta pregunta que específicamente dice que «yo soy esencialmente buscando un discbased en Java que implementa la java.util.List interface«.
    • Puede utilizar la composición e implementar la interfaz de Lista
    • a la derecha. Que sería un poco más «seguro», supongo. Uno tiene que preguntar «Es una SortedList un ArrayList?» y que, formalmente, creo que la respuesta es «no». Por lo menos es algo de usar y tirar código, la composición es probablemente el camino a seguir aquí.
    • Tal vez no debería ser llamado SortedList, ya que incumple la Lista contrato. AFAIK no hay una definición de interfaz en Java que se ajusta a una lista ordenada estructura de datos. Las listas deben dar un control preciso sobre donde cada elemento se inserta mientras que los Mapas no se permiten duplicados. Tal vez debería ser llamado SortedCollection? Como consecuencia de la delegación/composición tiene sentido, incluso si eso significa que más de la escritura de código.
    • formalmente hablando no cumplir con la Lista de la interfaz ya que todos los métodos add son opcionales.
    • estás en lo correcto. Cuando yo uso una lista en mi código (código de en contra de la interfaz) espero ser capaz de utilizar los métodos add, aunque. Si tengo una Lista de implementación que impone restricciones a los métodos add me gustaría utilizar el hormigón de la clase o de otra interfaz que no tiene el complemento de los métodos. Por lo tanto, le sugerimos utilizar la composición con una clase concreta de que los delegados a una Lista o definir una nueva interfaz de SortedList y el código en contra de esa lista. Soy consciente de que el OP quería una Lista, pero tal vez ese enfoque es erróneo…
    • tenga en cuenta que la API de métodos tales como la Arrays.asList y Collections.unmodifiableList regreso a las listas que no admite add. Así que, aunque puede parecer poco natural para usted tener un List que no admite agregar, no es raro.
    • Una vez más que correcta. Sin embargo, yo no uso esa lista todo mi código, pero sólo a nivel local donde yo sé es inmodificable o lo que sea restricciones. Yo no creo que sea un buen diseño a código en contra de una interfaz que puede ser o no el apoyo de ciertos métodos (sé que es común, pero eso no la hace buena). Alternativamente, utilizar la Lista como Iterable<T> o la Colección de<T>.

  2. 11

    Uso java.util.PriorityQueue.

    • que no es una Lista, es decir, sin acceso aleatorio.
    • Es una cola de prioridad basada en un montón de no implementar la Lista.
    • Por supuesto, con una lista que mantiene el orden de los índices cambian todo el tiempo, de modo de acceso aleatorio, probablemente no es necesario de todos modos.
    • Ninguna de acceso aleatorio, aunque.
    • Hmm, esto podría funcionar para lo que necesito (como no necesito de acceso aleatorio). Gracias!
    • +1 en mi humilde opinión la mejor solución teniendo en cuenta, incluso si no implementa la interfaz de Lista.
    • -1 como no implementar la Lista, que fue uno de los OP requisitos.
    • tenga en cuenta que la respuesta exacta no es siempre la mejor respuesta, o la respuesta que el OP es en realidad después.
    • cola de prioridad no conceder ordenada en la iteración.
    • marcorossi tiene el quid de la cuestión es, PriorityQueue se ser lo que el OP se busca si su iterador devuelve los elementos en el natural orden de la cola, pero el javadoc específicamente dice que no.

  3. 6

    Echar un vistazo a SortedList

    Esta clase implementa una lista ordenada. Se construye con un comparador que se pueden comparar dos objetos y clasificar objetos en consecuencia. Cuando se agrega un objeto a la lista, se inserta en el lugar correcto. Objetos que son iguales de acuerdo con el comparador, será en la lista en el orden en que se agregaron a esta lista. Agregar sólo los objetos que el comparador se puede comparar.


    Cuando la lista ya contiene objetos que son iguales de acuerdo con el comparador, el nuevo objeto se inserta inmediatamente después de estos otros objetos.

    • Que se ve bien, pero también se ve buggy: no hay ningún reemplazo de la versión de addAll, por lo que la lista serán seleccionados después de llamar a las personas.
    • Y el método add «no tiene ningún efecto». Sino lanzar un UnsupportedOperationException si no se puede utilizar.
    • Anderson @Thilo , de acuerdo con ambos.
    • Muy interesante, pero tengo un poco de cuidado de alguien en el futuro el uso de addAll() y el pensamiento de que todos los elementos de un ordenan de la moda. De acuerdo con el UnsupportedOperationException así.
    • ¿Cuál es el tiempo de la complejidad de adición a esta lista?
  4. 6

    Puede intentar La guayaba es TreeMultiSet.

     Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
     System.out.println(ms);
    • +1. Esta es una gran biblioteca. Conjunto múltiple es A collection that supports order-independent equality, like Set, but may have duplicate elements
  5. 4

    Listas suelen preservar el orden en que se agregan elementos. Usted definitivamente necesita un lista, o de un criterio de conjunto (por ejemplo,TreeSet<E>) ser bueno para usted? Básicamente, usted necesita a la necesidad de conservar los duplicados?

    • Gracias Jon, pero necesito conservar los duplicados
  6. 4

    Aioobe enfoque es el camino a seguir. Me gustaría sugerir la siguiente mejora con respecto a su solución, aunque.

    class SortedList<T> extends ArrayList<T> {
    
        public void insertSorted(T value) {
            int insertPoint = insertPoint(value);
            add(insertPoint, value);
        }
    
        /**
         * @return The insert point for a new value. If the value is found the insert point can be any
         * of the possible positions that keeps the collection sorted (.33 or 3.3 or 33.).
         */
        private int insertPoint(T key) {
            int low = 0;
            int high = size() - 1;
    
            while (low <= high) {
                int mid = (low + high) >>> 1;
                Comparable<? super T> midVal = (Comparable<T>) get(mid);
                int cmp = midVal.compareTo(key);
    
                if (cmp < 0)
                    low = mid + 1;
                else if (cmp > 0)
                    high = mid - 1;
                else {
                    return mid; //key found
                }
            }
    
            return low;  //key not found
        }
    }

    aioobe la solución se pone muy lento cuando se utilizan listas de gran tamaño. Utilizando el hecho de que la lista está ordenada que nos permite encontrar el punto de inserción para los nuevos valores mediante búsqueda binaria.

    Yo también uso la composición a través de herencia, algo a lo largo de las líneas de

    SortedList<E> implements List<E>, RandomAccess, Cloneable, java.io.Serializable
  7. 1

    Podría subclase ArrayList, y llamar a las Colecciones.sort(este) después de cualquier elemento se agrega – se tendría que anular dos versiones de agregar, y dos de addAll, para hacer esto.

    Rendimiento podría no ser tan buena como una inteligente aplicación que inserta elementos en el lugar correcto, pero es que hacer el trabajo. Si se suma a la lista es raro, el costo amortizado sobre todas las operaciones en la lista debe ser baja.

  8. 0

    Creo que la elección entre SortedSets/Listas y ‘normal’ que se puede ordenar colecciones depende, si usted necesita ordenar solo para fines de presentación o en casi cada punto durante el tiempo de ejecución. El uso de una colección ordenada puede ser mucho más caro debido a que la ordenación se realiza cada vez que se inserta un elemento.

    Si usted no puede optar por una colección en el JDK, usted puede tomar un vistazo a la Apache Commons Colecciones

  9. 0

    Desde la propuesta actualmente implementaciones que implementan una lista ordenada por la rotura de la Colección de API, tienen una propia implementación de un árbol o algo similar, yo estaba curiosidades de cómo una aplicación basada en el TreeMap que iba a realizar. (Especialy desde el TreeSet hace base en TreeMap, demasiado)

    Si alguien está interesado en que, también, él o ella puede sentirse libre para buscar en él:

    TreeList

    Su parte de la núcleo de la biblioteca, puede agregarlo a través de Maven dependencia de curso. (Licencia Apache)

    Actualmente la aplicación se parece a comparar muy bien en el mismo nivel que el de la guayaba SortedMultiSet y a la TreeList de Apache Commons biblioteca.

    Pero yo sería feliz si más que sólo me pondría a prueba la aplicación para asegurarse de que no me pierda de algo importante.

    Saludos!

  10. 0

    Yo tenía el mismo problema. Así que me tomé el código fuente de java.util.TreeMap y escribió IndexedTreeMap. Se implementa a mi propia IndexedNavigableMap:

    public interface IndexedNavigableMap<K, V> extends NavigableMap<K, V> {
       K exactKey(int index);
       Entry<K, V> exactEntry(int index);
       int keyIndex(K k);
    }

    La aplicación se basa en la actualización del nodo de pesos en el árbol rojo-negro cuando se cambia. El peso es el número de nodos secundarios debajo de un nodo dado, además de un auto. Por ejemplo, cuando un árbol se gira a la izquierda:

        private void rotateLeft(Entry<K, V> p) {
        if (p != null) {
            Entry<K, V> r = p.right;
    
            int delta = getWeight(r.left) - getWeight(p.right);
            p.right = r.left;
            p.updateWeight(delta);
    
            if (r.left != null) {
                r.left.parent = p;
            }
    
            r.parent = p.parent;
    
    
            if (p.parent == null) {
                root = r;
            } else if (p.parent.left == p) {
                delta = getWeight(r) - getWeight(p.parent.left);
                p.parent.left = r;
                p.parent.updateWeight(delta);
            } else {
                delta = getWeight(r) - getWeight(p.parent.right);
                p.parent.right = r;
                p.parent.updateWeight(delta);
            }
    
            delta = getWeight(p) - getWeight(r.left);
            r.left = p;
            r.updateWeight(delta);
    
            p.parent = r;
        }
      }

    updateWeight simplemente actualiza los pesos hasta la raíz:

       void updateWeight(int delta) {
            weight += delta;
            Entry<K, V> p = parent;
            while (p != null) {
                p.weight += delta;
                p = p.parent;
            }
        }

    Y cuando necesitamos buscar el elemento mediante el índice de aquí es la aplicación que utiliza pesas:

    public K exactKey(int index) {
        if (index < 0 || index > size() - 1) {
            throw new ArrayIndexOutOfBoundsException();
        }
        return getExactKey(root, index);
    }
    
    private K getExactKey(Entry<K, V> e, int index) {
        if (e.left == null && index == 0) {
            return e.key;
        }
        if (e.left == null && e.right == null) {
            return e.key;
        }
        if (e.left != null && e.left.weight > index) {
            return getExactKey(e.left, index);
        }
        if (e.left != null && e.left.weight == index) {
            return e.key;
        }
        return getExactKey(e.right, index - (e.left == null ? 0 : e.left.weight) - 1);
    }

    También es muy útil encontrar el índice de clave:

    Usted puede encontrar el resultado de este trabajo en la http://code.google.com/p/indexed-tree-map/

    TreeSet/TreeMap (así como sus indexado sus homólogos de la indexado árbol de un proyecto de mapa) no se permiten claves duplicadas , puede utilizar la tecla 1 para una matriz de valores. Si usted necesita un SortedSet con duplicados uso TreeMap con los valores de las matrices. Yo haría eso.

Dejar respuesta

Please enter your comment!
Please enter your name here