Soll ich eine Liste oder ein Array verwenden?

22

Ich arbeite an einem Windows-Formular, um die UPC für Artikelnummern zu berechnen.

Ich habe erfolgreich eine erstellt, die jeweils eine Artikelnummer / UPC verarbeiten kann. Jetzt möchte ich sie erweitern und für mehrere Artikelnummern / UPCs ausführen.

Ich habe angefangen und versucht, eine Liste zu verwenden, aber ich bleibe immer stecken. Ich habe eine Helferklasse erstellt:

public class Codes
{
    private string incrementedNumber;
    private string checkDigit;
    private string wholeNumber;
    private string wholeCodeNumber;
    private string itemNumber;

    public Codes(string itemNumber, string incrementedNumber, string checkDigit, string wholeNumber, string wholeCodeNumber)
    {
        this.incrementedNumber = incrementedNumber;
        this.checkDigit = checkDigit;
        this.wholeNumber = wholeNumber;
        this.wholeCodeNumber = wholeCodeNumber;
        this.itemNumber = itemNumber;
    }

    public string ItemNumber
    {
        get { return itemNumber; }
        set { itemNumber = value; }
    }

    public string IncrementedNumber
    { 
        get { return incrementedNumber; }
        set { incrementedNumber = value; } 
    }

    public string CheckDigit
    {
        get { return checkDigit; }
        set { checkDigit = value; }
    }

    public string WholeNumber
    {
        get { return wholeNumber; }
        set { wholeNumber = value; }
    }

    public string WholeCodeNumber
    {
        get { return wholeCodeNumber; }
        set { wholeCodeNumber = value; }
    }

}

Dann habe ich mit meinem Code angefangen, aber das Problem ist, dass der Prozess inkrementell ist, das heißt, ich erhalte die Artikelnummer aus einer Rasteransicht über Kontrollkästchen und füge sie in die Liste ein. Dann hole ich den letzten UPC aus der Datenbank, entferne die Prüfziffer, erhöhe die Zahl um eins und füge sie in die Liste ein. Dann berechne ich die Prüfziffer für die neue Nummer und trage sie in die Liste ein. Und hier bekomme ich bereits eine Out of Memory-Ausnahme. Hier ist der Code, den ich bisher habe:

List<Codes> ItemNumberList = new List<Codes>();


    private void buttonSearch2_Click(object sender, EventArgs e)
    {
        //Fill the datasets
        this.immasterTableAdapter.FillByWildcard(this.alereDataSet.immaster, (textBox5.Text));
        this.upccodeTableAdapter.FillByWildcard(this.hangtagDataSet.upccode, (textBox5.Text));
        this.uPCTableAdapter.Fill(this.uPCDataSet.UPC);
        string searchFor = textBox5.Text;
        int results = 0;
        DataRow[] returnedRows;
        returnedRows = uPCDataSet.Tables["UPC"].Select("ItemNumber = '" + searchFor + "2'");
        results = returnedRows.Length;
        if (results > 0)
        {
            MessageBox.Show("This item number already exists!");
            textBox5.Clear();
            //clearGrids();
        }
        else
        {
            //textBox4.Text = dataGridView1.Rows[0].Cells[1].Value.ToString();
            MessageBox.Show("Item number is unique.");
        }
    }

    public void checkMarks()
    {

        for (int i = 0; i < dataGridView7.Rows.Count; i++)
        {
            if ((bool)dataGridView7.Rows[i].Cells[3].FormattedValue)
            {
                {
                    ItemNumberList.Add(new Codes(dataGridView7.Rows[i].Cells[0].Value.ToString(), "", "", "", ""));
                }
            }
        }
    }

    public void multiValue1()
    {
        _value = uPCDataSet.UPC.Rows[uPCDataSet.UPC.Rows.Count - 1]["UPCNumber"].ToString();//get last UPC from database
        _UPCNumber = _value.Substring(0, 11);//strip out the check-digit
        _UPCNumberInc = Convert.ToInt64(_UPCNumber);//convert the value to a number

        for (int i = 0; i < ItemNumberList.Count; i++)
        {
            _UPCNumberInc = _UPCNumberInc + 1;
            _UPCNumberIncrement = Convert.ToString(_UPCNumberInc);//assign the incremented value to a new variable
            ItemNumberList.Add(new Codes("", _UPCNumberIncrement, "", "", ""));//**here I get the OutOfMemoreyException**
        }

        for (int i = 0; i < ItemNumberList.Count; i++)
        {
            long chkDigitOdd;
            long chkDigitEven;
            long chkDigitSubtotal;
            chkDigitOdd = Convert.ToInt64(_UPCNumberIncrement.Substring(0, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(2, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(4, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(6, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(8, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(10, 1));
            chkDigitOdd = (3 * chkDigitOdd);
            chkDigitEven = Convert.ToInt64(_UPCNumberIncrement.Substring(1, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(3, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(5, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(7, 1)) + Convert.ToInt64(_UPCNumberIncrement.Substring(9, 1));
            chkDigitSubtotal = (300 - (chkDigitEven + chkDigitOdd));
            _chkDigit = chkDigitSubtotal.ToString();
            _chkDigit = _chkDigit.Substring(_chkDigit.Length - 1, 1);
            ItemNumberList.Add(new Codes("", "",_chkDigit, "", ""));
        }

Ist dies der richtige Weg, eine Liste zu verwenden, oder sollte ich einen anderen Weg einschlagen?

campagnolo_1
quelle
Das Verwenden einer Liste ist in Ordnung. Das Durchlaufen der Liste während des Hinzufügens ist eine todsichere Möglichkeit, Ihren Code in die Luft zu jagen, und weist auf ein Problem in Ihrer Logik (oder beim Schreiben von Code) hin. Dies ist auch Ihr Fehler und wird wahrscheinlich zukünftigen Besuchern nicht helfen. Abstimmung zum Abschluss.
Telastyn
2
Nebenbei bemerkt, all diese privaten Felder (in Ihrer CodeKlasse) sind redundant und nichts als Lärm { get; private set; }würde wirklich ausreichen.
Konrad Morawski
5
Ist der Fragentitel dafür wirklich korrekt? Dies scheint nicht wirklich eine Frage zwischen Liste und Array zu sein , sondern vielmehr eine Frage, wie ich meine Implementierung verbessern kann . Das heißt, wenn Sie Elemente hinzufügen oder entfernen , möchten Sie eine Liste (oder eine andere flexible Datenstruktur). Arrays sind nur dann wirklich gut, wenn Sie genau wissen, wie viele Elemente Sie zu Beginn benötigen.
KChaloux
@KChaloux, das wollte ich eigentlich wissen. Ist eine Liste der richtige Weg, um dies zu erreichen, oder hätte ich einen anderen Weg suchen sollen, um dies zu erreichen? Eine Liste scheint also ein guter Weg zu sein, ich muss nur meine Logik anpassen.
campagnolo_1
1
@Telastyn, ich habe nicht so sehr darum gebeten, meinen Code zu verbessern, als vielmehr zu zeigen, was ich versuche.
campagnolo_1

Antworten:

73

Ich werde meinen Kommentar erweitern:

... wenn Sie Elemente hinzufügen oder entfernen , möchten Sie eine Liste (oder eine andere flexible Datenstruktur). Arrays sind nur dann wirklich gut, wenn Sie genau wissen, wie viele Elemente Sie zu Beginn benötigen.

Eine schnelle Panne

Arrays sind gut, wenn Sie über eine feste Anzahl von Elementen verfügen , die sich wahrscheinlich nicht ändern, und nicht sequentiell darauf zugreifen möchten.

  • Feste Größe
  • Schneller Zugriff - O (1)
  • Slow Resize - O (n) - muss jedes Element in ein neues Array kopieren!

Verknüpfte Listen sind für schnelles Hinzufügen und Entfernen an beiden Enden optimiert, haben jedoch in der Mitte einen langsamen Zugriff.

  • Variable Größe
  • Langsamer Zugriff in der Mitte - O (n)
    • Es muss jedes Element beginnend am Kopf durchlaufen werden, um den gewünschten Index zu erreichen
  • Schneller Zugriff an der Spitze - O (1)
  • Potenziell schneller Zugang am Heck
    • O (1) wenn eine Referenz am hinteren Ende gespeichert ist (wie bei einer doppelt verknüpften Liste)
    • O (n) wenn keine Referenz gespeichert ist (gleiche Komplexität wie der Zugriff auf einen Knoten in der Mitte)

Array-Listen (wie List<T>in C #!) Sind eine Mischung aus beidem, mit relativ schnellen Hinzufügungen und wahlfreiem Zugriff. List<T> wird oft Ihre Sammlung sein, wenn Sie nicht sicher sind, was Sie verwenden sollen.

  • Verwendet ein Array als Hintergrundstruktur
  • Ist schlau in Bezug auf die Größenänderung - teilt das Doppelte seines aktuellen Speicherplatzes zu, wenn er nicht mehr ausreicht.
    • Dies führt dazu, dass sich die Größe von O (log n) ändert, was besser ist, als die Größe jedes Mal zu ändern, wenn wir sie hinzufügen / entfernen
  • Schneller Zugriff - O (1)

So funktionieren Arrays

Die meisten Sprachen modellieren Arrays als zusammenhängende Daten im Speicher, von denen jedes Element dieselbe Größe hat. Nehmen wir an, wir hatten ein Array von ints (angezeigt als [Adresse: Wert], mit Dezimaladressen, weil ich faul bin)

[0: 10][32: 20][64: 30][96: 40][128: 50][160: 60]

Jedes dieser Elemente ist eine 32-Bit-Ganzzahl, daher wissen wir, wie viel Speicherplatz es im Speicher einnimmt (32 Bit!). Und wir kennen die Speicheradresse des Zeigers auf das erste Element.

Es ist trivial einfach, den Wert eines anderen Elements in diesem Array zu ermitteln:

  • Nimm die Adresse des ersten Elements
  • Nimm den Offset jedes Elements (seine Größe im Speicher)
  • Multiplizieren Sie den Offset mit dem gewünschten Index
  • Fügen Sie Ihr Ergebnis zur Adresse des ersten Elements hinzu

Nehmen wir an, unser erstes Element ist '0'. Wir wissen, dass unser zweites Element bei '32' (0 + (32 * 1)) und unser drittes Element bei 64 (0 + (32 * 2)) liegt.

Die Tatsache, dass wir all diese Werte nebeneinander speichern können, bedeutet, dass unser Array so kompakt wie möglich ist. Es bedeutet auch, dass alle unsere Elemente zusammen bleiben müssen, damit die Dinge weiter funktionieren!

Sobald wir ein Element hinzufügen oder entfernen, müssen wir alles andere aufnehmen und an eine neue Stelle im Speicher kopieren, um sicherzustellen, dass keine Lücken zwischen den Elementen vorhanden sind und alles genügend Platz hat. Dies kann sehr langsam sein , insbesondere wenn Sie dies jedes Mal tun , wenn Sie ein einzelnes Element hinzufügen möchten.

Verknüpfte Listen

Im Gegensatz zu Arrays müssen bei verknüpften Listen nicht alle Elemente im Speicher nebeneinander liegen. Sie bestehen aus Knoten, die die folgenden Informationen speichern:

Node<T> {
    Value : T      // Value of this element in the list
    Next : Node<T> // Reference to the node that comes next
}

Die Liste selbst enthält in den meisten Fällen einen Verweis auf den Kopf und den Schwanz (erster und letzter Knoten) und verfolgt manchmal ihre Größe.

Wenn Sie ein Element am Ende der Liste hinzufügen möchten, müssen Sie nur den Schwanz abrufen und ihn so ändern Next, dass er auf ein neues Element verweist, Nodedas Ihren Wert enthält. Das Entfernen vom Ende ist ebenso einfach - dereferenzieren Sie einfach den NextWert des vorhergehenden Knotens.

Wenn Sie ein LinkedList<T>Element mit 1000 Elementen haben und Element 500 möchten, gibt es leider keine einfache Möglichkeit, direkt zum 500. Element zu springen, wie dies bei einem Array der Fall ist. Sie müssen am Kopf beginnen und weiter zum NextKnoten gehen, bis Sie dies 500 Mal getan haben.

Aus diesem Grund ist das Hinzufügen und Entfernen von a LinkedList<T>schnell (wenn Sie an den Enden arbeiten), aber der Zugriff auf die Mitte ist langsam.

Bearbeiten : Brian weist in den Kommentaren darauf hin, dass verknüpfte Listen das Risiko haben, einen Seitenfehler zu verursachen, da sie nicht im zusammenhängenden Speicher gespeichert werden. Dies kann schwierig zu bewerten sein und dazu führen, dass verknüpfte Listen aufgrund ihrer zeitlichen Komplexität sogar etwas langsamer ablaufen als erwartet.

Beste aus beiden Welten

List<T>Kompromisse für beide T[]und LinkedList<T>und bietet eine Lösung, die in den meisten Situationen relativ schnell und einfach zu bedienen ist.

Intern List<T>ist ein Array! Es muss beim Ändern der Größe immer noch durch die Rahmen springen, um seine Elemente zu kopieren, aber es zieht ein paar nette Tricks.

Wenn Sie ein einzelnes Element hinzufügen, wird das Array normalerweise nicht kopiert. List<T>Stellt sicher, dass immer genügend Platz für weitere Elemente vorhanden ist. Anstatt ein neues internes Array mit nur einem neuen Element zuzuweisen, wird ein neues Array mit mehreren neuen Elementen zugewiesen (oft doppelt so viele wie derzeit!).

Kopiervorgänge sind teuer. List<T>Reduzieren Sie sie daher so weit wie möglich, und ermöglichen Sie dennoch einen schnellen Direktzugriff. Als Nebeneffekt wird möglicherweise etwas mehr Speicherplatz verschwendet als bei einem direkten Array oder einer verknüpften Liste, aber in der Regel lohnt sich der Kompromiss.

TL; DR

Verwenden Sie List<T>. Es ist normalerweise das, was Sie wollen, und es scheint in dieser Situation (in der Sie .Add () aufrufen) für Sie richtig zu sein. Wenn Sie sich nicht sicher sind, was Sie brauchen, List<T>ist dies ein guter Anfang.

Arrays eignen sich gut für leistungsstarke "Ich weiß, ich brauche genau X-Elemente" -Dinge. Alternativ sind sie nützlich für schnelle, einmalige "Ich muss diese X-Dinge, die ich bereits definiert habe, gruppieren, damit ich über sie eine Schleife erstellen kann" -Strukturen.

Es gibt eine Reihe weiterer Sammelklassen. Stack<T>ist wie eine verknüpfte Liste, die nur von oben funktioniert. Queue<T>arbeitet als First-In-First-Out-Liste. Dictionary<T, U>ist eine ungeordnete assoziative Zuordnung zwischen Schlüsseln und Werten. Spielen Sie mit ihnen und lernen Sie deren Stärken und Schwächen kennen. Sie können Ihre Algorithmen machen oder brechen.

KChaloux
quelle
2
In einigen Fällen kann die Verwendung einer Kombination aus einem Array und einer intAngabe der Anzahl verwendbarer Elemente Vorteile bringen . Unter anderem ist es möglich, mehrere Elemente gleichzeitig von einem Array in ein anderes zu kopieren. Für das Kopieren zwischen Listen müssen die Elemente jedoch in der Regel einzeln verarbeitet werden. Darüber hinaus können Array-Elemente refan Dinge wie übergeben werden Interlocked.CompareExchange, während Listenelemente dies nicht können.
Supercat
2
Ich wünschte, ich könnte mehr als eine Gegenstimme abgeben. Ich kannte die Anwendungsfallunterschiede und die Funktionsweise von Arrays / verknüpften Listen, wusste aber nie, wie List<>sie unter der Haube funktionieren.
Bobson
1
Hinzufügen eines einzelnen Elements zu einer Liste <T> wird amortisiert O (1); Die Effizienz des Hinzufügens von Elementen ist normalerweise nicht ausreichend, um eine verknüpfte Liste zu verwenden (und eine zirkuläre Liste ermöglicht es Ihnen, in amortisiertem O (1) vorne UND hinten hinzuzufügen). Verknüpfte Listen weisen viele Leistungsunterschiede auf. Wenn Sie beispielsweise nicht zusammenhängend im Speicher speichern, führt das Durchlaufen einer gesamten verknüpften Liste mit größerer Wahrscheinlichkeit zu einem Seitenfehler. Dies lässt sich nur schwer vergleichen. Die größere Rechtfertigung für die Verwendung einer verknüpften Liste ist, wenn Sie zwei Listen verketten möchten (dies kann in O (1) erfolgen) oder Elemente zur Mitte hinzufügen möchten.
Brian
1
Ich sollte klarstellen. Als ich Zirkelliste sagte, meinte ich eine Zirkelliste, keine Zirkelliste. Der richtige Begriff wäre deque (doppelte Warteschlange). Sie werden oft auf die gleiche Weise implementiert wie eine Liste (Array unter der Haube), mit einer Ausnahme: Es gibt einen internen ganzzahligen Wert "first", der angibt, welcher Index des Arrays das erste Element ist. Um der Rückseite ein Element hinzuzufügen, müssen Sie nur 1 von "first" abziehen (ggf. um die Länge des Arrays wickeln). Um auf ein Element zuzugreifen, müssen Sie nur darauf zugreifen (index+first)%length.
Brian
2
Es gibt einige Dinge, die Sie mit einer Liste nicht tun können, die Sie mit einem einfachen Array tun können, z. B. die Übergabe eines Indexelements als ref-Parameter.
Ian Goldby
6

Während die Antwort von KChaloux großartig ist, möchte ich auf eine andere Überlegung hinweisen: IstList<T> viel leistungsfähiger als ein Array. Die Methoden von List<T>sind unter vielen Umständen sehr nützlich - ein Array verfügt nicht über diese Methoden, und Sie müssen möglicherweise viel Zeit aufwenden, um Problemumgehungen zu implementieren.

Aus entwicklungspolitischer Sicht verwende ich daher fast immer, List<T>da zusätzliche Anforderungen oft viel einfacher zu implementieren sind, wenn Sie a verwenden List<T>.

Dies führt zu einem letzten Problem: Mein Code (ich weiß nicht, wie es bei Ihnen aussieht) enthält 90% List<T>, sodass Arrays nicht wirklich passen. Wenn ich sie weitergebe, muss ich ihre .toList()Methode aufrufen und sie in eine Liste konvertieren - dies ist ärgerlich und so langsam, dass jeglicher Leistungsgewinn durch die Verwendung eines Arrays verloren geht.

Christian Sauer
quelle
Das ist wahr, dies ist ein weiterer guter Grund, List <T> zu verwenden - es bietet viel mehr Funktionen, die Sie direkt in die Klasse integriert haben.
KChaloux
1
Gleicht LINQ das Feld nicht ab, indem viele dieser Funktionen für IEnumerable (einschließlich eines Arrays) hinzugefügt werden? Gibt es in modernem C # (4+) noch etwas, das Sie nur mit einer Liste <T> und nicht mit einem Array tun können?
Dave
1
@ Dave Das Erweitern des Arrays / der Liste scheint so etwas. Außerdem würde ich sagen, dass die Syntax zum Erstellen / Behandeln einer Liste viel besser ist als für Arrays.
Christian Sauer
2

Niemand erwähnte diesen Teil jedoch: "Und hier bekomme ich bereits eine Ausnahmebedingung wegen unzureichendem Speicher." Welches ist ganz auf

for (int i = 0; i < ItemNumberList.Count; i++)
{
    ItemNumberList.Add(new item());
}

Es ist klar, warum. Ich weiß nicht, ob Sie einer anderen Liste hinzufügen ItemNumberList.Countwollten oder nur als Variable vor der Schleife speichern sollten , um das gewünschte Ergebnis zu erzielen, aber das ist einfach kaputt.

Programmers.SE steht für "... Interesse an konzeptionellen Fragen zur Softwareentwicklung ..." und die anderen Antworten behandelten es als solche. Versuchen Sie stattdessen http://codereview.stackexchange.com , wo diese Frage passen würde. Aber selbst dort ist es schrecklich, da wir nur davon ausgehen können, dass dieser Code bei beginnt, bei _Clickdem kein Anruf erfolgt, multiValue1bei dem Sie sagen, dass der Fehler auftritt.

Wolfzoon
quelle