Czy powinienem użyć listy czy tablicy?

22

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?

campagnolo_1
źródło
Korzystanie z listy jest w porządku. Iterowanie listy podczas dodawania do niej jest pewnym sposobem na wysadzenie twojego kodu i wskazuje na problem w twojej logice (lub pisaniu kodu). Jest to także twój błąd i raczej nie pomoże przyszłym użytkownikom. Głosowanie na zakończenie.
Telastyn
2
Na marginesie, wszystkie te prywatne pola (w twojej Codeklasie) są zbędne i tak naprawdę { get; private set; }wystarczyłby tylko hałas .
Konrad Morawski,
5
Czy tytuł pytania na ten temat jest naprawdę dokładny? To tak naprawdę nie wydaje się pytaniem typu lista kontra macierz , a raczej pytaniem: jak mogę poprawić swoje pytanie dotyczące implementacji . Biorąc to pod uwagę, 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.
KChaloux,
@KChalhal, to prawie to, co chciałem wiedzieć. Czy lista jest właściwą drogą do tego, czy powinienem był spojrzeć na inny sposób, aby to osiągnąć? Wygląda na to, że lista to dobry sposób, muszę tylko dostosować swoją logikę.
campagnolo_1,
1
@Telastyn, nie tyle prosiłem o ulepszenie kodu, ile pokazałem, co próbuję zrobić.
campagnolo_1,

Odpowiedzi:

73

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.

KChaloux
źródło
2
W niektórych przypadkach zastosowanie kombinacji tablicy i intwskazania liczby użytecznych elementów może być korzystne . Możliwe jest między innymi kopiowanie zbiorcze wielu elementów z jednej tablicy do drugiej, ale kopiowanie między listami zazwyczaj wymaga indywidualnego przetwarzania elementów. Ponadto elementy tablicy mogą być przekazywane refdo takich rzeczy, jak Interlocked.CompareExchangeelementy listy nie.
supercat,
2
Chciałbym móc wyrazić więcej niż jedną opinię. Znałem różnice między przypadkami użycia i jak działały tablice / listy połączone, ale nigdy nie wiedziałem ani nie myślałem o tym, jak List<>działa pod maską.
Bobson,
1
Dodanie pojedynczego elementu do Listy <T> jest amortyzowane przez O (1); efektywność dodawania elementów zwykle nie jest wystarczającym uzasadnieniem dla korzystania z połączonej listy (a okrągła Lista pozwala dodawać z przodu ORAZ z tyłu w zamortyzowanym O (1)). Listy połączone mają wiele cech charakterystycznych dla wydajności. Na przykład brak ciągłego przechowywania w pamięci oznacza, że ​​iteracja po całej połączonej liście może spowodować błąd strony ... i trudno to porównać. Większe uzasadnienie używania Listy połączonej ma miejsce, gdy chcesz połączyć dwie listy (można to zrobić w O (1)) lub dodać elementy na środku.
Brian,
1
Powinienem wyjaśnić. Kiedy mówiłem o okrągłej liście, miałem na myśli okrągłą listę tablic, a nie okrągłą listę połączoną. Prawidłowym terminem byłoby deque (kolejka podwójnie zakończona). Często są one implementowane prawie tak samo jak List (tablica pod maską), z jednym wyjątkiem: Istnieje wewnętrzna liczba całkowita, „pierwsza”, która wskazuje, który indeks tablicy jest pierwszym elementem. Aby dodać element z tyłu, wystarczy odjąć 1 od „pierwszego” (w razie potrzeby zawinąć do długości tablicy). Aby uzyskać dostęp do elementu, wystarczy uzyskać dostęp (index+first)%length.
Brian,
2
Jest kilka rzeczy, których nie można zrobić z Listą, które można zrobić za pomocą zwykłej tablicy, na przykład przekazując element indeksu jako parametr ref.
Ian Goldby
6

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.

Christian Sauer
źródło
To prawda, jest to kolejny dobry powód, aby używać List <T> - zapewnia on znacznie więcej funkcji wbudowanych bezpośrednio w klasę.
KChaloux,
1
Czy LINQ nie niweluje pola, dodając wiele z tych funkcji dla dowolnego IEnumerable (w tym tablicy)? Czy we współczesnym C # (4+) pozostało coś, co można zrobić tylko z Listą <T>, a nie z tablicą?
Dave
1
@Dave Rozszerzenie tablicy / listy wydaje się czymś takim. Powiedziałbym też, że składnia do konstruowania / obsługi listy jest znacznie ładniejsza niż w przypadku tablic.
Christian Sauer
2

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.

Wolfzoon
źródło