Cosa è più efficiente: Lista <T> .Add() o System.Array.Resize()?

Question

Sto cercando di determinare quando è più efficiente a List<T>.Add() rispetto al metodo Array.Resize().

La documentazione di Array.Resize dice che esegue una copia dell'intero array e lo inserisce in un nuovo oggetto. Il vecchio oggetto dovrebbe essere scartato. Dove risiede questo vecchio oggetto? Nello stack o nell'heap?

Non so come funziona List.Add().

Qualcuno sa come il metodo List.Add viene confrontato con il metodo statico Array.Resize?

Sono interessato all'utilizzo della memoria (e alla pulizia) e cosa è meglio per 300 tipi di valore, contro 20.000 tipi di valore.

Per quello che vale, sto pianificando di eseguire questo codice su uno dei sapori incorporati di .NET. Potenzialmente il .NET Gadgeteer

Answer 1

È necessario utilizzare un List<T>.

L'utilizzo di Array.Resize ti obbliga ad espandere l'array separatamente ogni volta che aggiungi un elemento, rendendo più lento il tuo codice . (poiché gli array non possono avere capacità di riserva)

A List<T> è supportato da un array, ma contiene una capacità inutilizzata per inserire gli elementi.
Tutto ciò che deve fare per aggiungere un elemento è impostare un elemento nell'array e aumentare il suo contatore interno size.
Quando l'array si riempie, l'elenco raddoppia la sua capacità, consentendo di aggiungere nuovamente elementi in modo semplice.

Answer 2

.NET Framework non supporta i generici, quindi utilizzerò un array, copiandolo e distruggendolo secondo necessità.

mi potrebbe paragonare che perfmance alla lista collegata srotolato menzionato nella biblioteca powertools qui: Any implementation of an Unrolled Linked List in C#?

Answer 3

.NET Micro Framework non (ancora) generici di supporto. Sei limitato per quanto riguarda le raccolte dinamiche.

Una cosa da considerare quando si sceglie il proprio approccio è che il codice gestito sul microcontrollore è molto, molto lento. Molte operazioni negli oggetti .NET Micro Framework gestiti sono in realtà solo chiamate in codice nativo per eseguire il lavoro. Questo è molto più veloce.

Ad esempio, confrontare la copia di un elemento di una matrice per elemento in un ciclo for contro la chiamata di Array.Copy() che essenzialmente fa la stessa cosa ma nel codice nativo.

Ove possibile, utilizzare queste estensioni native per ottenere prestazioni migliori. Considera anche di dare un'occhiata allo MicroLinq project su CodePlex. Esiste un sottoprogetto dedicato solo alle raccolte avanzate su NETMF (disponibile anche come NuGet package). Il codice è disponibile gratuitamente e concesso in licenza per qualsiasi scopo. (Completa divulgazione: sono lo sviluppatore di questo progetto.)

Se riesci a superare l'allocazione di un array di grandi dimensioni e tenere traccia della posizione massima in cui sono stati salvati i dati reali, questo sarebbe il più veloce ma richiede più lavoro/pensiero messo nel design e toglie tempo alla costruzione di cose interessanti.

Answer 4

L'elenco sarà più veloce se si ridimensiona l'array frequentemente, ad esempio ogni volta che si aggiunge un elemento. Tuttavia, se la ridimensionate ogni pochi fotogrammi, l'elenco e gli array incorporati dovrebbero essere equivalenti, forse gli array ancora più veloci.

Answer 5

Ho visto l'implementazione Elenco dopo la decompilazione e ho scoperto che utilizza Array.Resize() per l'array interno. Ma gestisce il contatore di elementi e utilizza la lunghezza dell'array come capacità e ridimensiona l'array con uno spazio extra quando si chiama Add(). Quindi, suppongo che tu possa sviluppare una strategia di allocazione più ottimale rispetto a List for your case. Ma dovrai gestire il contatore degli elementi manualmente. Inoltre, si eliminerà l'overhead degli indicizzatori durante l'accesso agli elementi dell'array, perché gli indicizzatori all'interno di List sono solo metodi che richiedono elementi di array interni. Penso che valga la pena sostituire List by array con ridimensionamento manuale se è solo un collo di bottiglia.