¿Por qué no hay SortedList en Java?

503

En Java existen las interfaces SortedSety SortedMap. Ambos pertenecen al marco de Java Collections y proporcionan una forma ordenada de acceder a los elementos.

Sin embargo, según tengo entendido, no hay SortedListen Java. Puede usar java.util.Collections.sort()para ordenar una lista.

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

Jijoy
fuente
66
Entonces, ¿cuál es su resultado esperado al insertar un elemento en el medio de la lista?
bestsss
44
@bestsss Sería completamente posible tener una clase SortedList que no implemente la interfaz java.util.List. Lea la pregunta como una pregunta de por qué no hay una estructura de datos que admita la funcionalidad solicitada. No se distraiga con detalles insignificantes como los nombres.
Alderath
@Alderath, la estructura habitual para esto es un árbol (rojo / negro, avl o btree) con enlaces prev / next adicionales para admitir pedidos. Yo uso estructura similar rojo / negro con enlaces prev / next. Sin embargo, es un uso bastante especializado. El árbol puede atravesarse tanto en orden como en orden de inserción, tiene O (logn) find / contiene pero get (int) es O (n). Dado el hecho de su aplicabilidad de nicho, supongo que se dejó a los desarrolladores implementar uno si lo necesitan.
bestsss
3
No respondo la pregunta "por qué", pero la solución más simple para TreeSet es usar un Comparador que nunca devuelve cero, por ejemplo, int diff = this.score - that.score; return (diff == 0) ? 1 : diff; como es un truco maloliente, proporcionaría esto como un argumento de constructor anónimo en lugar de tener ningún implemento Comparable.
Earcam

Respuestas:

682

Los iteradores de lista garantizan en primer lugar 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 ordenación puede verse 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 tal como lo veo personalmente:

1. Considere usar Seto Bagcolecciones en su 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 realiza la clasificación mientras agrega elementos a la colección. También significa que no necesita ordenarlo manualmente.

Además, si está seguro de que no necesita preocuparse por (o tener) elementos duplicados, puede usar el TreeSet<T>en su lugar. Implementa SortedSete NavigableSetinteractúa y funciona como probablemente esperarías 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 a Comparator<T>.

Alternativamente, puede usar Multisets (también conocidos como Bolsas ) , es decir, Setque permite elementos duplicados, y hay implementaciones de terceros de ellos. Más notablemente de las bibliotecas de guayaba hay un TreeMultiset, que funciona mucho como el TreeSet.

2. Ordene su lista con Collections.sort()

Como se mencionó anteriormente, la clasificación de Lists es una manipulación de la estructura de datos. Entonces, para situaciones en las que necesita "una fuente de verdad" que se clasificará de varias maneras, entonces ordenarlas manualmente es el camino a seguir.

Puedes ordenar tu lista con el java.util.Collections.sort()método. 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"

Usando comparadores

Un beneficio claro es que puede usarlo Comparatoren el sortmétodo. Java también proporciona algunas implementaciones para Comparator, como la Collatorque es útil para cadenas de clasificación sensibles a la configuración regional. Aquí hay un ejemplo:

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

Collections.sort(strings, usCollator);

Ordenar en entornos concurrentes

Sin embargo, tenga en cuenta que el uso del sortmétodo no es amigable en entornos concurrentes, ya que la instancia de la colección será manipulada, y debería considerar el uso de colecciones inmutables. Esto es algo que Guava ofrece en la Orderingclase y es simple:

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

3. Envuelva su lista con java.util.PriorityQueue

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

Nico Haase enlazó 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 desee manipular la estructura de datos interna, por lo que PriorityQueue no implementa la interfaz Lista (porque eso le daría acceso directo a sus elementos).

Advertencia sobre el PriorityQueueiterador

La PriorityQueueclase implementa las interfaces Iterable<E>y Collection<E>para que pueda iterarse como de costumbre. Sin embargo, no se garantiza que el iterador devuelva elementos en el orden ordenado. En cambio (como señala Alderath en los comentarios) necesita hacer poll()cola hasta que esté vacío.

Tenga en cuenta que puede convertir una lista en una cola prioritaria 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 SortedListclase

NOTA: No debería tener que hacer esto.

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

  1. Rompe el contrato que List<E>tiene la interfaz porque los addmétodos deben garantizar que el elemento residirá en el índice que el usuario especifique.
  2. ¿Por qué reinventar la rueda? En su lugar, debe usar TreeSet o Multisets como se señala en el primer punto anterior.

Sin embargo, si desea hacerlo como ejercicio, aquí hay una muestra de código para comenzar, utiliza la AbstractListclase abstracta:

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 anulado los métodos que necesita, las implementaciones predeterminadas de AbstractListarrojarán UnsupportedOperationExceptions.

Spoike
fuente
12
+1. Imo, esto es más constructivo que la respuesta más votada. Sin embargo, viene con dos inconvenientes menores. PriorityQueue no admite acceso aleatorio. No puede hacer un vistazo (elementIndex). Entonces no puedes hacer, por ejemplo Integer maxVal = prioQueue.peek(prioQueue.size() - 1);. En segundo lugar, si tiene la intención de utilizar PriorityQueue simplemente como una lista ordenada, sonará menos intuitivo ver PriorityQueueen el código de lo que hubiera sido ver SortedList, si existiera dicha estructura de datos.
Alderath
12
Y, después de ver la otra pregunta que alguien vinculó en los comentarios, otra gran desventaja es que no se garantiza que el iterador de PriorityQueue devuelva elementos en ningún orden específico. Por lo tanto, a menos que esté pasando por alto algo, la única forma de, por ejemplo, imprimir todos los objetos en PriorityQueue para sondear repetidamente () la cola hasta que esté vacía. Para mí, esto se siente al límite relanzado. Para imprimir los objetos en un PriorityQueue dos veces, primero debe copiar el PriorityQueue y luego sondear () todos los objetos del PriorityQueue original y luego pol () l todos los objetos de la copia.
Alderath
1
Hmm ... parece que tienes razón, Alderath. No puede usar el iterador de PriorityQueue para obtener los elementos en el orden esperado. Parece que tengo que editar mi respuesta.
Spoike
77
La cola de prioridad es solo un montón, puede acceder solo a la parte superior, a decir verdad, no pertenece a la respuesta de la pregunta.
bestsss
1
También vale la pena señalar que Collections.sort()incluso le permite definir la función de comparación que se utiliza para ordenar, mediante el uso de un Comparatorobjeto.
Mike 'Pomax' Kamermans
71

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 list.add(7, elem), list.get(7)volverá una llamada a elem. Con una lista ordenada automáticamente, el elemento podría terminar en una posición arbitraria.

Michael Borgwardt
fuente
26

Como todas las listas ya están "ordenadas" por el orden en que se agregaron los elementos (orden FIFO), puede "recurrirlas" con otro orden, incluido el orden natural de los elementos java.util.Collections.sort().

EDITAR:

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

Los conjuntos no tienen esa información.

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

SJuan76
fuente
22
El conjunto no permite duplicados
bestsss
10
No creo que esta sea una muy buena respuesta. Claro, las listas en la API de Java tienen un orden específico determinado por cuándo / cómo se insertaron los elementos. Sin embargo, la existencia de listas ordenadas de una manera que depende del método / tiempo de inserción no impide tener otras estructuras de datos en cuyo orden se determina de otra manera (por ejemplo, un Comparador). Básicamente, el OP pregunta por qué no hay una estructura de datos equivalente a un SortedSet con la excepción de que la estructura de datos debe permitir múltiples ocurrencias de elementos que son iguales.
Alderath
55
Entonces, mi pregunta de seguimiento sería: " ¿Por qué no hay una estructura de datos que funcione como un SortedSet, pero que pueda contener múltiples elementos iguales? " (Y no responda " porque los Conjuntos solo pueden contener un elemento ")
Alderath
@Alderath: consulte stackoverflow.com/questions/416266/sorted-collection-in-java . En resumen: use TreeMultiset de guayaba
Janus Troelsen
44
Las listas NO están "ordenadas", incluso si pones "ordenadas" entre comillas dobles. Están ordenados
Koray Tugay
21

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

ingrese la descripción de la imagen aquí


La estructura de datos de árbol SortedSety las SortedMapinterfaces implementan TreeSety TreeMaputilizan respectivamente el algoritmo de implementación de árbol rojo-negro utilizado . 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 Listpodemos tener duplicados, por lo que no hay TreeList(es decir, no SortedList).
  • La lista mantiene los elementos en orden de inserción. Entonces, si queremos ordenar la lista, tenemos que usarla java.util.Collections.sort(). Ordena la lista especificada en orden ascendente, de acuerdo con el orden natural de sus elementos.
Premraj
fuente
14

JavaFX SortedList

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

Como puede ver en los javadocs, forma parte de las colecciones JavaFX , destinadas a proporcionar una vista ordenada en un ObservableList.

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 separada. JavaFX 11 está disponible como un SDK descargable o desde MavenCentral. Ver https://openjfx.io

swpalmer
fuente
2
Desafortunadamente, esta SortedList no funciona como una lista habitual; por ejemplo, no tiene un constructor predeterminado (debe construirla usando una ObservableList, lo que sea que eso signifique ...)
Erel Segal-Halevi
La SortedList de JavaFX claramente es para el uso de componentes GUI y debido a la sobrecarga NO es adecuada solo para tener una lista de objetos ordenados. También significaría hacer referencia a todo el Módulo FX incluso si la GUI no se usa en el proyecto.
COBRA.cH
1
@ COBRA.cH Sí, eso es cierto. Una lista ordenada más eficaz probablemente podría ser una envoltura delgada alrededor de un TreeMap, donde se usa un número entero para contar duplicados de la clave. También puede usar un TreeSet con un comparador que nunca devuelve 0.
swpalmer
¿Por qué los votos negativos? La pregunta comienza con una presuposición de que no hay una lista ordenada en las bibliotecas JDK. Esta respuesta corrige esa suposición. Si le gusta o no la implementación de esta lista ordenada en particular no es una razón para rechazar el voto. Esta respuesta no recomienda la clase, simplemente señala su existencia.
Basil Bourque
10

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

Amagi82
fuente
1
Vale la pena señalar que en el momento de este comentario, los Androids SortedList carecen de soporte para la funcionalidad onItemMoved () con RecyclerView. Escribir mi propia SortedList, que es menos eficiente, es lo que tuve que hacer para sortear las limitaciones.
Mateo
4

Otro punto es la complejidad temporal 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 equalso compare.

Ingo
fuente
puede tener una lista sin insertar (eliminar) / eliminar / buscar / contiene pero no con w / get (int).
bestsss
3
El último punto no es realmente una buena explicación. Puede hacer una SortedSetde las cosas que no se implementan Comparable. Vea este constructor de TreeSet .
Alderath
1
@Alderath: tal vez mi redacción era demasiado débil. Sin embargo, la observación sostiene que los elementos de Conjuntos y claves de Árboles deben ser comparables al menos para la igualdad, mientras que los elementos de la lista no necesariamente. Si la relación de orden / igualdad para Conjuntos y Árboles se implementa en un Comparador o en otro lugar es irrelevante, pero necesita uno.
Ingo
Las listas no garantizan la inserción de O (1) , garantizan el acceso de O (1) . bigocheatsheet.com
Matt Quigley
1
@Betlista tienes razón! No puedo actualizar mi comentario, pero la Listinterfaz Java no garantiza ninguna especificación de rendimiento en sus métodos.
Matt Quigley el
3

Piense en ello como esto: la Listinterfaz 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.

Si cualquier implementación de la lista almacenara elementos en un orden distinto al basado en el índice, los métodos de lista anteriores no tendrían sentido.

Costi Ciudatu
fuente
2

La primera línea de la API de lista dice que es una colección ordenada (también conocida como secuencia). Si ordena la lista, no puede mantener el orden, por lo que no hay TreeList en Java.
Como dice API, Java List se inspiró en Sequence y vea las propiedades de 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 listas de forma predeterminada.

Syam
fuente
2

En caso de que esté buscando una forma de ordenar elementos, pero también poder acceder a ellos por índice de manera eficiente, puede hacer lo siguiente:

  1. Utilice una lista de acceso aleatorio para el almacenamiento (p ArrayList. Ej. )
  2. Asegúrese de que siempre esté ordenado

Luego, para agregar o eliminar un elemento que puede usar Collections.binarySearchpara obtener el índice de inserción / eliminación. Como su lista implementa acceso aleatorio, puede modificar eficientemente la lista con el índice determinado.

Ejemplo:

/**
 * @deprecated
 *      Only for demonstration purposes. Implementation is incomplete and does not 
 *      handle invalid arguments.
 */
@Deprecated
public class SortingList<E extends Comparable<E>> {
    private ArrayList<E> delegate;

    public SortingList() {
        delegate = new ArrayList<>();
    }

    public void add(E e) {
        int insertionIndex = Collections.binarySearch(delegate, e);

        // < 0 if element is not in the list, see Collections.binarySearch
        if (insertionIndex < 0) {
            insertionIndex = -(insertionIndex + 1);
        }
        else {
            // Insertion index is index of existing element, to add new element 
            // behind it increase index
            insertionIndex++;
        }

        delegate.add(insertionIndex, e);
    }

    public void remove(E e) {
        int index = Collections.binarySearch(delegate, e);
        delegate.remove(index);
    }

    public E get(int index) {
        return delegate.get(index);
    }
}
Marcono1234
fuente
1

Considere usar 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 actualizar los pesos de los nodos cambiantes cada vez que hay un cambio.

Vitaly Sazanovich
fuente