recorrer - Clasificación de listas de Java: ¿hay alguna manera de mantener una lista ordenada de manera permanente como TreeMap?
listas en java netbeans ejemplos (13)
Comentario
Probablemente haya una buena razón para que no exista SortedList implementación SortedList en el JDK. Personalmente, no puedo pensar en una razón para tener una clasificación automática en el JDK.
Apesta a una optimización prematura que salió mal. Si la lista no se lee tan a menudo como se inserta, entonces perderá ciclos ordenando repetidamente sin ningún motivo. Ordenar antes de leer sería mucho más reactivo y tener un boolean algún lugar que indique que la lista necesita o no ordenarse antes de leer sería aún mejor.
Lo único que realmente importa es el orden al atravesar la lista con un Iterator o for each ciclo, por lo que llamar a Collections.sort() antes de cualquier código que itere probablemente sea más eficaz que intentar mantener la lista ordenada todo el tiempo en cada inserción.
Existen ambigüedades con List debido a los duplicados, ¿cómo se ordenan los duplicados de manera determinista? Hay SortedSet , y eso tiene sentido debido a la singularidad. Pero ordenar una List puede tener más complicaciones por los efectos secundarios de duplicados y otras restricciones como hacer que cada objeto sea Comparable o como muestro en mi código, teniendo que tener un Comparator que pueda hacer el trabajo en su lugar.
Clasificando en .add()
Si tiene una situación muy especial en la que una List clasificación automática sería útil, una cosa que podría hacer es sub-clase una implementación de List y .add() para hacer una Collections.sort(this, comparator) que usted pasar a un constructor personalizado. Utilicé LinkedList lugar de ArrayList por una razón, ArrayList es una List orden de inserción natural para comenzar. También tiene la capacidad de .add() en un índice que es bastante inútil si quiere una List constantemente ordenada, que tendría que manejarse de alguna manera que probablemente sería menos que ideal. De acuerdo con el Javadoc;
void add(int index, Object element)
Inserta el elemento especificado en la posición especificada en esta lista ( operación opcional ).
Por lo tanto, solo sería aceptable lanzar UnSupportedOperationException , o simplemente podría ignorar el index y delegar en .add(Object element); si lo documenta en un JavaDoc en el método.
Por lo general, cuando desea realizar muchas inserciones / eliminaciones y ordenar, debe usar una LinkedList debido a las mejores características de rendimiento dado el uso de la `Lista ''.
Aquí hay un ejemplo rápido:
import java.util.Collections;
import java.util.Comparator;
import java.util.LinkedList;
public class SortedList<E> extends LinkedList<E>
{
private Comparator<E> comparator;
public SortedList(final Comparator<E> comparator)
{
this.comparator = comparator;
}
/**
* this ignores the index and delegates to .add()
* so it will be sorted into the correct place immediately.
*/
@Override
public void add(int index, Object element)
{
this.add(element);
}
@Override
public boolean add(final E e)
{
final boolean result = super.add(e);
Collections.sort(this, this.comparator);
return result;
}
}
La solución más eficiente:
Alternativamente, solo se podía ordenar al obtener el Iterator y esto estaría más orientado al rendimiento si el orden ordenado fuera realmente importante al iterar sobre la List . Esto cubriría el caso de uso del código del cliente al no tener que llamar, Collections.sort() antes de cada iteración y encapsular ese comportamiento en la clase.
import java.util.Collections;
import java.util.Comparator;
import java.util.Iterator;
import java.util.LinkedList;
public class SortedList<E> extends LinkedList<E>
{
private Comparator<E> comparator;
public SortedList(final Comparator<E> comparator)
{
this.comparator = comparator;
}
@Override
public Iterator<E> iterator()
{
Collections.sort(this, this.comparator);
return super.iterator();
}
}
Por supuesto, habría que verificar y controlar los errores para ver si el Comparator era null o no y qué hacer si ese fuera el caso, pero esto le da la idea. Aún no tienes una forma determinista de lidiar con duplicados.
Solución de Guava:
Si está usando guayaba y debería estarlo, puede usar
Ordering.immutableSortedCopy() solo cuando necesita iterar y terminarlo.
En Java puedes construir una ArrayList con elementos y luego llamar:
Collections.sort(list, comparator);
¿Hay alguna forma de pasar el Comparador en el momento de la creación de la Lista como lo puede hacer con TreeMap? El objetivo es poder agregar un elemento a la lista y en lugar de tenerlo adjunto automáticamente al final de la lista, la lista se mantendrá ordenada en función del Comparador e insertará el nuevo elemento en el índice determinado por el Comparador. Así que, básicamente, la lista podría tener que reordenar cada nuevo elemento agregado.
¿Hay alguna forma de lograr esto de esta manera con el Comparador o por algún otro medio similar?
Algo como TreeSet (o TreeMultiset en caso de que necesite duplicados) con un acceso aleatorio más eficiente es posible, pero dudo que se haya implementado en Java. Hacer que cada nodo del árbol recuerde el tamaño de su subárbol izquierdo permite acceder a un elemento por índice en el tiempo O(log(size)) que no está mal.
Para implementarlo, necesitaría reescribir una buena porción del TreeMap subyacente.
Considere el indexed-tree-map que creé al enfrentar un problema similar, podrá acceder a los elementos por índice y obtener el índice de los elementos mientras mantiene el orden de clasificación. Los duplicados se pueden poner en matrices como valores bajo la misma clave.
Creo que una cola prioritaria hará el trabajo.
Advertencia (de la misma página de documento):
Esta clase y su iterador implementan todos los métodos opcionales de las interfaces
Collectione Iterator. No se garantiza que elIteratorproporcionado en eliterator()métodoiterator()atraviese los elementos de la cola de prioridad en un orden particular. Si necesita un recorrido ordenado, considere usarArrays.sort(pq.toArray()).
El contrato de la interfaz ListIterator lo hace un poco engorroso, pero este método realizará la inserción utilizando un único escaneo de la lista (hasta el punto de inserción):
private void add(Integer value) {
ListIterator<Integer> listIterator = list.listIterator();
Integer next = null;
while (listIterator.hasNext()) {
next = listIterator.next();
if (next.compareTo(value) > 0) {
break;
}
}
if (next == null || next.compareTo(value) < 0) {
listIterator.add(value);
} else {
listIterator.set(value);
listIterator.add(next);
}
}
La única forma de tener cualquier estructura ordenada con menos de O (n) tiempo para agregar / indexOf / remove / get element es usando un árbol. En ese caso, las operaciones generalmente tienen O (log2n) y poligonal es como O (1).
O (n) es solo una lista vinculada.
Editar: insertando en la lista vinculada w / búsqueda binaria. Para las operaciones de inserción, no usar estructura binaria, y tamaños no pequeños, eso debería ser óptimo.
@Peter: existe el algo w / O (log2n) que se compara (que es lento) para insertar y O (n) se mueve. Si necesita anular LinkedList, que así sea. Pero eso es lo mejor que puede obtener. Mantengo el algoritmo lo más limpio posible para que sea más comprensible, se puede optimizar un poco.
package t1;
import java.util.LinkedList;
import java.util.List;
import java.util.ListIterator;
import java.util.Random;
public class SortedList {
private static <T> int binarySearch(ListIterator<? extends Comparable<? super T>> i, T key){
int low = 0;
int high= i.previousIndex();
while (low <= high) {
int mid = (low + high) >>> 1;
Comparable<? super T> midVal = get(i, mid);
int cmp = midVal.compareTo(key);
if (cmp < 0)
low = mid + 1;
else if (cmp > 0)
high = mid - 1;
else
return mid;
}
return -(low + 1); // key not found
}
private static <T> T get(ListIterator<? extends T> i, int index) {
T obj = null;
int pos = i.nextIndex();
if (pos <= index) {
do {
obj = i.next();
} while (pos++ < index);
} else {
do {
obj = i.previous();
} while (--pos > index);
}
return obj;
}
private static void move(ListIterator<?> i, int index) {
int pos = i.nextIndex();
if (pos==index)
return;
if (pos < index) {
do {
i.next();
} while (++pos < index);
}
else {
do {
i.previous();
} while (--pos > index);
}
}
@SuppressWarnings("unchecked")
static <T> int insert(List<? extends Comparable<? super T>> list, T key){
ListIterator<? extends Comparable<? super T>> i= list.listIterator(list.size());
int idx = binarySearch(i, key);
if (idx<0){
idx=~idx;
}
move(i, idx);
((ListIterator<T>)i).add(key);
return i.nextIndex()-1;
}
public static void main(String[] args) {
LinkedList<Integer> list = new LinkedList<Integer>();
LinkedList<Integer> unsorted = new LinkedList<Integer>();
Random r =new Random(11);
for (int i=0;i<33;i++){
Integer n = r.nextInt(17);
insert(list, n);
unsorted.add(n);
}
System.out.println(" sorted: "+list);
System.out.println("unsorted: "+unsorted);
}
La mejor manera de hacer esto sería anular la implementación de agregar una lista. Voy a utilizar LinkedList para demostrarlo, ya que permite una inserción eficiente.
public boolean add(Integer e)
{
int i = 0;
for (Iterator<Integer> it = this.iterator(); it.hasNext();)
{
int current = it.next();
if(current > e)
{
super.add(i, e);
return true;
}
i++;
}
return super.add(e);
}
El código anterior crea una lista ordenada de enteros, que siempre está ordenada. Se puede modificar fácilmente para que funcione con cualquier otro tipo de datos. Sin embargo, aquí deberá evitar el uso de la función de add(index, value) , ya que eso obviamente rompería la clasificación.
Aunque las personas anteriores sugirieron usar Arrays.sort (), lo evitaría, ya que puede ser un enfoque significativamente menos eficiente, especialmente dado que el método de clasificación debe invocarse con cada adición a la lista.
La principal diferencia entre SortedSet y List es:
- SortedSet mantiene su elemento en el orden correcto, pero no puede acceder a un elemento específico por índice.
- La lista permite el acceso indexado y el ordenamiento arbitrario de los elementos. También permite cambiar cualquier elemento (por índice o iterador) a otro elemento, sin que la ubicación cambie.
Parece que desea una especie de fusión de ambos: clasificación automática y acceso al índice (razonablemente rápido). Según el tamaño de los datos y la frecuencia con la lectura indexada o la adición de nuevos elementos, estas son mis ideas:
- ArrayList envuelto, donde el método add usa un ListIterator para encontrar el lugar de inserción, luego insertando el elemento allí. Esto es O (n) para inserciones, O (1) para acceso indexado.
- una LinkedList envolvente, donde el método add utilizó un ListIterator para encontrar el lugar de inserción, luego insertando el elemento allí. (Esto todavía es O (n) para inserciones (con factor a veces bastante menor como ArrayList, a veces incluso más), así como acceso indexado).
- un árbol binario modificado haciendo un seguimiento de los tamaños de ambas mitades en cada nivel, lo que permite el acceso indexado. (Esto sería O (log n) para cada acceso, pero necesita alguna programación adicional, ya que aún no está incluido en Java SE. O puede encontrar alguna biblioteca que pueda hacerlo.)
En cualquier caso, las interfaces y los contratos de SortedSet y List no son realmente compatibles, por lo que querrá que la parte de la Lista sea de solo lectura (o de solo lectura y eliminación), no permita la configuración y la adición, y tenga un extra objeto (tal vez implementando la interfaz de Colección) para agregar Objetos.
La solución obvia es crear su propia clase que implemente la interfaz java.util.List y tome un Comparator como argumento para el constructor. Utilizaría el comparador en los lugares correctos, es decir, el método add iteraría a través de los elementos existentes e insertaría el nuevo en el lugar correcto. No permitirás llamadas a métodos como add(int index, Object obj) etc.
De hecho, alguien debe haber creado esto ya ... una búsqueda rápida en Google revela al menos un ejemplo:
http://www.ltg.ed.ac.uk/NITE/nxt/apidoc/net/sourceforge/nite/util/SortedList.html
Puede cambiar el comportamiento de ArrayList
List<MyType> list = new ArrayList<MyType>() {
public boolean add(MyType mt) {
super.add(mt);
Collections.sort(list, comparator);
return true;
}
};
Nota: un PriorityQueue NO es una Lista, si no le importaba qué tipo de colección era, lo más simple sería usar un TreeSet, que es como un TreeMap pero es una colección. La única ventaja que tiene PriorityQueue es permitir duplicados.
Nota: el recurso no es muy eficiente para grandes colecciones. Usar una búsqueda binaria e insertar una entrada sería más rápido. (pero más complicado)
EDITAR: Mucho depende de lo que necesita la "lista" para hacer. Le sugiero que escriba un Contenedor de listas para una ArrayList, LinkedList, PriorityQueue, TreeSet o una de las otras colecciones ordenadas e implemente los métodos que realmente se utilizarán. De esta forma, tiene una buena comprensión de los requisitos para la colección y puede asegurarse de que funcione correctamente para usted.
EDITAR (2): Dado que había mucho interés en usar binarySearch en su lugar. ;)
List<MyType> list = new ArrayList<MyType>() {
public boolean add(MyType mt) {
int index = Collections.binarySearch(this, mt);
if (index < 0) index = ~index;
super.add(index, mt);
return true;
}
};
Todos están sugiriendo PriorityQueue . Sin embargo, es importante tener en cuenta que si iterate sobre los contenidos de una PriorityQueue , los elementos no estarán ordenados. Solo tiene la garantía de obtener el elemento "mínimo" de los métodos peek() , poll() , etc.
Un TreeSet parece ser una mejor TreeSet . Las advertencias serían que, como Set , no puede contener elementos duplicados y no admite el acceso aleatorio con un índice.
Yo usaría un Guava TreeMultiset suponiendo que quieres una List porque puedes tener elementos duplicados. Hará todo lo que quieras. Lo único que no tendrá es acceso basado en índices, lo cual no tiene mucho sentido dado que de todos modos no está poniendo elementos en los índices que elija. La otra cosa a tener en cuenta es que en realidad no almacenará duplicados de objetos equal ... solo un recuento del número total de ellos.
commons-collections tiene TreeBag
Inicialmente sugerí PriorityQueue , pero su orden de iteración no está definido, por lo que no sirve de nada, a menos que lo iteres obteniendo el encabezado de un clon de la cola hasta que se vacíe.
Como lo más probable es que esté interesado en el orden de iteración, creo que puede anular el método de iterator() :
public class OrderedIterationList<E> extends ArrayList<E> {
@Override
public Iterator<E> iterator() {
Object[] array = this.toArray(); // O(1)
Arrays.sort(array);
return Arrays.asList(array).iterator(); // asList - O(1)
}
}
Puede mejorar esto almacenando una instantánea de la colección ordenada, y usar modCount para verificar si la colección no se cambia.
Dependiendo de los casos de uso, esto puede ser menos o más eficiente que la sugerencia de Peter. Por ejemplo, si agrega varios elementos e itera. (sin agregar elementos entre iteraciones), entonces esto podría ser más eficiente.