LinkedList, HashSet, LinkedHashSet, ecc...

[peruzzo]

Codice:

// Demonstrate ArrayList. 
import java.util.*; 
 
class ArrayListDemo { 
  public static void main(String args[]) { 
    // Create an array list. 
    ArrayList<String> al = new ArrayList<String>(); 
     
    System.out.println("Initial size of al: " + 
                       al.size()); 
 
    // Add elements to the array list. 
    al.add("C"); 
    al.add("A"); 
    al.add("E"); 
    al.add("B"); 
    al.add("D"); 
    al.add("F"); 
    al.add(1, "A2"); 
 
    System.out.println("Size of al after additions: " + 
                       al.size()); 
 
    // Display the array list. 
    System.out.println("Contents of al: " + al); 
 
    // Remove elements from the array list. 
    al.remove("F"); 
    al.remove(2); 
 
    System.out.println("Size of al after deletions: " + 
                       al.size()); 
    System.out.println("Contents of al: " + al); 
  } 
}

Il manuale inizia con un lungo elenco di classi però vorrei riassumere un pochetto cercando di capire quale conviene usare a seconda dei casi quando si usa il metodo add().

1-ArrayList per esempio con add() mette in ordine di inserimento i valori ma è lento.
2-LinkedList mette in ordine ed è lento quindi non capisco la differenza rispetto al precedente.
3-HashSet non mette in ordine ma è veloce (in realtà non è più veloce ma è sempre ugualmente veloce all'aumentare della dimensione della collection... ho riassunto per capirci... e per non farne un messale...)
4-LinkedHashSed non c'è scritto se è veloce o se è lento ma funziona come i primi 2 (la confusione diventa sempre più grande)
5-TreeSet mette in ordine crescente ma non si capisce se sia veloce o lento (penso lento ma non saprei).
6-ArrayDeque: sul testo c'é scritta una frase incomprensibile:
(l'interfaccia Deque supporta implementazioni che limitano la capacità, ma non tali limitazioni non sono necessarie)
7-EnumSet invece si usa per le enumerazioni.

[Alex'87]

Originariamente inviato da peruzzo
1-ArrayList per esempio con add() mette in ordine di inserimento i valori ma è lento.

No. ArrayList memorizza i suoi elementi in un semplice array per cui l'accesso e la lettura sono diretti e costano O(1).
Problema 1: essendo l'array non infinito, prima o poi bisogna allargarlo e ricopiarci dentro i valori precedenti.
Problema 2: la cancellazione. Se cancelli il primo elemento di un ArrayList di 100000 di elementi, tutti gli elementi devono essere spostati a sinistra di uno.

Originariamente inviato da peruzzo
2-LinkedList mette in ordine ed è lento quindi non capisco la differenza rispetto al precedente.

LinkedList non usa un array ma ogni elemento è un "nodo" collegato al nodo precedente e a quello successivo.
Problema: se devo inserire un elemento in posizione i devo prima scorrerla fino ad i. Costa O(n).
Vantaggi: la cancellazione non deve spostare nulla, solo cambiare due puntatori, costa sempre O(n)

Originariamente inviato da peruzzo
5-TreeSet mette in ordine crescente ma non si capisce se sia veloce o lento (penso lento ma non saprei).

TreeSet ordina man mano che inserisci gli elementi usando un Comparator, di default usa un ordine crescente. E' veloce nelle operazioni base, costa log(n)

Originariamente inviato da peruzzo
6-ArrayDeque: sul testo c'é scritta una frase incomprensibile:
(l'interfaccia Deque supporta implementazioni che limitano la capacità, ma non tali limitazioni non sono necessarie)

La documentazione è chiara, la traduzione automatica magari no

Più o meno sarebbe "ArrayDeque non ha restrizioni sulla capacità: cresce quel che serve ecc ecc"

[MItaly]

Sono tutte strutture dati standard dell'informatica, di cui trovi dovunque (=Wikipedia) le caratteristiche di performance (ma devi essere un po' familiare con la notazione dell'"O grande"); di seguito un minimo di glossario per orientarti sulle risorse che si trovano (a palate) su internet:

ArrayList = Array dinamico
LinkedList = Doubly-linked list (lista doppiamente collegata)
ArrayDeque = è una double-eneded queue basata su un array; i metodi per implementarla variano.

I vari "*Set" in genere sono in un certo senso la versione di container associativi (tipo dizionario) in cui chiave e valore coincidono.
HashSet = Hashtable in cui la chiave e il valore relativo corrispondono
LinkedHashSet = un HashSet e una linked list "sincronizzate", l'HashSet gestisce la memorizzazione degli elementi, la linked list memorizza l'ordinamento degli elementi
TreeSet = è un albero binario (apparentemente un red-black tree), anche qui con chiave e valore che coincidono
La stessa documentazione specifica che questi ultimi tre sono proprio basati sulle loro controparti associative (HashMap, LinkedHashMap, TreeMap).

L'EnumSet è un caso particolare, di fatto è un bitset.

---

A differenza di JNI , queste ti conviene studiartele bene - è fondamentale conoscere le principali strutture dati normalmente utilizzate, i loro utilizzi tipici, punti di forza e punti deboli e avere un'idea di come possono essere implementate - specie perché la loro applicabilità va ben al di là di Java in sé (sono cose che si usano in ogni linguaggio).

[peruzzo]

Qualcuno mi spiega come interpretare O(1) oppure O(n) cioè mi basta sapere il significato spicciolo. Dimenticavo... anche log(n) ma sempre solo per capire se una cosa è più veloce di un'altra e quindi poter fare un confronto...

[MItaly]

Cosa sai di analisi matematica?

[schumy2000]

Più che altro che studi hai fatto?

[peruzzo]

Originariamente inviato da MItaly
Cosa sai di analisi matematica?

Analisi matematica la conosco bene! Dimmi pure quello che hai in testa ma ricorca che a me interessa capire quello che Alex'87 voleva dire con quei simboli: NIENTE ALTRO!

[oregon]

Originariamente inviato da peruzzo
Analisi matematica la conosco bene!

E chiedi spiegazioni su log(n) ?

Scusa ma seguo questi tuoi thread perché mi sembrano sempre un po' strani oltre che dispersivi ... cosa c'entra log, O e altro con LinkedList e altro ?

Non si può parlare di tutto e di più in un thread in un forum solo perché la gente è disponibile ...

Per questo ci sono, nell'ordine, la scuola, l'università, i corsi di specializzazione ...

[peruzzo]

Sempre nell’ottica di Alex'87 nel voler descrivere queste classi che mi piace un sacco perché dice in soldoni quello che bisogna sapere (davvero molto bravo, bisogna ammetterlo, ha centrato in pieno la mia domanda) è giusto dire:
“HashSet sostituisce all’indice del vettore il valore associato a quella precisa chiava trasformandolo prima in codice hash, in questo modo si perde l’indice dell’array ovvero si ottiene una collection non ordinabile (QUESTO E’ UN PROBLEMA) ma si ha un accesso più rapido agli elementi di un vettore perché il confronto di codici hash è veloce, ovvero faccio prima a verificare la presenza di un elemento all’interno di un vettore (QUESTO E’ UN VANTAGGIO), è faccio prima ad aggiungere elementi perché HashSet non è un array dinamico ma una lista senza indice e quindi l’inserimento di nuovi valori avviene senza dover scorrere tutto il vettore (QUESTO E’ UN VETTORE).”
“HashSetList è simile ad HashSet ma ad ogni entità del vettore (valore + codice hash al posto dell’indice) ha anche una lista che ne permette l’indicizzazione come in un array semplice. PROBLEMA: Se devo inserire un elemento in posizione i devo scorrere fino ad i. VANTAGGIO: A differenza di LinkedList impiego meno tempo a cercare valori in un array perché posso confrontare codici hash invece di valori stringa.”
In pratica se ho capito bene HashSetList è migliore di LinkedList in tutto, HashSet è più rapido ma ha funzioni in meno e ArrayList è una ciofecca che di comando che non serve a un tubo. Alla fine, gira che ti rigira il migliore resta sempre HashSetList.
Potete correggere e riformulare se ho dedotto male.

[peruzzo]

Originariamente inviato da oregon
E chiedi spiegazioni su log(n) ?

Scusa ma seguo questi tuo thread perché mi sembrano sempre un po' strani oltre che dispersivi ... cosa c'entra log, O e altro con LinkedList e altro ?

Non si può parlare di tutto e di più in un thread in un forum solo perché la gente è disponibile ...

Per questo ci sono, nell'ordine, la scuola, l'università, i corsi di specializzazione ...

Che cavolo é "n" non log!
Volete escludermi perché non ho una laurea! Grazie, sei davvero gentile ed educato!
Poi non ho chiesto nulla di trascendentale ma solo capire quale e quando un metodo è più veloce di un altro! Siete voi che vi siete messi a parlare di "O" e di "n".