Come creare un set ordinato con un accesso casuale O (1) per indice

Question

È necessario recuperare una raccolta di stringhe in cui gli elementi inseriti devono essere ordinati e anche non duplicati, tramite indice.

• posso usare TreeSet che elimina i duplicati e ordina tutto in ordine ma non in grado di recuperare attraverso indice. per il recupero tramite l'indice , posso creare gli elementi ArrayList e addAll, ma questo addAll richiede molto tempo.

o

• posso usare un ArrayList, inserto necessario quindi rimuovere duplicati da un altro metodo, quindi utilizzando Collections.sort metodo per ordinare gli elementi.

Ma la cosa è, tutti questi richiedono tempo, non v'è alcun diritto-modo per raggiungere questo obiettivo, una collezione -sorted, non duplicate, con O (1) accesso casuale in base all'indice.

Answer 1

C'è un tipo di dati nella raccolta di comuni denominata SetUniqueList che credo soddisfi perfettamente le tue esigenze. Check it out:

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

Answer 2

Non sono sicuro, testate la mappa? Voglio dire usare la stringa come chiave in una TreeMap.

In una mappa, è un O (1) per una chiave per trovare la sua posizione (un valore hash). E KeySet di TreeMap restituirà un insieme ordinato di chiavi in ​​TreeMap.

Questo soddisfa le vostre esigenze?

Answer 3

È possibile utilizzare la seconda idea:

posso usare ArrayList, inserto richiesto e poi rimuovere i duplicati da qualche altro metodo, quindi utilizzando il metodo Collections.sort per ordinare gli elementi.

ma invece di rimuovere i duplicati prima del genere, è possibile ordinare il ArrayList prima, poi tutti i duplicati sono in posizioni consecutive e possono essere rimossi in una sola passata successivamente.

A questo punto, entrambi i metodi hanno la stessa complessità complessiva: O (N * logN) e vale la pena notare che non è possibile ottenere una sequenza ordinata più veloce di questa comunque (senza ulteriore sfruttamento di una certa conoscenza dei valori).

Answer 4

Se si sono tenuti alla List all'inizio e alla fine dell'operazione, convertirlo in un Set con il costruttore "copia" (o addAll) dopo gli elementi sono popolati, questo elimina i duplicati. Se lo converti in un TreeSet con uno Comparator appropriato, lo risolve persino. Di conseguenza, è possibile convertirlo nuovamente in List.

Answer 5

Le prestazioni dipendono dalla frequenza con cui gli elementi vengono aggiunti e dalla frequenza con cui saranno accessibili per indice.

Posso usare TreeSet che rimuove i duplicati e ordina tutto in ordine ma non può recuperare tramite indice. per il recupero tramite indice, posso creare arraylist e aggiungere elementi ad esso, ma questo addAll richiede molto tempo.

List.addAll (yourSortedSet) avrà atleast O (n) tempo e spazio ogni volta che si desidera accedere al SortedSet come elenco (cioè dall'indice di elemento).

Posso usare ArrayList, inserire richiesto e quindi rimuovere i duplicati con un altro metodo, quindi utilizzando il metodo Collections.sort per ordinare gli elementi.

l'ordinamento richiederà sicuramente più di O (n) ogni volta che si desidera una visualizzazione ordinata dell'elenco.

Un'altra soluzione

Se non si recuperano con l'indice molto spesso, allora è più efficiente di farlo nel modo seguente:

Basta memorizzare String s in un SortedSet può essere estendere TreeSet e fornire/implementare il proprio metodo get(int i) in cui si itera fino all'elemento ith e si restituisce quell'elemento. Nel peggiore dei casi, questo sarà O (n) altrimenti molto meno. In questo modo sei non eseguendo alcun confronto o conversione o copia di stringhe. Non è necessario spazio extra.

Answer 6

Utilizzare un Hashmap per risolvere il problema con valori univoci e ordinarlo con alcuni metodi di ordinamento. Se è possibile utilizzare quicksort.

Answer 7

Forse usando LinkedList (che richiede meno memoria dell'array) con il metodo booleano che determina se quell'elemento è già presente nell'elenco e un algoritmo QuickSort. Tutte le strutture di java devono essere in qualche modo ordinate e protette dai duplicati, quindi tutto richiede tempo ...

Answer 8

Il vero problema qui è che il PO non ci ha detto il vero problema. Quindi molte persone indovinano le strutture dati e postano le risposte senza pensarci veramente.

Il vero sintomo, come l'OP ha dichiarato in un commento, è che ci vuole 700ms a mettere le corde in un TreeSet, e un altro 700 ms per copiare che TreeSet in un ArrayList. Ovviamente, il programma non sta facendo quello che l'OP pensa che sia, dato che la copia dovrebbe richiedere al massimo qualche microsecondo. In effetti, il programma seguente, eseguito sul mio vecchio Thinkpad, impiega solo 360 ms per creare 100.000 stringhe casuali, metterle in un TreeSet e copiare TreeSet in una ArrayList.

Detto questo, l'OP ha selezionato una risposta (due volte). Forse se/quando l'OP decide di pensare al vero problema, questo esempio di SSCCE sarà utile. È CW, quindi sentitevi liberi di modificarlo.

---

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

ci sono due modi per farlo LinkedMap uso dove ogni elemento nella mappa è unico o rendere la propria estensione della lista e metodo di sostituzione aggiungere

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

ho anche affrontato il problema della trovare elementi in una determinata posizione in una TreeMap. Ho migliorato l'albero con pesi che consentono di accedere agli elementi per indice e trovare elementi negli indici. Il progetto si chiama indexed-tree-map http://code.google.com/p/indexed-tree-map/. L'implementazione per trovare l'indice di un elemento o elemento in un indice in una mappa ordinata non è basata su iterazione lineare ma su una ricerca binaria ad albero. L'aggiornamento dei pesi dell'albero si basa anche sulla salita verticale dell'albero. Quindi nessuna iterazione lineare.