Wie und wann sollte auf die Verwendung von Arrays in C# verzichtet werden?

https://stackoverflow.com/questions/75976

09-06-2019
|

Frage

Mir wurde immer gesagt, dass das Hinzufügen eines Elements zu einem Array so abläuft:

Eine leere Kopie des Array+1Elements wird erstellt, und dann werden die Daten aus dem ursprünglichen Array in sie kopiert, dann werden die neuen Daten für das neue Element dann geladen

Wenn dies zutrifft, ist die Verwendung eines Arrays in einem Szenario, das viele Elementaktivitäten erfordert, aufgrund der Speicher- und CPU-Auslastung kontraindiziert, richtig?

Wenn das der Fall ist, sollten Sie dann nicht versuchen, die Verwendung eines Arrays so weit wie möglich zu vermeiden, wenn Sie viele Elemente hinzufügen?Sollten Sie stattdessen iStringMap verwenden?Wenn ja, was passiert, wenn Sie mehr als zwei Dimensionen benötigen UND viele Elementzusätze hinzufügen müssen?Nehmen Sie einfach den Leistungseinbruch in Kauf oder gibt es etwas anderes, das verwendet werden sollte?

Lösung

Sehen Sie sich die allgemeine List<T> als Ersatz für Arrays. Sie unterstützen die meisten die gleichen Dinge tun Arrays, einschließlich einer anfängliche Speichergröße Zuteilung, wenn Sie wollen.

Andere Tipps

Das hängt davon ab, was Sie unter „hinzufügen.“

Wenn Sie nach:

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

Dann nein, das nicht ein neues Array schafft, und ist in-die Tat den schnellsten Weg, um jede Art von IList in .NET zu ändern.

Wenn jedoch Sie mit so etwas wie Arraylist, List, Sammlung, usw. dann die Schaltfläche „Hinzufügen“ Methode aufrufen können ein neues Array erstellen - aber sie sind über es klug, sie nicht nur um 1 Element Größe verändern, wachsen sie geometrisch, also, wenn Sie viele Werte nur jeder einmal in eine Weile Zugabe wird es ein neues Array zuweisen müssen. Selbst dann können Sie die „Kapazität“ Eigenschaft verwenden, um es vor der Hand zu wachsen zu zwingen, wenn Sie wissen, wie viele Elemente Sie hinzufügen (list.Capacity += numberOfAddedElements)

Im Allgemeinen ziehe ich Array Nutzung zu vermeiden. Verwenden Sie einfach List . Es verwendet ein dynamisch-sized Array intern und ist schnell genug für die meisten Nutzung. Wenn Sie Multi-dimentional Arrays verwenden, verwenden List >> wenn Sie müssen. Es ist nicht so viel schlechter in Bezug auf Speicher und ist viel einfacher fügen Sie Artikel zu.

Wenn Sie in dem 0,1% des Verbrauches sind, die extreme Geschwindigkeit erfordert, stellen Sie sicher, dass es Ihre Liste zugreift, die wirklich das Problem ist, bevor Sie versuchen, es zu optimieren.

Wenn Sie vorhaben, werden das Hinzufügen / Entfernen von Elementen viel, benutzen Sie einfach eine Liste. Wenn es mehrdimensional ist, können Sie immer eine Liste mit > oder so etwas.

Auf der anderen Seite, sind Listen weniger effizient als Arrays, wenn, was Sie meistens tun ist durchlaufen die Liste, weil Arrays an einem zentralen Ort in Ihren CPU-Cache ist, wo Objekte in einer Liste sind überall verstreut.

Wenn Sie ein Array für effizientes Lesen verwenden möchten, aber Sie gehen „Hinzufügen“ Elemente häufig werden, haben Sie zwei Möglichkeiten:

1) generieren sie als Liste (oder Liste der Listen) und verwenden Sie dann ToArray () es zu einer effizienten Arraystruktur zu machen.

2) Ordnen Sie die Array größer zu sein, als Sie brauchen, setzen Sie dann die Objekte in die vorgezugeordneten Zellen. Wenn Sie noch mehr Elemente am Ende brauchen, als Sie vorbelegt, können Sie einfach das Array neu zuteilen, wenn es füllt, die Größe jedes Mal verdoppeln. Dies gibt O (log n) Ändern der Größe Leistung anstelle von O (n), wie es mit einem Umspeichern-einmal-pro-add-Array sein würde. Beachten Sie, dass diese ziemlich viel ist, wie Stringbuilder arbeitet, können Sie einen schnelleren Weg zu geben in eine Zeichenfolge ständig anhängen.

Bei der Verwendung von Arrays verlassen

In erste Linie , wenn Semantik von Arrays Sie nicht Spiel mit Absicht - Brauchen Sie noch eine dynamisch wachsende Sammlung? Ein Satz, der keine Duplikate zulassen? Eine Kollektion, die unveränderlich bleiben muss? Vermeiden Sie Arrays in allen Fällen, dass. Das ist 99% der Fälle. Gerade das Offensichtliche Basispunkt.
Zweitens , wenn Sie sind nicht Codierung für absolute Performance Kritikalität - Das ist etwa 95% der Fälle. Arrays eine bessere Leistung marginal , besonders in Iteration . Es ist fast immer nie egal.
Wenn Sie sind nicht ein Argument mit params Stichwort gezwungen - ich besser, nur wollte params jede IEnumerable<T> akzeptiert oder sogar eine Sprache selbst konstruieren ein bezeichnen sequence (und kein Rahmentyp).
Wenn Sie nicht Schreiben Legacy-Code oder mit Interop tun

Kurz gesagt, es ist sehr selten, dass man wäre tatsächlich ein Array benötigen. Ich will hinzufügen, warum kann man es vermeiden?

Der wichtigste Grund dafür Arrays zu vermeiden imo ist konzeptuell. Arrays sind näher an Umsetzung und weiter von der Abstraktion. Arrays vermittelt mehr wie es gemacht wird als was getan wird, , die gegen den Geist der Hochsprachen ist. Das ist nicht überraschend, wenn man bedenkt Arrays ist näher an das Metall, sie sind gerade aus einem speziellen Typ (obwohl intern Array eine Klasse). Nicht zu pädagogischen, sondern Arrays wirklich auf eine semantische Bedeutung haben übersetzen sehr sehr selten erforderlich. Die nützlichsten und häufige Semantik ist, dass eine Sammlung mit allen Einträgen, setzt mit unterschiedlichen Elementen, Schlüsselwert Karten usw. mit einem beliebigen Kombination von addable, nur lesbar, unveränderlich, um respektiere Varianten. Denken Sie darüber nach, könnte man eine addable Sammlung will, oder Nur-Lese-Sammlung mit vordefinierten Positionen ohne weitere Modifikation, aber wie oft kommt Ihre Logik aussehen: „Ich eine dynamisch addable Sammlung will, aber nur eine feste Anzahl von ihnen, und sie sollten auch veränderbar sein „? Sehr selten würde ich sagen.

Array wurde während der Pre-Generika-Ära entworfen und imitiert Genericity mit viel Laufzeit Hacks und es wird seine Merkwürdigkeiten hier und da zeigen. Einige der Fänge ich gefunden:

Gebrochene Kovarianz.

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

Arrays können Sie auf eine Struktur verweisen! . Das ist anders als anderswo. Ein Beispiel:

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

Laufzeit implementiert Methoden wie ICollection<T>.Contains können unterschiedlich sein für structs und Klassen . Es ist keine große Sache, aber wenn Sie vergessen, nicht generic Equals richtig für Referenztypen generische Auflistung erwarten außer Kraft zu setzen für generic Equals zu betrachten, werden Sie falsche Ergebnisse erhalten.

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"

Die Length Eigenschaft und [] Indexer auf T[] scheinen regelmäßig Eigenschaften zu sein, dass Sie durch Reflexion zugreifen können (was etwas Magie beinhalten sollte), aber wenn es um Ausdruck Bäume kommt, müssen Sie die exakt gleichen Code ausspucken die Compiler tut. Es gibt ArrayLength und ArrayIndex Methoden, die separat zu tun. Eine solche Frage hier Ein anderes Beispiel:.
```
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;
```

Wie die Verwendung von Arrays verlassen

Die am häufigsten verwendete Ersatz ist List<T>, die eine sauberere API hat. Aber es ist eine dynamisch wachsende Struktur, die bedeutet, dass Sie zu einem List<T> am Ende hinzufügen oder überall zu jeder Kapazität einsetzen. Es gibt keinen Ersatz für das genaue Verhalten eines Arrays, aber die Leute meistens Arrays als Nur-Lese-Sammlung verwenden, in denen Sie nichts zu Ende hinzufügen. Ein Ersatz ist ReadOnlyCollection<T>. Ich trage diese Erweiterung Methode:

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

Wenn das Array der Größe verändert wird, muss ein neues Array zugeordnet wird, und der Inhalt kopiert. Wenn Sie nur den Inhalt des Arrays ändern, es ist nur eine Speicherbelegung.

Also, sollten Sie nicht Arrays verwenden, wenn Sie die Größe des Arrays nicht kennen, oder die Größe wird sich wahrscheinlich ändern. Wenn Sie jedoch eine feste Länge Array haben, sind sie eine einfache Möglichkeit, Elemente von Index des Abrufens.

Arraylist und Liste wachsen das Array von mehr als einem, wenn nötig (ich glaube, es ist durch die Größe zu verdoppeln, aber ich habe die Quelle nicht überprüft). Sie sind im Allgemeinen die beste Wahl, wenn Sie einen dynamisch angepassten Array bauen.

Wenn Sie Ihre Benchmarks, dass Array Resize zeigen ernsthaft Ihre Anwendung verlangsamt (denken Sie daran - vorzeitige Optimierung ist die Wurzel allen Übels)., Können Sie eine benutzerdefinierte Array-Klasse mit gezwickt Redimensionierung Verhalten bewerten Schreiben

Wenn Sie die BESTE Leistung bei der indizierten Suche benötigen, ist es im Allgemeinen am besten, zuerst eine Liste zu erstellen und sie dann in ein Array umzuwandeln. Dabei zahlen Sie zunächst einen kleinen Nachteil, vermeiden ihn aber später.Wenn das Problem darin besteht, dass Sie ständig neue Daten hinzufügen und alte Daten entfernen, möchten Sie der Einfachheit halber möglicherweise eine ArrayList oder List verwenden. Beachten Sie jedoch, dass es sich nur um Arrays in Sonderfällen handelt.Wenn sie „wachsen“, weisen sie ein völlig neues Array zu und kopieren alles hinein, was extrem langsam ist.

Anordnungsliste ist nur ein Array, das bei Bedarf wächst.Das Hinzufügen wird mit O(1) amortisiert. Achten Sie nur darauf, dass die Größenänderung nicht zu einem ungünstigen Zeitpunkt erfolgt.Einfügen ist O(n), alle Elemente rechts müssen verschoben werden.Remove ist O(n), alle Elemente rechts müssen verschoben werden.

Beachten Sie auch, dass es sich bei der Liste nicht um eine verknüpfte Liste handelt.Es ist nur eine typisierte ArrayList.Die Liste Dokumentation stellt fest, dass es in den meisten Fällen eine bessere Leistung erbringt, sagt jedoch nicht, warum.

Am besten wählen Sie eine Datenstruktur aus, die zu Ihrem Problem passt.Das hängt von vielen Dingen ab und deshalb möchten Sie vielleicht die Seite durchsuchen System.Collections.Generic Namensraum.

In diesem speziellen Fall würde ich sagen, dass Sie einen guten Schlüsselwert finden können Wörterbuch wäre die beste Wahl.Es verfügt über Einfügen und Entfernen, die sich O(1) nähern.Allerdings müssen Sie auch bei einem Dictionary darauf achten, dass sich die Größe des internen Arrays nicht ändert (eine O(n)-Operation).Geben Sie ihnen am besten viel Platz, indem Sie im Konstruktor eine größere Anfangskapazität angeben, als Sie erwarten.

-Rick

Eine Standard Array sollte mit einer Länge definiert werden, die den gesamten Speicher behält, die es in einem zusammenhängenden Block muss. ein Element in dem Array Hinzufügen es innerhalb des Blocks der bereits reservierten Speicher setzen würde.

Arrays sind für wenige schreiben und viele lesen, insbesondere die eine iterative Natur -. Für etwas anderes, eine der viele anderen Datenstrukturen verwendet

Sie sind richtig ein Array für Look-Ups ist groß. Jedoch Änderungen an der Größe des Arrays sind teuer.

Sie sollten einen Behälter verwenden, die inkrementelle Größe Anpassungen im Szenario unterstützt, wo Sie die Größe des Arrays sind zu ändern. Sie könnten eine Arraylist verwenden, die Sie die Ausgangsgröße festlegen kann, und man konnte die Größe im Vergleich zu der Kapazität kontinuierlich überprüfen und dann von einem großen Teil der Kapazität erhöhen, um die Anzahl der Größenänderungen zu begrenzen.

Oder Sie könnten nur eine verkettete Liste verwenden. Dann aber schauen ups sind langsam ...

Dieses Forum Post könnte oder nicht zu Ihnen in Bezug auf Effizienz verschiedenen Array-Typen von Nutzen sein: C # Arrays - mehrdimensionale vs lexicographic

Wenn ich denke, ich werde Elemente in die Kollektion eine Menge über die gesamte Lebensdauer zu geben, als ich eine Liste verwenden werden. Wenn ich weiß genau, was die Größe der Sammlung sein wird, wenn ihre erklärten, dann werde ich ein Array verwendet werden.

Ein weiteres Mal, dass ich in der Regel ein Array über eine Liste verwenden, wenn ich eine Sammlung als eine Eigenschaft eines Objekts zurückgeben müssen - ich möchte keine Anrufer Elemente hinzufügen, die Sammlung über Liste Methoden hinzufügen, sondern wollen, dass sie Artikel hinzufügen die Sammlung über die Schnittstelle meines Objekts. In diesem Fall werde ich die interne Liste nehmen und ToArray anrufen und ein Array zurück.

Wenn Sie vorhaben, viel Zugabe zu tun, und Sie werden nicht mit wahlfreiem Zugriff (wie myArray[i]) tun. Sie könnten eine verkettete Liste (LinkedList<T>) in Betracht ziehen, weil es nie müssen „wachsen“ wie die List<T> Umsetzung. Beachten Sie aber, dass Sie nur wirklich Elemente in einer LinkedList<T> Implementierung mit Hilfe des IEnumerable<T> Schnittstelle zugreifen können.

Das Beste, was man tun kann, ist, wie viel Speicher zuweisen, wie Sie, wenn möglich, im Voraus benötigen. Dadurch wird verhindert, .NET aus mit zusätzlichen Anrufe tätigen Speicher auf dem Heap zu bekommen. Gelingt das nicht, dann ist es sinnvoll in Stücke von fünf oder was auch immer Zahl macht Sinn für Ihre Anwendung zuzuweisen.

Dies ist eine Regel, die Sie wirklich etwas anwenden können.

Lizenziert unter: CC-BY-SA mit Zuschreibung

Nicht verbunden mit StackOverflow