Quando utilizzare un SortedList su un SortedDictionary ?

Questo potrebbe sembrare un duplicato di questa domanda , che chiede “Qual è la differenza tra SortedList e SortedDictionary ?” Sfortunatamente, le risposte non fanno altro che citare la documentazione MSDN (che afferma chiaramente che ci sono delle prestazioni e le differenze nell’uso della memoria tra i due) ma in realtà non rispondono alla domanda.

In effetti (e quindi questa domanda non ottiene le stesse risposte), secondo MSDN:

La class generica SortedList è un albero di ricerca binario con O (log n) retrieval, dove n è il numero di elementi nel dizionario. In questo, è simile alla class generica SortedDictionary . Le due classi hanno modelli di oggetti simili ed entrambi hanno il recupero di O (log n). Dove le due classi differiscono è nell’uso della memoria e nella velocità di inserimento e rimozione:

  • SortedList utilizza meno memoria di SortedDictionary .

  • SortedDictionary ha operazioni di inserimento e rimozione più veloci per i dati non ordinati, O (log n) in contrapposizione a O (n) per SortedList .

    • Se l’elenco viene popolato tutto in una volta dai dati ordinati, SortedList è più veloce di SortedDictionary .

    Quindi, chiaramente questo avrebbe indicato che SortedList è la scelta migliore a meno che non sia necessario inserire e rimuovere più rapidamente le operazioni per i dati non ordinati .

    La domanda rimane ancora, date le informazioni sopra quali sono le ragioni pratiche (mondo reale, business case, ecc.) Per usare un SortedDictionary ? In base alle informazioni sul rendimento, ciò implicherebbe che non è affatto necessario SortedDictionary .

    Non sono sicuro di quanto sia accurata la documentazione MSDN su SortedList e SortedDictionary . Sembra stia dicendo che entrambi sono implementati usando un albero di ricerca binario. Ma se SortedList utilizza un albero di ricerca binario, perché sarebbe più lento sulle aggiunte rispetto a SortedDictionary ?

    Ad ogni modo, ecco alcuni risultati dei test delle prestazioni.

    Ogni test funziona su SortedList / SortedDictionary contenente 10.000 chiavi int32. Ogni test viene ripetuto 1.000 volte (Release build, Start without Debugging).

    Il primo gruppo di test aggiunge chiavi in ​​sequenza da 0 a 9.999. Il secondo gruppo di test aggiunge chiavi casuali mescolate tra 0 e 9.999 (ogni numero viene aggiunto esattamente una volta).

     ***** Tests.PerformanceTests.SortedTest SortedDictionary Add sorted: 4411 ms SortedDictionary Get sorted: 2374 ms SortedList Add sorted: 1422 ms SortedList Get sorted: 1843 ms ***** Tests.PerformanceTests.UnsortedTest SortedDictionary Add unsorted: 4640 ms SortedDictionary Get unsorted: 2903 ms SortedList Add unsorted: 36559 ms SortedList Get unsorted: 2243 ms 

    Come per qualsiasi profilazione, l’importante è la performance relativa, non i numeri reali.

    Come puoi vedere, sui dati ordinati la lista ordinata è più veloce di SortedDictionary . Su dati non ordinati SortedList è leggermente più veloce nel recupero, ma circa 9 volte più lento all’aggiunta.

    Se entrambi utilizzano internamente gli alberi binari, è piuttosto sorprendente che l’operazione Aggiungi su dati non ordinati sia molto più lenta per SortedList . È ansible che la lista ordinata possa anche aggiungere elementi a una struttura di dati lineare ordinata allo stesso tempo, il che lo rallenterebbe.

    Tuttavia, ci si aspetterebbe che l’utilizzo della memoria di una SortedList sia uguale o superiore o almeno uguale a SortedDictionary . Ma questo contraddice ciò che dice la documentazione MSDN.

    Non so perché MSDN dice che SortedList usa un albero binario per la sua implementazione, perché se si guarda il codice con un decompilatore come Reflector capisci che non è vero.

    SortedList è semplicemente una matrice che cresce nel tempo.

    Ogni volta che inserisci un elemento, prima controlla se l’array ha una capacità sufficiente, in caso contrario, viene ricreato un array più grande e vengono copiati elementi vecchi (come List )

    Successivamente, cerca dove inserire l’elemento, utilizzando una ricerca binaria (ciò è ansible poiché l’array è indicizzabile e già ordinato).

    Per mantenere ordinato l’array, sposta (o spinge) tutti gli elementi situati dopo la posizione dell’elemento da inserire di una posizione (usando Array.Copy() ).

    Per esempio :

     // we want to insert "3" 2 4 <= 3 5 8 9 . . . // we have to move some elements first 2 . <= 3 4 5 | 8 v 9 . . 

    Questo spiega perché le prestazioni di SortedList sono così brutte quando si inseriscono elementi non ordinati. Deve ricalcare alcuni elementi quasi ogni inserimento. L'unico caso che non deve essere fatto è quando l'elemento deve essere inserito alla fine dell'array.

    SortedDictionary è diverso e usa un albero binario per inserire e recuperare elementi. Ha anche un costo di inserimento perché a volte l'albero deve essere riequilibrato (ma non ogni inserimento).

    Le prestazioni sono abbastanza simili durante la ricerca di un elemento con SortedList o SortedDictionary perché entrambi utilizzano una ricerca binaria.


    A mio parere, non dovresti mai usare SortedList per ordinare solo un array. A meno che tu non abbia pochi elementi, sarà sempre più veloce inserire i valori in una lista (o array) e quindi chiamare il metodo Sort() .

    SortedList è utile soprattutto quando hai un elenco di valori già ordinati (ad esempio: dal database), vuoi mantenerlo ordinato ed eseguire alcune operazioni che potrebbero avvantaggiarlo è ordinato (es .: il metodo Contains() di SortedList esegue una ricerca binaria invece di ricerca lineare)

    SortedDictionary offre gli stessi vantaggi di SortedList ma offre prestazioni migliori se i valori da inserire non sono già ordinati.


    EDIT: Se si utilizza .NET Framework 4.5, un'alternativa a SortedDictionary è SortedSet . Funziona allo stesso modo di SortedDictionary , usando un albero binario, ma le chiavi e i valori sono gli stessi qui.

    Sono pensati per due scopi diversi?

    Non c’è molta differenza semantica in questi due tipi di raccolta in .NET. Entrambi offrono una ricerca con chiave e mantengono le voci in ordine di chiavi. Nella maggior parte dei casi starai bene con entrambi. Forse l’unico SortedList differenziazione sarebbe il permesso di SortedList recupero indicizzato.

    Ma prestazioni?

    Tuttavia c’è una differenza di prestazioni che potrebbe essere un fattore più forte per scegliere tra di loro. Ecco una vista tabellare della loro complessità asintotica.

     +------------------+---------+----------+--------+----------+----------+---------+ | Collection | Indexed | Keyed | Value | Addition | Removal | Memory | | | lookup | lookup | lookup | | | | +------------------+---------+----------+--------+----------+----------+---------+ | SortedList | O(1) | O(log n) | O(n) | O(n)* | O(n) | Lesser | | SortedDictionary | n/a | O(log n) | O(n) | O(log n) | O(log n) | Greater | +------------------+---------+----------+--------+----------+----------+---------+ * Insertion is O(1) for data that are already in sort order, so that each element is added to the end of the list (assuming no resize is required). 

    Sommario

    Per riassumere sumriamente, si desidera un SortedList quando:

    1. hai bisogno di una ricerca indicizzata.
    2. è auspicabile avere un sovraccarico di memoria minore.
    3. i tuoi dati di input sono già ordinati (ad esempio hai già ordinato da db).

    Preferiresti invece preferire un SortedDictionary quando:

    1. le prestazioni generali relative sono importanti (rispetto al ridimensionamento).
    2. i tuoi dati di input non sono ordinati.

    Codice di scrittura

    Sia SortedList e SortedDictionary implementano IDictionary , quindi nel codice è ansible restituire IDictionary dal metodo o dichiarare variabile come IDictionary . In pratica nascondi i dettagli dell’implementazione e il codice contro l’interfaccia.

     IDictionary x = new SortedDictionary(); //for eg. 

    In futuro, è più facile passare da uno all’altro nel caso in cui non si è soddisfatti delle prestazioni caratteristiche di una collezione.


    Per maggiori informazioni sui due tipi di collezione, vedi la domanda originale collegata.

    Rappresentazione visiva delle differenze di prestazioni.

    inserisci la descrizione dell'immagine qui

    Questo è tutto ciò che c’è da fare. Il recupero delle chiavi è paragonabile, ma l’aggiunta è molto più veloce con i dizionari.

    Cerco di usare SortedList il più ansible perché mi permette di scorrere le chiavi e le collezioni di valore. Questo non è ansible con SortedDictionary per quanto ne so.

    Non ne sono sicuro, ma per quanto ne so i Dizionari archiviano i dati nelle strutture Tree, mentre i List memorizzano i dati in array lineari. Questo spiega perché l’inserimento e la rimozione sono molto più veloci con i dizionari, poiché è necessario spostare meno memoria. Spiega anche perché è ansible eseguire iterazioni su SortedList ma non SortedDictionary.