Come e quando abbandonare l'uso degli array in C#?

https://stackoverflow.com/questions/75976

09-06-2019
|

Domanda

Mi è sempre stato detto che l'aggiunta di un elemento a un array avviene in questo modo:

Viene creata una copia vuota dell'array+1Element e quindi vengono caricati i dati dall'array originale, quindi vengono caricati i nuovi dati per il nuovo elemento

Se ciò è vero, l'utilizzo di un array all'interno di uno scenario che richiede molta attività degli elementi è controindicato a causa dell'utilizzo della memoria e della CPU, giusto?

In tal caso, non dovresti cercare di evitare il più possibile l'utilizzo di un array quando aggiungerai molti elementi?Dovresti invece usare iStringMap?In tal caso, cosa succede se hai bisogno di più di due dimensioni E devi aggiungere molte aggiunte di elementi.Prendi solo il colpo in termini di prestazioni o c'è qualcos'altro che dovrebbe essere usato?

Soluzione

Guarda il generico List<T> in sostituzione degli array.Supportano la maggior parte delle stesse cose che fanno gli array, inclusa l'allocazione di una dimensione di archiviazione iniziale, se lo desideri.

Altri suggerimenti

Dipende davvero da cosa intendi per "aggiungere".

Se intendi:

T[] array;
int i;
T value;
...
if (i >= 0 && i <= array.Length)
    array[i] = value;

Quindi no, questo non crea un nuovo array ed è in effetti il modo più veloce per modificare qualsiasi tipo di IList in .NET.

Se, tuttavia, stai utilizzando qualcosa come ArrayList, List, Collection, ecc.quindi chiamando il metodo "Aggiungi". Maggio crea un nuovo array - ma sono intelligenti a riguardo, non si limitano a ridimensionarsi di 1 elemento, crescono geometricamente, quindi se aggiungi molti valori solo ogni tanto dovrà allocare un nuovo array .Anche in questo caso, puoi utilizzare la proprietà "Capacità" per forzarne la crescita in anticipo, se sai quanti elementi stai aggiungendo (list.Capacity += numberOfAddedElements)

In generale, preferisco evitare l'utilizzo dell'array.Basta usare List<T>.Utilizza internamente un array di dimensioni dinamiche ed è sufficientemente veloce per la maggior parte degli utilizzi.Se utilizzi array multidimensionali, utilizza List<List<List<T>>> se necessario.Non è molto peggio in termini di memoria ed è molto più semplice aggiungere elementi.

Se ti trovi nello 0,1% di utilizzo che richiede velocità estrema, assicurati che siano gli accessi all'elenco il vero problema prima di provare a ottimizzarlo.

Se aggiungerai/rimuoverai molti elementi, usa semplicemente un Elenco.Se è multidimensionale, puoi sempre utilizzare un List<List<int>> o qualcosa del genere.

D'altra parte, gli elenchi sono meno efficienti degli array se ciò che stai facendo principalmente è attraversamento l'elenco, perché gli array sono tutti in un unico posto nella cache della CPU, dove gli oggetti in un elenco sono sparsi ovunque.

Se desideri utilizzare un array per una lettura efficiente ma "aggiungerai" elementi frequentemente, hai due opzioni principali:

1) Generarlo come elenco (o elenco di elenchi) e quindi utilizzare ToArray() per trasformarlo in una struttura di array efficiente.

2) Assegna l'array in modo che sia più grande del necessario, quindi inserisci gli oggetti nelle celle preassegnate.Se finisci per aver bisogno di ancora più elementi di quelli pre-allocati, puoi semplicemente riallocare l'array quando si riempie, raddoppiando ogni volta la dimensione.Ciò fornisce prestazioni di ridimensionamento O(log n) invece di O(n) come sarebbe con un array riallocato una volta per aggiunta.Tieni presente che questo è più o meno il modo in cui funziona StringBuilder, offrendoti un modo più veloce per aggiungere continuamente a una stringa.

Quando abbandonare l'uso degli array

Innanzitutto, quando la semantica degli array non corrisponde al tuo intento - Hai bisogno di una collezione in crescita dinamica?Un set che non ammette duplicati?Una collezione che deve rimanere immutabile?Evita gli array in tutti questi casi.Questo è il 99% dei casi.Sto solo affermando l'ovvio punto fondamentale.
In secondo luogo, quando sei non codifica per la criticità assoluta delle prestazioni - Questo è circa il 95% dei casi. Gli array hanno prestazioni migliori marginalmente, soprattutto in iterazione.Quasi sempre non ha importanza.
Quando tu sei non costretto da una discussione con params parola chiave - Lo desideravo e basta params accettato qualsiasi IEnumerable<T> o meglio ancora un costrutto linguistico stesso per denotare a sequenza (e non un tipo di framework).
Quando sei non scrivere codice legacy o gestire l'interoperabilità

In breve, è molto raro che tu abbia effettivamente bisogno di un array.Aggiungerò perché si può evitarlo?

Il motivo principale per evitare gli array secondo me è concettuale.Gli array sono più vicini all'implementazione e più lontani dall'astrazione.Gli array trasmettono di più come è fatto di ciò che è fatto il che è contrario allo spirito dei linguaggi di alto livello.Ciò non sorprende, considerando che gli array sono più vicini al metallo, appartengono direttamente a un tipo speciale (sebbene internamente l'array sia una classe).Non per essere pedagogico, ma gli array si traducono davvero in un significato semantico richiesto molto molto raramente.La semantica più utile e frequente è quella di raccolte con qualsiasi voce, insiemi con elementi distinti, mappe di valori chiave ecc. con qualsiasi combinazione di varianti addizionabili, di sola lettura, immutabili e che rispettano l'ordine.Pensa a questo, potresti desiderare una raccolta aggiungibile o una raccolta di sola lettura con elementi predefiniti senza ulteriori modifiche, ma quanto spesso la tua logica assomiglia a "Voglio una raccolta aggiungibile dinamicamente ma solo un numero fisso di essi e dovrebbero essere anch'essi modificabili" "?Molto raro direi.

L'array è stato progettato durante l'era pre-generica e imita la genericità con molti hack di runtime e mostrerà le sue stranezze qua e là.Alcune delle catture che ho trovato:

Covarianza rotta.

string[] strings = ...
object[] objects = strings;
objects[0] = 1; //compiles, but gives a runtime exception.

Gli array possono darti un riferimento a una struttura!.È diverso da qualsiasi altro posto.Un campione:

struct Value { public int mutable; }

var array = new[] { new Value() };  
array[0].mutable = 1; //<-- compiles !
//a List<Value>[0].mutable = 1; doesnt compile since editing a copy makes no sense
print array[0].mutable // 1, expected or unexpected? confusing surely

Metodi implementati in fase di esecuzione come ICollection<T>.Contains può essere diverso per strutture e classi.Non è un grosso problema, ma se ti dimentichi di eseguire l'override non generico Equals correttamente per i tipi di riferimento che prevedono la ricerca di una raccolta generica generico Equals, otterrai risultati errati.

public class Class : IEquatable<Class>
{
    public bool Equals(Class other)
    {
        Console.WriteLine("generic");
        return true;
    }
    public override bool Equals(object obj)
    {
        Console.WriteLine("non generic");
        return true;
    } 
}

public struct Struct : IEquatable<Struct>
{
    public bool Equals(Struct other)
    {
        Console.WriteLine("generic");
        return true;
    }
    public override bool Equals(object obj)
    {
        Console.WriteLine("non generic");
        return true;
    } 
}

class[].Contains(test); //prints "non generic"
struct[].Contains(test); //prints "generic"

IL Length proprietà e [] indicizzatore attivo T[] sembrano essere proprietà regolari a cui puoi accedere attraverso la riflessione (il che dovrebbe comportare un po' di magia), ma quando si tratta di alberi delle espressioni devi sputare esattamente lo stesso codice del compilatore.Ci sono ArrayLength E ArrayIndex metodi per farlo separatamente.Uno di questi domanda qui.Un altro esempio:
```
Expression<Func<string>> e = () => new[] { "a" }[0];
//e.Body.NodeType == ExpressionType.ArrayIndex

Expression<Func<string>> e = () => new List<string>() { "a" }[0];
//e.Body.NodeType == ExpressionType.Call;
```

Come abbandonare l'uso degli array

Il sostituto più comunemente usato è List<T> che ha un'API più pulita.Ma è una struttura in crescita dinamica, il che significa che puoi aggiungere a List<T> alla fine o inserirlo ovunque a qualsiasi capacità.Non esiste alcun sostituto per il comportamento esatto di un array, ma le persone utilizzano principalmente gli array come raccolte di sola lettura in cui non è possibile aggiungere nulla alla fine.Un sostituto lo è ReadOnlyCollection<T>.Porto questo metodo di estensione:

public ReadOnlyCollection<T> ToReadOnlyCollection<T>(IEnumerable<T> source)
{
    return source.ToList().AsReadOnly();
}

Quando l'array viene ridimensionato, è necessario allocare un nuovo array e copiarne il contenuto.Se stai modificando solo il contenuto dell'array, si tratta solo di un'assegnazione di memoria.

Pertanto, non dovresti utilizzare gli array quando non ne conosci la dimensione o è probabile che la dimensione cambi.Tuttavia, se si dispone di un array a lunghezza fissa, rappresentano un modo semplice per recuperare gli elementi in base all'indice.

ArrayList e List aumentano l'array di più di uno quando necessario (penso che raddoppi la dimensione, ma non ho controllato la fonte).In genere rappresentano la scelta migliore quando si crea un array di dimensioni dinamiche.

Quando i tuoi benchmark indicano che il ridimensionamento dell'array sta rallentando seriamente la tua applicazione (ricorda: l'ottimizzazione prematura è la radice di tutti i mali), puoi valutare la scrittura di una classe di array personalizzata con un comportamento di ridimensionamento ottimizzato.

In generale, se è necessario avere le MIGLIORI prestazioni di ricerca indicizzata, è meglio creare prima una lista e poi trasformarla in un array, pagando così una piccola penalità all'inizio ma evitando di farlo in seguito.Se il problema è che aggiungerai continuamente nuovi dati e rimuoverai vecchi dati, potresti voler utilizzare un ArrayList o un Elenco per comodità, ma tieni presente che si tratta solo di array di casi speciali.Quando "crescono" allocano un array completamente nuovo e vi copiano tutto, il che è estremamente lento.

Lista di array è solo un array che cresce quando necessario.L'aggiunta è ammortizzata O(1), fai solo attenzione ad assicurarti che il ridimensionamento non avvenga in un brutto momento.Inserisci è O(n) tutti gli elementi a destra devono essere spostati.Rimuovi è O(n) tutti gli elementi a destra devono essere spostati.

È anche importante tenere presente che List non è un elenco collegato.È solo un ArrayList digitato.La lista documentazione nota che funziona meglio nella maggior parte dei casi ma non dice perché.

La cosa migliore da fare è scegliere una struttura dati adatta al tuo problema.Dipende da MOLTE cose e quindi potresti voler sfogliare il file System.Collections.Generic Spazio dei nomi.

In questo caso particolare direi che se riesci a trovare un buon valore chiave Dizionario sarebbe la soluzione migliore.Ha inserisci e rimuovi che si avvicina a O(1).Tuttavia, anche con un Dizionario devi stare attento a non lasciare che ridimensioni il suo array interno (un'operazione O(n)).È meglio concedere loro molto spazio specificando nel costruttore una capacità iniziale maggiore di quella che si prevede di utilizzare.

-Rick

Un array standard dovrebbe essere definito con una lunghezza, che riservi tutta la memoria di cui ha bisogno in un blocco contiguo.L'aggiunta di un elemento all'array lo collocherebbe all'interno del blocco di memoria già riservata.

Gli array sono ottimi per poche scritture e molte letture, in particolare quelle di natura iterativa; per qualsiasi altra cosa, utilizza una delle tante altre strutture dati.

Hai ragione, un array è ottimo per le ricerche.Tuttavia le modifiche alla dimensione dell'array sono costose.

Dovresti utilizzare un contenitore che supporti le modifiche incrementali delle dimensioni nello scenario in cui stai modificando la dimensione dell'array.Potresti utilizzare un ArrayList che ti consente di impostare la dimensione iniziale e potresti controllare continuamente la dimensione rispetto alla capacità e quindi incrementare la capacità di un grosso pezzo per limitare il numero di ridimensionamenti.

Oppure potresti semplicemente utilizzare un elenco collegato.Poi però le ricerche sono lente...

Questo post sul forum potrebbe o meno esserti utile per quanto riguarda l'efficienza di vari tipi di array:Array C#: multidimensionali e lessicografici

Se penso che aggiungerò molti elementi alla raccolta nel corso della sua vita, utilizzerò un elenco.Se so con certezza quale sarà la dimensione della raccolta quando verrà dichiarata, utilizzerò un array.

Un'altra volta in cui generalmente utilizzo un array su un elenco è quando devo restituire una raccolta come proprietà di un oggetto: non voglio che i chiamanti aggiungano elementi a quella raccolta tramite i metodi Aggiungi di Elenco, ma voglio invece che aggiungano elementi alla raccolta tramite l'interfaccia del mio oggetto.In tal caso, prenderò l'elenco interno, chiamerò ToArray e restituirò un array.

Se hai intenzione di fare molte aggiunte, E non eseguirai l'accesso casuale (come myArray[i]).Potresti prendere in considerazione l'utilizzo di un elenco collegato (LinkedList<T>), perché non dovrà mai "crescere" come il List<T> implementazione.Tieni presente, tuttavia, che puoi realmente accedere solo agli elementi in a LinkedList<T> implementazione utilizzando il IEnumerable<T> interfaccia.

La cosa migliore che puoi fare è allocare in anticipo tutta la memoria necessaria, se possibile.Ciò impedirà .NETTO dal dover effettuare chiamate aggiuntive per ottenere memoria nell'heap.In caso contrario, ha senso allocare in blocchi di cinque o qualsiasi numero abbia senso per la tua applicazione.

Questa è una regola che puoi applicare davvero a qualsiasi cosa.

Autorizzato sotto: CC-BY-SA insieme a attribuzione

Non affiliato a StackOverflow