Cómo hacer un conjunto ordenado con O (1) acceso aleatorio por índice

Question

Necesita una colección de cadenas donde los elementos insertados necesitan ser ordenados y también no duplicados, se puede recuperar a través del índice.

• puedo usar TreeSet que elimina los duplicados y ordena todo en orden pero no puede recuperar a través del índice. para recuperar a través del índice , puedo hacer elementos ArrayList y addAll, pero este addAll lleva mucho tiempo.

o

• puedo usar un ArrayList, inserto requerido y luego eliminar duplicados por algún otro método, y luego usando Collections.sort método para ordenar elementos.

Pero la cuestión es que todo esto lleva tiempo, ¿hay algún camino directo para lograr esto, una colección? Clasificada, no duplicada, con O (1) acceso aleatorio por índice.

Answer 1

Hay un tipo de datos en la colección commons llamado SetUniqueList que creo que cumple perfectamente con sus necesidades. Compruébelo usted mismo:

https://commons.apache.org/proper/commons-collections/apidocs/org/apache/commons/collections4/list/SetUniqueList.html

Answer 2

No estoy seguro, ¿prueba el mapa? Me refiero a usar su cadena como clave en un TreeMap.

En un mapa, es una O (1) para que una tecla encuentre su posición (un valor hash). Y KeySet de TreeMap devolverá un conjunto ordenado de claves en TreeMap.

¿Se ajusta esto a su requerimiento?

Answer 3

Usted puede utilizar la segunda idea:

puedo usar ArrayList, inserción deseada y eliminar duplicados por algún otro método , a continuación, utilizando el método Collections.sort para ordenar los elementos.

pero en lugar de eliminar los duplicados antes de la clase, se puede ordenar la ArrayList en primer lugar, a continuación, todos los duplicados en posiciones consecutivas y se puede retirar en una sola pasada después.

En este punto, ambos métodos tienen la misma complejidad general: O (N * logN) y vale la pena señalar que no se puede obtener una secuencia ordenada más rápido que esto de todos modos (sin explotación adicional de algunos conocimientos sobre los valores).

Answer 4

Si usted está limitado a la List al principio y al final de la operación, convertirlo en un Set con el constructor "copia" (o addAll) después de que los elementos están pobladas, esto elimina los duplicados. Si lo convierte en un TreeSet con un Comparator apropiado, incluso lo ordenará. Entonces, puede convertirlo nuevamente a List.

Answer 5

El rendimiento depende de con qué frecuencia se agregan los elementos y con qué frecuencia se accederá por índice.

Puedo usar TreeSet que elimina duplicados y ordena todo en orden pero no puede recuperar a través del índice. para recuperar a través del índice, puedo hacer elementos de arraylist y addall, pero este addAll toma mucho tiempo.

List.addAll (yourSortedSet) tendrá al menos O tiempo y el espacio (n) cada vez que desee acceder a la SortedSet como la lista (es decir, por el índice del elemento).

Puedo usar ArrayList, insertar como obligatorio y luego eliminar duplicados por algún otro método, luego usar el método Collections.sort para ordenar los elementos.

Sin duda la ordenación tomará más de O (n) cada vez que desee una vista ordenada de su lista.

Una solución más

Si no estás obteniendo por el índice muy a menudo, entonces es más eficiente de hacerlo de la siguiente manera:

tienda sólo String s en un SortedSet puede ser extender TreeSet y proporcione/implemente su propio método get(int i) donde itere hasta el i-ésimo elemento y devuelva ese elemento. En el peor de los casos, esto será O (n) por lo demás mucho menor. De esta manera usted es no realizando cualquier comparación o conversión o copia de cadenas. No se necesita espacio adicional.

Answer 6

Utilice un Hashmap para resolver problemas con valores únicos y ordenarlos por algunos de los métodos de clasificación. Si es posible, use quicksort.

Answer 7

Quizás usando LinkedList (que toma menos memoria que el arraylist) con el método booleano que determina si ese elemento ya está en la lista y un algoritmo QuickSort. Todas las estructuras en Java tienen que clasificarse y protegerse de duplicados de alguna manera, así que todo lleva su tiempo ...

Answer 8

El verdadero problema aquí es que el PO no nos ha dicho el verdadero problema. Entonces, mucha gente adivina las estructuras de datos y publica respuestas sin pensar realmente.

El verdadero síntoma, como el OP se indica en un comentario, es que se tarda 700ms para poner las cadenas en un TreeSet, y otros 700 ms para copiar que TreeSet en un ArrayList. Obviamente, el programa no está haciendo lo que el OP cree que es, ya que la copia debería tomar como máximo unos pocos microsegundos. De hecho, el siguiente programa, que se ejecuta en mi antiguo Thinkpad, requiere solo 360 ms para crear 100.000 cadenas aleatorias, colocarlas en un TreeSet y copiar ese TreeSet en ArrayList.

Dicho esto, el OP ha seleccionado una respuesta (dos veces). Tal vez si/cuando el OP decide pensar sobre el problema real, este ejemplo de un SSCCE será útil. Es CW, así que siéntete libre de editarlo.

---

import java.lang.management.ManagementFactory; 
import java.lang.management.ThreadMXBean; 
import java.util.ArrayList; 
import java.util.List; 
import java.util.Random; 
import java.util.TreeSet; 


public class Microbench 
{ 
    public static void main(String[] argv) 
    throws Exception 
    {   
     ThreadMXBean threadBean = ManagementFactory.getThreadMXBean(); 
     long start = threadBean.getCurrentThreadCpuTime(); 
     executeTest(); 
     long finish = threadBean.getCurrentThreadCpuTime(); 
     double elapsed = (finish - start)/1000000.0; 
     System.out.println(String.format("elapsed time = %7.3f ms", elapsed)); 
    } 


    private static List<String> executeTest() 
    { 
     String[] data = generateRandomStrings(100000); 

     TreeSet<String> set = new TreeSet<String>(); 
     for (String s : data) 
      set.add(s); 

     return new ArrayList<String>(set); 
    } 


    private static String[] generateRandomStrings(int size) 
    { 
     Random rnd = new Random(); 
     String[] result = new String[size]; 
     for (int ii = 0 ; ii < size ; ii++) 
      result[ii] = String.valueOf(rnd.nextLong()); 
     return result; 
    } 
} 

Answer 9

hay dos maneras de hacer que el uso LinkedMap que cada elemento de mapa es único o hacer su propia extensión de lista y método de reemplazo añadir

import java.util.ArrayList; 

public class MyList<V> extends ArrayList<V>{ 

    private static final long serialVersionUID = 5847609794342633994L; 

    public boolean add(V object) { 
     //make each object unique 
     if(contains(object)){ 
      return false; 
     } 

     //you can make here ordering and after save it at position 

     //your ordering here 

     //using extended method add 
     super.add(yourposition,object); 
    } 
} 

Answer 10

también me enfrenté al problema de encontrar elemento en una posición determinada en un TreeMap. Mejoré el árbol con pesos que permiten acceder a los elementos por índice y encontrar elementos en los índices. El proyecto se llama indexed-tree-map http://code.google.com/p/indexed-tree-map/. La implementación para encontrar el índice de un elemento o elemento en un índice en un mapa ordenado no se basa en la iteración lineal sino en una búsqueda binaria de árbol. La actualización de los pesos del árbol también se basa en el ascenso vertical del árbol. Entonces no hay iteraciones lineales.