SortedList < > ;, SortedDictionary < > e dizionario < >

StackOverflow https://stackoverflow.com/questions/1427147

Domanda

Trovo che SortedList < TKey, TValue > SortedDictionary < TKey, TValue > e Dictionary < TKey, TValue > implementano le stesse interfacce .

  1. Quando dovremmo optare per SortedList e SortedDictionary su Dizionario ?
  2. Qual è la differenza tra SortedList e SortedDictionary in termini di applicazione?
È stato utile?

Soluzione

  1. Quando si ripetono gli elementi in uno dei due, gli elementi verranno ordinati. Non così con Dictionary<T,V>.

  2. MSDN risolve la differenza tra SortedList < ; T, V > e SortedDictionary < T, V > :

  

La classe generica SortedDictionary (TKey, TValue) è una ricerca binaria   albero con recupero O (log n), dove n è il numero di elementi in   il dizionario. A questo proposito, è simile a SortedList (TKey,   TValue) classe generica. Le due classi hanno modelli di oggetti simili e   entrambi hanno il recupero O (log n). Dove si trovano le due classi diverse   utilizzo della memoria e velocità di inserimento e rimozione:

     

SortedList (TKey, TValue) utilizza meno memoria di SortedDictionary (TKey,   TValue).

     

SortedDictionary (TKey, TValue) ha inserimento e rimozione più rapidi   operazioni per dati non ordinati: O (log n) rispetto a O (n) per   SortedList (TKey, TValue).

     

Se l'elenco viene popolato tutto in una volta dai dati ordinati,   SortedList (TKey, TValue) è più veloce di SortedDictionary (TKey,   TValue).

Altri suggerimenti

inserisci qui la descrizione dell'immagine

Vorrei citare la differenza tra i dizionari.

L'immagine qui sopra mostra che Dictionary < K, V > è uguale o più veloce in ogni caso rispetto all'analogo Sorted , ma se è richiesto l'ordine degli elementi, ad es. per stamparli, Ordinati ne viene scelto uno

Src: http: // people.cs.aau.dk/~normark/oop-csharp/html/notes/collections-note-time-complexity-dictionaries.html

Riassumendo i risultati di un Test delle prestazioni - SortedList vs. SortedDictionary vs. Dizionario vs. Hashtable , i risultati dalla migliore alla peggiore per diversi scenari:

Utilizzo della memoria: 

SortedList<T,T>
Hashtable
SortedDictionary<T,T>
Dictionary<T,T>

inserimenti: 

Dictionary<T,T>
Hashtable
SortedDictionary<T,T>
SortedList<T,T>

Operazioni di ricerca: 

Hashtable
Dictionary<T,T>
SortedList<T,T>
SortedDictionary<T,T>

Operazioni foreach loop 

SortedList<T,T>
Dictionary<T,T>
Hashtable
SortedDictionary<T,T>

  1. Quando si desidera che la raccolta venga ordinata per chiave quando si esegue l'iterazione su di essa. Se non hai bisogno di ordinare i tuoi dati, stai meglio con solo un dizionario, avrà prestazioni migliori.

  2. SortedList e SortedDictionary fanno praticamente la stessa cosa, ma sono implementati in modo diverso, quindi hanno diversi punti di forza e di debolezza spiegato qui .

Vedo che le risposte proposte si concentrano sulle prestazioni. L'articolo fornito di seguito non fornisce nulla di nuovo riguardo alle prestazioni, ma spiega i meccanismi sottostanti. Si noti inoltre che non si concentra sui tre tipi Collection citati nella domanda, ma riguarda tutti i tipi dello spazio dei nomi System.Collections.Generic .

http://geekswithblogs.net/BlackRabbitCoder/archive/2011/06/16/c.net-fundamentals-choosing-the-right-collection-class.aspx

Estratti:

Dictionnary < >

  

Il dizionario è probabilmente la classe contenitore associativa più utilizzata. Il dizionario è la classe più veloce per ricerche associative / inserti / eliminazioni perché utilizza una tabella hash sotto le copertine . Poiché le chiavi sono sottoposte a hash, il tipo di chiave dovrebbe implementare correttamente GetHashCode () e Equals () in modo appropriato o dovresti fornire un IEqualityComparer esterno al dizionario durante la costruzione. Il tempo di inserimento / eliminazione / ricerca degli elementi nel dizionario è tempo costante ammortizzato - O (1) - il che significa non importa quanto sia grande il dizionario, il tempo impiegato per trovare qualcosa rimane relativamente costante. Questo è altamente desiderabile per le ricerche ad alta velocità. L'unico aspetto negativo è che il dizionario, per natura dell'uso di una tabella hash, non è ordinato, quindi non è possibile attraversare facilmente gli elementi in un dizionario in ordine .

SortedDictionary < >

  

SortedDictionary è simile al Dizionario in uso ma molto diverso nell'implementazione. SortedDictionary utilizza un albero binario sotto le copertine per mantenere gli elementi in ordine tramite la chiave . Come conseguenza dell'ordinamento, il tipo utilizzato per la chiave deve implementare correttamente IComparable in modo che le chiavi possano essere ordinate correttamente. Il dizionario ordinato scambia un po 'di tempo di ricerca per la capacità di mantenere gli elementi in ordine, quindi i tempi di inserimento / cancellazione / ricerca in un dizionario ordinato sono logaritmici - O (log n). In generale, con il tempo logaritmico, è possibile raddoppiare le dimensioni della raccolta e per trovare l'oggetto è sufficiente eseguire un ulteriore confronto. Usa SortedDictionary quando vuoi ricerche veloci ma vuoi anche essere in grado di mantenere la raccolta in ordine dalla chiave.

SortedList < >

  

SortedList è l'altra classe contenitore associativa ordinata nei contenitori generici. Ancora una volta SortedList, come SortedDictionary, utilizza una chiave per ordinare le coppie chiave-valore . A differenza di SortedDictionary, tuttavia, gli elementi in un SortedList vengono archiviati come array ordinati di elementi . Ciò significa che gli inserimenti e le eliminazioni sono lineari - O (n) - poiché l'eliminazione o l'aggiunta di un elemento può comportare lo spostamento di tutti gli elementi in alto o in basso nell'elenco. Il tempo di ricerca, tuttavia, è O (log n) poiché SortedList può utilizzare una ricerca binaria per trovare qualsiasi elemento nell'elenco mediante la sua chiave. Quindi perché mai vorresti farlo? Bene, la risposta è che se caricherai la SortedList in anticipo, gli inserimenti saranno più lenti, ma poiché l'indicizzazione dell'array è più veloce rispetto ai seguenti collegamenti agli oggetti, le ricerche sono leggermente più veloci di un SortedDictionary. Ancora una volta lo userei in situazioni in cui desideri ricerche rapide e desideri mantenere la raccolta in ordine tramite la chiave e in cui inserimenti ed eliminazioni sono rari.

Riepilogo provvisorio delle procedure sottostanti

Il feedback è molto gradito in quanto sono sicuro di non aver fatto tutto bene.

  • Tutti gli array hanno dimensioni n .
  • Matrice non ordinata = .Add / .Remove è O (1), ma .Item (i) è O (n).
  • Matrice ordinata = .Add / .Remove è O (n), ma .Item (i) è O (1).

Dictionnary

Memory

KeyArray (n) - > array non ordinato < pointer >
ItemArray (n) - > array non ordinato < pointer >
HashArray (n) - > array ordinato < hashvalue >

Aggiungi

  1. Aggiungi HashArray (n) = Key.GetHash # O (1)
  2. Aggiungi KeyArray (n) = PointerToKey # O (1)
  3. Aggiungi ItemArray (n) = PointerToItem # O (1)

Rimuovi

  1. Per i = da 0 a n , trova i dove HashArray (i) = Key.GetHash # O (registro n) (ordinato array)
  2. Rimuovi HashArray (i) # O (n) (matrice ordinata)
  3. Rimuovi KeyArray (i) # O (1)
  4. Rimuovi ItemArray (i) # O (1)

Ottieni oggetto

  1. Per i = da 0 a n , trova i dove HashArray (i) = Key.GetHash # O (registro n) (ordinato array)
  2. Restituisce ItemArray(i)

Passa attraverso

  1. Per i = da 0 a n , restituisce ItemArray(i)

SortedDictionary

Memory

KeyArray (n) = array non ordinato < pointer >
ItemArray (n) = array non ordinato < pointer >
OrderArray (n) = array ordinato < pointer >

Aggiungi

  1. Aggiungi KeyArray (n) = PointerToKey # O (1)
  2. Aggiungi ItemArray (n) = PointerToItem # O (1)
  3. Per i = da 0 a n , trova i dove KeyArray (i-1) < Chiave < KeyArray (i) (utilizzando ICompare ) # O (n)
  4. Aggiungi OrderArray (i) = n # O (n) (array ordinato)

Rimuovi

  1. Per i = 0 a n , trova i dove KeyArray (i) .GetHash = Key.GetHash # O (n)
  2. Rimuovi KeyArray (SortArray (i)) # O (1)
  3. Rimuovi ItemArray (SortArray (i)) # O (1)
  4. Rimuovi OrderArray (i) # O (n) (array ordinato)

Ottieni oggetto

  1. Per i = 0 a n , trova i dove KeyArray (i) .GetHash = Key.GetHash # O (n)
  2. Restituisce ItemArray(i)

Passa attraverso

  1. Per i = da 0 a n , restituisce ItemArray(OrderArray(i))

SortedList

Memory

KeyArray (n) = array ordinato < pointer >
ItemArray (n) = array ordinato < pointer >

Aggiungi

  1. Per i = da 0 a n , trova i dove KeyArray (i-1) < Chiave < KeyArray (i) (utilizzando ICompare ) # O (log n)
  2. Aggiungi KeyArray (i) = PointerToKey # O (n)
  3. Aggiungi ItemArray (i) = PointerToItem # O (n)

Rimuovi

  1. Per i = 0 a n , trova i dove KeyArray (i) .GetHash = Key.GetHash # O (registro n)
  2. Rimuovi KeyArray (i) # O (n)
  3. Rimuovi ItemArray (i) # O (n)

Ottieni oggetto

  1. Per i = 0 a n , trova i dove KeyArray (i) .GetHash = Key.GetHash # O (registro n)
  2. Restituisce ItemArray(i)

Passa attraverso

  1. Per i = da 0 a n , restituisce ItemArray(i)

Cercando di assegnare un punteggio di rendimento a ciascun caso presentato da @Lev, ho usato i seguenti valori:

  • O (1) = 3
  • O (registro n) = 2
  • O (n) = 1
  • O (1) o O (n) = 2
  • O (log n) o O (n) = 1.5

I risultati sono (più alto = migliore): 

Dictionary:       12.0 
SortedDictionary:  9.0 
SortedList:        6.5

Ovviamente, ogni caso d'uso darà più peso a determinate operazioni.

Autorizzato sotto: CC-BY-SA insieme a attribuzione
Non affiliato a StackOverflow
scroll top