ejemplo - ¿Por qué no hay SortedList en Java?

private jlabel

Question

En Java hay las interfaces SortedSet y SortedMap . Ambos pertenecen al marco de Colecciones estándar de Java y proporcionan una forma ordenada de acceder a los elementos.

Sin embargo, a mi entender, no hay una lista SortedList en Java. Puede usar java.util.Collections.sort() para ordenar una lista.

¿Alguna idea de por qué está diseñado así?

Answer 1

SortedList JavaFX

Aunque tomó un tiempo, Java 8 tiene una List ordenada. http://docs.oracle.com/javase/8/javafx/api/javafx/collections/transformation/SortedList.html

Como puede ver en los javadocs, forma parte de las colecciones de JavaFX , con la intención de proporcionar una vista ordenada en una lista observable.

Actualización: Tenga en cuenta que con Java 11, el kit de herramientas JavaFX se ha movido fuera del JDK y ahora es una biblioteca independiente. JavaFX 11 está disponible como un SDK descargable o de MavenCentral. Ver https://openjfx.io

Answer 2

Considere el uso de indexed-tree-map . Es un TreeSet de JDK mejorado que proporciona acceso al elemento por índice y encuentra el índice de un elemento sin iteración o listas subyacentes ocultas que respaldan el árbol. El algoritmo se basa en la actualización de los pesos de los nodos cambiantes cada vez que se produce un cambio.

Answer 3

Dado que todas las listas ya están "ordenadas" por el orden en que se agregaron los artículos (pedido FIFO), puede "recurrir" a ellos con otro orden, incluido el orden natural de los elementos, utilizando java.util.Collections.sort() .

EDITAR:

Las listas como estructuras de datos se basan en lo que es interesante es el orden en el que se insertaron los elementos.

Los conjuntos no tienen esa información.

Si desea realizar un pedido agregando tiempo, use List . Si desea ordenar por otros criterios, use SortedSet .

Answer 4

La primera línea en la API de la lista dice que es una colección ordenada (también conocida como una secuencia). Si ordena la lista, no puede mantener el orden, por lo que no hay una lista de árboles en Java.
Como dice la API, la Lista de Java se inspiró en la secuencia y vea las propiedades de la secuencia http://en.wikipedia.org/wiki/Sequence_(mathematics )

No significa que no pueda ordenar la lista, pero Java es estricto con su definición y no proporciona versiones ordenadas de las listas de forma predeterminada.

Answer 5

Los iteradores de lista garantizan, ante todo, que obtiene los elementos de la lista en el orden interno de la lista (también conocido como orden de inserción ). Más específicamente, está en el orden en que ha insertado los elementos o en cómo ha manipulado la lista. La clasificación se puede ver como una manipulación de la estructura de datos, y hay varias formas de ordenar la lista.

Ordenaré las formas en el orden de utilidad como lo veo personalmente:

1. Considera usar colecciones de Set o Bag lugar

NOTA: Pongo esta opción en la parte superior porque esto es lo que normalmente quieres hacer de todos modos.

Un conjunto ordenado clasifica automáticamente la colección en la inserción , lo que significa que hace la clasificación mientras agrega elementos a la colección. También significa que no es necesario ordenarlo manualmente.

Además, si está seguro de que no necesita preocuparse (o tener) elementos duplicados, puede utilizar el TreeSet<T> lugar. Implementa las interfaces SortedSet y SortedSet y funciona como probablemente esperaría de una lista:

TreeSet<String> set = new TreeSet<String>();
set.add("lol");
set.add("cat");
// automatically sorts natural order when adding

for (String s : set) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Si no desea el orden natural, puede usar el parámetro constructor que toma un Comparator<T> .

Alternativamente, puede usar Multisets (también conocido como Bolsas ) , que es un Set que permite elementos duplicados, en lugar de eso, y existen implementaciones de terceros. En particular, de las bibliotecas de guayaba hay un TreeMultiset , que funciona muy parecido al TreeSet .

2. Ordena tu lista con Collections.sort()

Como se mencionó anteriormente, la clasificación de la List s es una manipulación de la estructura de datos. Por lo tanto, para situaciones en las que necesite "una fuente de verdad" que se clasifique de varias maneras, entonces la forma de hacerlo manualmente es el camino a seguir.

Puede ordenar su lista con el método java.util.Collections.sort() . Aquí hay un ejemplo de código sobre cómo:

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

Collections.sort(strings);
for (String s : strings) {
    System.out.println(s);
}
// Prints out "cat" and "lol"

Utilizando comparadores

Un beneficio claro es que puede usar Comparator en el método de sort . Java también proporciona algunas implementaciones para el Comparator , como Collator que es útil para cadenas de clasificación sensibles al entorno local. Aquí hay un ejemplo:

Collator usCollator = Collator.getInstance(Locale.US);
usCollator.setStrength(Collator.PRIMARY); // ignores casing

Collections.sort(strings, usCollator);

Clasificación en entornos concurrentes

Sin embargo, tenga en cuenta que el uso del método de sort no es amigable en entornos concurrentes, ya que la instancia de colección será manipulada, y debería considerar usar colecciones inmutables en su lugar. Esto es algo que Guava proporciona en la clase de Ordering y es simple:

List<string> sorted = Ordering.natural().sortedCopy(strings);

3. Envuelve tu lista con java.util.PriorityQueue

Aunque no hay una lista ordenada en Java, sin embargo hay una cola ordenada que probablemente funcione igual de bien para usted. Es la clase java.util.PriorityQueue .

Nico Haase vinculó en los comentarios a una pregunta relacionada que también responde a esto.

En una colección ordenada, lo más probable es que no quiera manipular la estructura de datos interna, razón por la cual PriorityQueue no implementa la interfaz de la Lista (porque eso le daría acceso directo a sus elementos).

Advertencia sobre el iterador PriorityQueue

La clase PriorityQueue implementa las interfaces Iterable<E> y Collection<E> para que se pueda iterar como de costumbre. Sin embargo, no se garantiza que el iterador devuelva elementos en el orden ordenado. En su lugar (como señala Alderath en los comentarios) debe poll() la cola hasta que esté vacía.

Tenga en cuenta que puede convertir una lista en una cola de prioridad a través del constructor que toma cualquier colección :

List<String> strings = new ArrayList<String>()
strings.add("lol");
strings.add("cat");

PriorityQueue<String> sortedStrings = new PriorityQueue(strings);
while(!sortedStrings.isEmpty()) {
    System.out.println(sortedStrings.poll());
}
// Prints out "cat" and "lol"

4. Escribe tu propia clase SortedList

NOTA: No deberías tener que hacer esto.

Puede escribir su propia clase de lista que ordena cada vez que agrega un nuevo elemento. Esto puede hacer que el cómputo sea bastante pesado dependiendo de su implementación y no tiene sentido , a menos que quiera hacerlo como un ejercicio, debido a dos razones principales:

1. Rompe el contrato que tiene la interfaz List<E> porque los métodos de add deben garantizar que el elemento residirá en el índice que el usuario especifica.
2. ¿Por qué reinventar la rueda? Debería usar TreeSet o Multisets en su lugar, como se señaló en el primer punto anterior.

Sin embargo, si desea hacerlo como un ejercicio aquí es un ejemplo de código para comenzar, utiliza la clase abstracta AbstractList :

public class SortedList<E> extends AbstractList<E> {

    private ArrayList<E> internalList = new ArrayList<E>();

    // Note that add(E e) in AbstractList is calling this one
    @Override 
    public void add(int position, E e) {
        internalList.add(e);
        Collections.sort(internalList, null);
    }

    @Override
    public E get(int i) {
        return internalList.get(i);
    }

    @Override
    public int size() {
        return internalList.size();
    }

}

Tenga en cuenta que si no ha reemplazado los métodos que necesita, entonces las implementaciones predeterminadas de AbstractList generarán las excepciones de UnsupportedOperationException ( UnsupportedOperationException ).

Answer 6

Otro punto es la complejidad del tiempo de las operaciones de inserción. Para una inserción de lista, se espera una complejidad de O (1). Pero esto no se puede garantizar con una lista ordenada.

Y el punto más importante es que las listas no asumen nada sobre sus elementos. Por ejemplo, puede hacer listas de cosas que no implementan ni compare equals .

Answer 7

Para todos los recién llegados, a partir de abril de 2015, Android ahora tiene una clase SortedList en la biblioteca de asistencia, diseñada específicamente para trabajar con RecyclerView . Aquí está la publicación del blog al respecto.

Answer 8

Piénselo así: la interfaz de la List tiene métodos como add(int index, E element) , set(int index, E element) . El contrato es que una vez que haya agregado un elemento en la posición X, lo encontrará allí a menos que agregue o elimine elementos antes de él.

Si alguna de las implementaciones de la lista almacenara elementos en algún orden distinto al basado en el índice, los métodos de la lista anterior no tendrían sentido.

Answer 9

Porque el concepto de una lista es incompatible con el concepto de una colección ordenada automáticamente. El punto de una lista es que después de llamar a list.add(7, elem) , una llamada a list.get(7) devolverá elem . Con una lista auto-ordenada, el elemento podría terminar en una posición arbitraria.

Answer 10

Set y Map son estructuras de datos no lineales. La lista es la estructura de datos lineales.

Las SortedSet estructura de datos de árbol SortedSet y SortedMap implementan TreeSet y TreeMap respectivamente usando el algoritmo de implementación de árbol rojo-negro usado. Por lo tanto, asegúrese de que no haya elementos duplicados (o claves en caso de Map ).

• List ya mantiene una colección ordenada y una estructura de datos basada en índices, los árboles no son estructuras de datos basadas en índices.
• Tree por definición no puede contener duplicados.
• En la List podemos tener duplicados, por lo que no hay una lista de TreeList (es decir, no hay una lista de SortedList ).
• Lista mantiene elementos en orden de inserción. Entonces, si queremos ordenar la lista, tenemos que usar java.util.Collections.sort() . Ordena la lista especificada en orden ascendente, de acuerdo con el orden natural de sus elementos.