Czy powinienem użyć listy czy tablicy?

Pracuję nad formularzem systemu Windows, aby obliczyć UPC dla numerów pozycji.

Z powodzeniem tworzę taki, który będzie obsługiwał jeden numer pozycji / UPC na raz, teraz chcę rozwinąć i zrobić to dla wielu numerów pozycji / UPC.

Zacząłem i próbowałem używać listy, ale ciągle się zacinam. Stworzyłem klasę pomocnika:

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; }
    }

}

Potem zacząłem pisać kod, ale problem polega na tym, że proces jest przyrostowy, co oznacza, że ​​otrzymuję numer pozycji z widoku siatki za pomocą pól wyboru i umieszczam je na liście. Następnie pobieram ostatni UPC z bazy danych, usuwam cyfrę kontrolną, a następnie zwiększam liczbę o jeden i umieszczam ją na liście. Następnie obliczam cyfrę kontrolną dla nowego numeru i umieszczam go na liście. I tutaj już dostaję wyjątek braku pamięci. Oto kod, który mam do tej pory:

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, "", ""));
        }

Czy to właściwy sposób, aby to zrobić, korzystając z listy, czy powinienem patrzeć w inny sposób?

Rozwinę mój komentarz:

... jeśli dodajesz lub usuwasz elementy, potrzebujesz listy (lub innej elastycznej struktury danych). Tablice są naprawdę dobre tylko wtedy, gdy dokładnie wiesz, ile elementów potrzebujesz na początku.

Szybki podział

Tablice są dobre, gdy masz ustaloną liczbę elementów, których zmiana jest mało prawdopodobna, i chcesz uzyskać do nich dostęp w sposób niesekwencyjny.

• Naprawiono rozmiar
• Szybki dostęp - O (1)
• Powolna zmiana rozmiaru - O (n) - musi skopiować każdy element do nowej tablicy!

Listy połączone są zoptymalizowane pod kątem szybkiego dodawania i usuwania na obu końcach, ale dostęp do nich jest powolny w środku.

• Zmienny rozmiar
• Powolny dostęp na środku - O (n)
  • Musi przejść każdy element, zaczynając od głowy, aby osiągnąć pożądany indeks
• Szybki dostęp na czele - O (1)
• Potencjalnie szybki dostęp do Tail
  • O (1), jeśli odniesienie jest przechowywane na końcu (jak w przypadku podwójnie powiązanej listy)
  • O (n) jeśli nie zachowano odniesienia (taka sama złożoność jak dostęp do węzła w środku)

Listy tablic (takie jak List<T>w C #!) Są mieszanką tych dwóch, z dość szybkimi dodatkami i losowym dostępem. List<T> będzie często twoją kolekcją, gdy nie jesteś pewien, czego użyć.

• Używa tablicy jako struktury podkładu
• Jest mądry w kwestii zmiany rozmiaru - przydaje się podwójnej bieżącej przestrzeni, gdy jej zabraknie.
  • Prowadzi to do zmiany rozmiaru O (log n), co jest lepsze niż zmiana rozmiaru za każdym razem, gdy dodajemy / usuwamy
• Szybki dostęp - O (1)

Jak działają tablice

Większość języków modeluje tablice jako ciągłe dane w pamięci, których każdy element ma ten sam rozmiar. Powiedzmy, że mieliśmy tablicę ints (wyświetlaną jako [adres: wartość], używając adresów dziesiętnych, ponieważ jestem leniwy)

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

Każdy z tych elementów jest 32-bitową liczbą całkowitą, więc wiemy, ile miejsca zajmuje w pamięci (32 bity!). I znamy adres pamięci wskaźnika do pierwszego elementu.

Łatwo jest dostać się do wartości dowolnego innego elementu w tej tablicy:

• Weź adres pierwszego elementu
• Weź przesunięcie każdego elementu (jego rozmiar w pamięci)
• Pomnóż przesunięcie przez żądany indeks
• Dodaj swój wynik do adresu pierwszego elementu

Powiedzmy, że naszym pierwszym elementem jest „0”. Wiemy, że naszym drugim elementem jest „32” (0 + (32 * 1)), a nasz trzeci element to 64 (0 + (32 * 2)).

Fakt, że możemy przechowywać wszystkie te wartości obok siebie w pamięci oznacza, że ​​nasza tablica jest tak zwarta, jak to tylko możliwe. Oznacza to również, że wszystkie nasze elementy muszą pozostać razem, aby rzeczy mogły dalej działać!

Jak tylko dodamy lub usuniemy element, musimy pobrać wszystko inne i skopiować je do nowego miejsca w pamięci, aby upewnić się, że nie ma żadnych przerw między elementami i wszystko ma wystarczająco dużo miejsca. Może to być bardzo wolne , szczególnie jeśli robisz to za każdym razem, gdy chcesz dodać pojedynczy element.

Połączone listy

W przeciwieństwie do tablic, Listy Połączone nie potrzebują, aby wszystkie ich elementy znajdowały się obok siebie w pamięci. Składają się z węzłów, które przechowują następujące informacje:

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

Sama lista zawiera odniesienie do głowy i ogona (pierwszy i ostatni węzeł) w większości przypadków, a czasami śledzi jej rozmiar.

Jeśli chcesz dodać element na końcu listy, wszystko, co musisz zrobić, to zdobyć ogon i zmienić go tak, Nextaby odwoływał się do nowego Nodezawierającego twoją wartość. Usuwanie z końca jest równie proste - po prostu odłóż Nextwartość poprzedniego węzła.

Niestety, jeśli masz LinkedList<T>1000 elementów i chcesz element 500, nie ma łatwego sposobu na przejście do 500. elementu, tak jak w przypadku tablicy. Musisz zacząć od głowy i iść do Nextwęzła, dopóki nie zrobisz tego 500 razy.

Dlatego dodawanie i usuwanie z a LinkedList<T>jest szybkie (podczas pracy na końcach), ale dostęp do środka jest powolny.

Edycja : Brian wskazuje w komentarzach, że Listy połączone mogą powodować błąd strony, ponieważ nie są przechowywane w ciągłej pamięci. Może to być trudne do porównania i może sprawić, że Listy Połączone będą nawet nieco wolniejsze, niż można się spodziewać, biorąc pod uwagę ich złożoność czasową.

Najlepsze z obu światów

List<T>kompromisy zarówno dla, jak T[]i dlaLinkedList<T> oferuje rozwiązanie, które jest dość szybkie i łatwe w użyciu w większości sytuacji.

Wewnętrznie List<T>jest tablicą! Nadal musi przeskakiwać przez obręcze kopiowania swoich elementów podczas zmiany rozmiaru, ale wyciąga kilka fajnych sztuczek.

Po pierwsze, dodanie pojedynczego elementu zwykle nie powoduje skopiowania tablicy. List<T>upewnia się, że zawsze jest wystarczająco dużo miejsca na więcej elementów. Kiedy skończy się, zamiast przydzielić nową tablicę wewnętrzną tylko jednym nowym elementem, przydzieli nową tablicę z kilkoma nowymi elementami (często dwa razy więcej niż obecnie!).

Operacje kopiowania są kosztowne, więc List<T>zmniejsz je jak najwięcej, jednocześnie umożliwiając szybki losowy dostęp. Efektem ubocznym może być marnowanie nieco więcej miejsca niż prosta tablica lub połączona lista, ale zwykle jest to warte kompromisu.

TL; DR

Zastosowanie List<T>. Jest to zwykle to, czego chcesz, i wydaje się, że jest odpowiednie dla ciebie w tej sytuacji (gdy dzwonisz .Add ()). Jeśli nie masz pewności, czego potrzebujesz, List<T>warto zacząć.

Tablice są dobre dla rzeczy o wysokiej wydajności, „Wiem, że potrzebuję dokładnie X elementów”. Alternatywnie, są one przydatne do szybkiego, jednorazowego „Muszę pogrupować te X rzeczy, które już zdefiniowałem, aby móc je zapętlić”.

Istnieje wiele innych klas kolekcji. Stack<T>jest jak połączona lista, która działa tylko od góry. Queue<T>działa jako lista „pierwsze weszło-pierwsze wyszło”. Dictionary<T, U>to nieuporządkowane, asocjacyjne mapowanie między kluczami a wartościami. Graj z nimi i poznaj mocne i słabe strony każdego z nich. Mogą tworzyć lub łamać algorytmy.

Chociaż odpowiedź KChaloux jest świetna, chciałbym zwrócić uwagę na inną kwestię: List<T>jest znacznie potężniejszy niż tablica. Metody List<T>są bardzo przydatne w wielu okolicznościach - tablica nie ma tych metod i możesz poświęcić dużo czasu na wdrożenie obejść.

Tak więc z perspektywy programowania prawie zawsze używam, List<T>ponieważ gdy są dodatkowe wymagania, często są one znacznie łatwiejsze do wdrożenia, gdy używasz List<T>.

Prowadzi to do końcowego problemu: mój kod (nie wiem o twoim) zawiera 90% List<T>, więc tablice tak naprawdę nie pasują. Kiedy je przekazuję, muszę wywołać ich .toList()metodę i przekonwertować je na Listę - to jest denerwujący i jest tak wolny, że tracony jest wzrost wydajności wynikający z użycia macierzy.

Nikt jednak nie wspomniał o tej części: „I tutaj już dostaję wyjątek braku pamięci”. Co jest całkowicie spowodowane

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

Łatwo zrozumieć, dlaczego. Nie wiem, czy chciałeś dodać do innej listy, czy po prostu zapisz ItemNumberList.Countjako zmienną przed pętlą, aby uzyskać pożądany wynik, ale jest to po prostu zepsute.

Programmers.SE jest dla „… zainteresowanych koncepcyjnymi pytaniami dotyczącymi rozwoju oprogramowania…”, a inne odpowiedzi traktowały to jako takie. Zamiast tego spróbuj http://codereview.stackexchange.com , gdzie pasowałoby to pytanie. Ale nawet tam jest okropnie, ponieważ możemy założyć, że ten kod zaczyna się od _Click, w którym nie ma wywołania, w multiValue1którym mówi się, że wystąpił błąd.