convertir - toarray java

Lista ordenada de arreglos en Java

Question

Estoy desconcertado porque no puedo encontrar una respuesta rápida a esto. Básicamente, estoy buscando una estructura de datos en Java que implemente la interfaz java.util.List , pero que almacene sus miembros en un orden ordenado. Sé que puede usar una ArrayList normal y usar Collections.sort() en ella, pero tengo un escenario en el que ocasionalmente agrego y, a menudo, recupero miembros de mi lista y no quiero tener que ordenarlo cada vez que lo hago. recuperar un miembro en caso de que se haya agregado uno nuevo. ¿Alguien puede indicarme algo que existe en el JDK o incluso en bibliotecas de terceros?

EDITAR : la estructura de datos deberá conservar los duplicados.

RESUMEN DE RESPUESTA : Encontré todo esto muy interesante y aprendí mucho. Aioobe, en particular, merece mención por su perseverancia al tratar de cumplir mis requisitos anteriores (principalmente una implementación ordenada de java.util.List que admite duplicados). He aceptado su respuesta como la más precisa para lo que pregunté y la que más me provocó las implicaciones de lo que estaba buscando, incluso si lo que le pedí no era exactamente lo que necesitaba.

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

El usuario de esta interfaz tiene un control preciso sobre en qué parte de la lista se inserta cada elemento.

Insertar en una lista ordenada no tiene un control preciso sobre el punto de inserción. Entonces, debes pensar cómo manejarás algunos de los métodos. Take add por ejemplo:

public boolean add (Object o)

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

Ahora queda en la incómoda situación de: 1) Romper el contrato e implementar una versión ordenada de agregar 2) Dejar add agregar un elemento al final de la lista, rompiendo su orden ordenado 3) Dejar salir (como opcional) lanzando una UnsupportedOperationException e implementando otro método que agrega elementos en un orden ordenado.

La opción 3 es probablemente la mejor, pero me parece desagradable tener un método add que no puedes usar y otro método sortedAdd que no está en la interfaz.

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

• java.util.PriorityQueue que es probablemente lo más cercano a lo que necesitaba de lo que pedí. Una cola no es la definición más precisa de una colección de objetos en mi caso, pero funcionalmente hace todo lo que necesito.
• net.sourceforge.nite.util.SortedList . Sin embargo, esta implementación rompe el contrato de la interfaz de la Lista implementando la clasificación en el método add(Object obj) y extrañamente tiene un método sin efecto para add(int index, Object obj) . El consenso general sugiere throw new UnsupportedOperationException() podría ser una mejor opción en este escenario.
• TreeMultiSet de Guava Una implementación de conjunto que admite duplicados
• ca.odell.glazedlists.SortedList Esta clase viene con la advertencia en su javadoc: Warning: This class breaks the contract required by List

Answer 1

Solución minimalista

Aquí hay una solución "mínima".

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 tiempo lineal, pero eso sería lo que obtendría utilizando una ArrayList de todos modos (todos los elementos a la derecha del elemento insertado tendrían que cambiarse de una forma u otra).

Insertar resultados no comparables en una ClassCastException. (Este es el enfoque adoptado por java.util.PriorityQueue también: una cola de prioridad que depende de la ordenación natural tampoco permite la inserción de objetos no comparables (al hacerlo puede dar lugar a ClassCastException). )

Anulación de List.add

Tenga en cuenta que anular List.add (o List.addAll para el caso) para insertar elementos de una manera ordenada sería una violación directa de la especificación de la interfaz . Lo que podría hacer es anular este método para lanzar UnsupportedOperationException .

De los documentos de List.add :

boolean add(E e)
Agrega el elemento especificado al final de esta lista (operación opcional).

Se aplica el mismo razonamiento para ambas versiones de add , ambas versiones de addAll y set . (Todas las cuales son operaciones opcionales de acuerdo con la interfaz de la lista).

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);

....huellas dactilares:

[ddd]
[aaa, ddd]
[aaa, ccc, ddd]
[aaa, bbb, ccc, ddd]
[aaa, bbb, ccc, ddd, eee]

Answer 2

Creo que la elección entre SortedSets / Lists y las colecciones ordenables ''normales'' depende, ya sea que necesite ordenar solo para fines de presentación o en casi todos los puntos durante el tiempo de ejecución. Usar una colección ordenada puede ser mucho más costoso porque la clasificación se realiza cada vez que inserta un elemento.

Si no puede optar por una colección en el JDK, puede echar un vistazo a las Colecciones de Apache Commons

Answer 3

Dado que las implementaciones actualmente propuestas que implementan una lista ordenada al romper la API de recopilación, tienen una implementación propia de un árbol o algo similar, yo era curioso cómo funcionaría una implementación basada en TreeMap. (Especialmente porque el TreeSet también se basa en TreeMap)

Si alguien está interesado en eso, también, él o ella pueden sentirse libres de investigarlo:

TreeList

Es parte de la biblioteca central , puede agregarla a través de la dependencia de Maven, por supuesto. (Licencia de Apache)

Actualmente, la implementación parece compararse bastante bien en el mismo nivel que la guayaba SortedMultiSet y la TreeList de la biblioteca de Apache Commons.

Pero me sentiría feliz si más que solo yo pusiera a prueba la implementación para asegurarme de no perderme algo importante.

¡Atentamente!

Answer 4

Eche un vistazo a net.sourceforge.nite.util.SortedList

Esta clase implementa una lista ordenada. Está construido con un comparador que puede comparar dos objetos y ordenar objetos en consecuencia. Cuando agrega un objeto a la lista, se inserta en el lugar correcto. Los objetos que son iguales según el comparador, estarán en la lista en el orden en que se agregaron a esta lista. Agregue solo objetos que el comparador pueda comparar.

Cuando la lista ya contiene objetos que son iguales según el comparador, el nuevo objeto se insertará inmediatamente después de estos otros objetos.

Answer 5

El enfoque de Aioobe es el camino a seguir. Sin embargo, me gustaría sugerir la siguiente mejora sobre su solución.

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
}
}

La solución de aioobe se vuelve muy lenta cuando se usan listas grandes. Usar el hecho de que la lista está ordenada nos permite encontrar el punto de inserción para nuevos valores usando la búsqueda binaria.

También usaría la composición sobre la herencia, algo parecido a

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

Answer 6

Las listas generalmente conservan el orden en que se agregan los elementos. ¿Definitivamente necesita una lista , o un conjunto ordenado (por ejemplo, TreeSet<E> ) estaría bien para usted? Básicamente, ¿necesita conservar duplicados?

Answer 7

Puede crear una subclase de ArrayList y llamar a Collections.sort (this) después de agregar cualquier elemento: deberá sobrescribir dos versiones de add y dos de addAll para hacerlo.

El rendimiento no sería tan bueno como una implementación más inteligente que inserta elementos en el lugar correcto, pero haría el trabajo. Si la adición a la lista es rara, el costo amortizado en todas las operaciones de la lista debe ser bajo.

Answer 8

Puede ser un poco demasiado pesado para usted, pero GlazedLists tiene una ca.odell.glazedlists.SortedList que es perfecta para usar como el modelo de una tabla o JList

Answer 9

Puedes probar TreeMultiSet Guava''s .

 Multiset<Integer> ms=TreeMultiset.create(Arrays.asList(1,2,3,1,1,-1,2,4,5,100));
System.out.println(ms);

Answer 10

Use java.util.PriorityQueue .

Answer 11

Yo tuve el mismo problema. Así que tomé el código fuente de java.util.TreeMap y escribí IndexedTreeMap . Implementa mi propio 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 implementación se basa en actualizar los pesos de los nodos en el árbol rojo-negro cuando se cambia. El peso es la cantidad de nodos secundarios debajo de un nodo dado, más uno mismo. Por ejemplo, cuando un árbol se gira hacia 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 encontrar el elemento por índice, aquí está la implementación que usa ponderaciones:

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 resulta muy útil encontrar el índice de una clave:

 public int keyIndex(K key) {
if (key == null) {
throw new NullPointerException();
}
Entry<K, V> e = getEntry(key);
if (e == null) {
throw new NullPointerException();
}
if (e == root) {
return getWeight(e) - getWeight(e.right) - 1;//index to return
}
int index = 0;
int cmp;
index += getWeight(e.left);
Entry<K, V> p = e.parent;
// split comparator and comparable paths
Comparator<? super K> cpr = comparator;
if (cpr != null) {
while (p != null) {
cmp = cpr.compare(key, p.key);
if (cmp > 0) {
index += getWeight(p.left) + 1;
}
p = p.parent;
}
} else {
Comparable<? super K> k = (Comparable<? super K>) key;
while (p != null) {
if (k.compareTo(p.key) > 0) {
index += getWeight(p.left) + 1;
}
p = p.parent;
}
}
return index;
}

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

TreeSet / TreeMap (así como sus contrapartes indexadas del proyecto indexed-tree-map) no permiten duplicar claves, puede usar 1 tecla para una matriz de valores. Si necesita un SortedSet con duplicados, utilice TreeMap con valores como matrices. Yo haria eso.