Должен ли я использовать список или массив?

22

Я работаю над формой окна для расчета UPC для номеров позиций.

Я успешно создал один, который будет обрабатывать один номер элемента / UPC за раз, теперь я хочу расширить и сделать это для нескольких номеров элементов / UPC.

Я начал и попытался использовать список, но я продолжаю застрять. Я создал вспомогательный класс:

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

}

Затем я приступил к написанию своего кода, но проблема в том, что этот процесс пошаговый, то есть я получаю номер элемента из таблицы с помощью флажков и помещаю их в список. Затем я получаю последний UPC из базы данных, убираю контрольную цифру, затем увеличиваю число на единицу и помещаю его в список. Затем я вычисляю контрольную цифру для нового номера и помещаю ее в список. И здесь я уже получаю исключение нехватки памяти. Вот код, который у меня есть:

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

Это правильный путь, используя список, или я должен смотреть по-другому?

campagnolo_1
источник
Использование списка это нормально. Повторение списка при добавлении в него - верный способ взорвать ваш код и указывает на проблему в вашей логике (или написании кода). Кроме того, это ваша ошибка и вряд ли поможет будущим посетителям. Голосование, чтобы закрыть.
Теластин
2
Как примечание, все эти частные поля (в вашем Codeклассе) являются избыточными, и на самом деле ничего, кроме шума, { get; private set; }будет достаточно.
Конрад Моравский
5
Название вопроса для этого действительно точно? На самом деле это не похоже на вопрос списка или массива , а скорее на вопрос Как я могу улучшить свой вопрос реализации . При этом, если вы добавляете или удаляете элементы, вам нужен список (или другая гибкая структура данных). Массивы действительно хороши только тогда, когда вы точно знаете, сколько элементов вам нужно в начале.
KChaloux
@KChaloux, это почти то, что я хотел знать. Является ли список правильным способом для этого, или я должен был искать другой способ добиться этого? Кажется, список - это хороший способ, мне просто нужно скорректировать свою логику.
campagnolo_1
1
@Telastyn, я не столько просил улучшить свой код, сколько показать, что я пытаюсь сделать.
campagnolo_1

Ответы:

73

Я расширю свой комментарий:

... если вы добавляете или удаляете элементы, вам нужен список (или другая гибкая структура данных). Массивы действительно хороши только тогда, когда вы точно знаете, сколько элементов вам нужно в начале.

Быстрый пробой

Массивы хороши, когда у вас есть фиксированное количество элементов , которое вряд ли изменится, и вы хотите обращаться к нему непоследовательным образом.

  • Исправленный размер
  • Быстрый доступ - O (1)
  • Медленное изменение размера - O (n) - необходимо скопировать каждый элемент в новый массив!

Связанные списки оптимизированы для быстрого добавления и удаления с обоих концов, но медленный доступ к середине.

  • Размер переменной
  • Медленный доступ в середине - O (n)
    • Необходимо пройти каждый элемент, начиная с головы, чтобы достичь желаемого индекса
  • Быстрый доступ в голову - O (1)
  • Потенциально быстрый доступ в хвост
    • O (1), если ссылка хранится в конце (как в случае двусвязного списка)
    • O (n), если ссылка не сохраняется (такая же сложность, как и доступ к узлу в середине)

Списки массивов (такие как List<T>в C #!) Представляют собой смесь двух, с довольно быстрыми добавлениями и произвольным доступом. List<T> часто будет вашей коллекцией, когда вы не уверены, что использовать.

  • Использует массив в качестве вспомогательной структуры
  • Умно относится к его изменению размера - выделяет вдвое больше своего текущего пространства, когда у него заканчивается.
    • Это приводит к изменению размера O (log n), что лучше, чем изменение размера каждый раз, когда мы добавляем / удаляем
  • Быстрый доступ - O (1)

Как работают массивы

Большинство языков моделируют массивы как непрерывные данные в памяти, каждый из которых имеет одинаковый размер. Допустим, у нас был массив ints (показанный как [адрес: значение] с использованием десятичных адресов, потому что я ленивый)

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

Каждый из этих элементов представляет собой 32-разрядное целое число, поэтому мы знаем, сколько места он занимает в памяти (32 бита!). И мы знаем адрес памяти указателя на первый элемент.

Получить значение любого другого элемента в этом массиве довольно просто:

  • Взять адрес первого элемента
  • Возьмите смещение каждого элемента (его размер в памяти)
  • Умножьте смещение на нужный индекс
  • Добавьте свой результат по адресу первого элемента

Допустим, наш первый элемент в '0'. Мы знаем, что наш второй элемент находится в '32' (0 + (32 * 1)), и наш третий элемент находится в 64 (0 + (32 * 2)).

Тот факт, что мы можем хранить все эти значения рядом друг с другом в памяти, означает, что наш массив настолько компактен, насколько это возможно. Это также означает, что все наши элементы должны оставаться вместе, чтобы вещи продолжали работать!

Как только мы добавляем или удаляем элемент, нам нужно собрать все остальное и скопировать их в какое-то новое место в памяти, чтобы убедиться, что между элементами нет промежутков, и всему есть достаточно места. Это может быть очень медленно , особенно если вы делаете это каждый раз, когда хотите добавить один элемент.

Связанные списки

В отличие от массивов, связанные списки не нуждаются в том, чтобы все их элементы находились рядом в памяти. Они состоят из узлов, которые хранят следующую информацию:

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

Сам список в большинстве случаев содержит ссылку на голову и хвост (первый и последний узлы), а иногда и отслеживает его размер.

Если вы хотите добавить элемент в конец списка, все, что вам нужно сделать, это получить хвост и изменить его, Nextчтобы он ссылался на новый, Nodeсодержащий ваше значение. Удаление с конца одинаково просто - просто разыменуйте Nextзначение предыдущего узла.

К сожалению, если у вас есть элемент LinkedList<T>с 1000 элементами и вы хотите элемент 500, нет простого способа перейти прямо к 500-му элементу, как с массивом. Вы должны начать с головы , и продолжать идти кNext узлу, пока не сделаете это 500 раз.

Вот почему добавление и удаление из a LinkedList<T>выполняется быстро (при работе на концах), но доступ к середине выполняется медленно.

Редактировать : Брайан указывает в комментариях, что связанные списки могут вызвать сбой страницы из-за того, что они не сохраняются в непрерывной памяти. Это может быть трудно для сравнения, и может сделать связанные списки даже немного медленнее, чем вы могли бы ожидать, учитывая только их сложность времени.

Лучшее обоих миров

List<T>компромиссы для обоих T[]иLinkedList<T> и предлагает решение, которое является достаточно быстрым и простым в использовании в большинстве ситуаций.

Внутренне, List<T>это массив! Он все еще должен перепрыгивать через копирование своих элементов при изменении размера, но он тянет некоторые изящные приемы.

Для начала, добавление одного элемента обычно не приводит к копированию массива. List<T>гарантирует, что всегда есть достаточно места для большего количества элементов. Когда он заканчивается, вместо выделения нового внутреннего массива только с одним новым элементом, он выделяет новый массив с несколькими новыми элементами (часто вдвое больше, чем в настоящее время!).

Операции копирования стоят дорого, поэтому List<T> сокращайте их как можно больше, но при этом допускайте быстрый произвольный доступ. Как побочный эффект, он может в конечном итоге тратить немного больше места, чем прямой массив или связанный список, но это обычно стоит компромисса.

TL; DR

Использование List<T>. Обычно это то, что вы хотите, и, кажется, это правильно для вас в этой ситуации (когда вы вызываете .Add ()). Если вы не уверены, что вам нужно, List<T>это хорошее место для начала.

Массивы хороши для высокопроизводительных вещей: «Я знаю, что мне нужны именно элементы X». В качестве альтернативы, они полезны для быстрой одноразовой структуры «Мне нужно сгруппировать эти вещи X, которые я уже определил, чтобы я мог зациклить их».

Есть ряд других классов коллекции. Stack<T>это как связанный список, который работает только сверху. Queue<T>работает как список «первым пришел - первым вышел». Dictionary<T, U>является неупорядоченным, ассоциативным отображением между ключами и значениями. Играйте с ними и узнайте сильные и слабые стороны каждого. Они могут сделать или сломать ваши алгоритмы.

KChaloux
источник
2
В некоторых случаях могут быть преимущества использования комбинации массива и intуказания количества используемых элементов. Помимо прочего, возможно массовое копирование нескольких элементов из одного массива в другой, но копирование между списками обычно требует индивидуальной обработки элементов. Кроме того, элементы массива могут передаваться refтаким вещам Interlocked.CompareExchange, как элементы списка, а не могут.
суперкат
2
Я хотел бы дать больше, чем один голос. Я знал различия в сценариях использования и как работали массивы / связанные списки, но я никогда не знал и не думал о том, как List<>работать под капотом.
Бобсон
1
Добавление одного элемента в список <T> амортизируется O (1); Эффективность добавления элементов обычно не является достаточным основанием для использования связанного списка (а круговой список позволяет добавлять в начало И обратно в амортизированном O (1)). Связанные списки имеют много особенностей производительности. Например, отсутствие непрерывного хранения в памяти означает, что итерации по всему связанному списку с большей вероятностью вызовут ошибку страницы ... и это трудно измерить. Большее оправдание для использования связанного списка - это когда вы хотите объединить два списка (можно сделать в O (1)) или добавить элементы в середину.
Брайан
1
Я должен уточнить. Когда я говорил круговой список, я имел в виду круговой список массивов, а не круговой связанный список. Правильный термин будет deque (двусторонняя очередь). Они часто реализуются почти так же, как List (массив под капотом), с одним исключением: существует внутреннее целочисленное значение «first», которое указывает, какой индекс массива является первым элементом. Чтобы добавить элемент в конец, вы просто вычитаете 1 из «первого» (при необходимости оборачивая до длины массива). Чтобы получить доступ к элементу, вы просто получите доступ (index+first)%length.
Брайан
2
Есть несколько вещей, которые вы не можете сделать с List, которые вы можете сделать с простым массивом, например, передав элемент index в качестве параметра ref.
Ян Голдби
6

Хотя ответ К.Чалу великолепен, я хотел бы отметить еще одно соображение: List<T>оно намного мощнее массива. МетодыList<T> очень полезны во многих обстоятельствах - у массива нет этих методов, и вы можете потратить много времени на реализацию обходных путей.

Таким образом, с точки зрения разработки я почти всегда использую, List<T>потому что когда есть дополнительные требования, их часто гораздо легче реализовать, когда вы используетеList<T> .

Это приводит к последней проблеме: мой код (я не знаю о вашем) содержит 90% List<T>, поэтому массивы не очень подходят. Когда я передаю их, мне приходится вызывать их .toList()метод и преобразовывать их в список - это раздражает и настолько медленный, что любой выигрыш в производительности при использовании массива теряется.

Кристиан Зауэр
источник
Это правда, это еще одна веская причина использовать List <T> - он предоставляет гораздо больше функциональных возможностей, встроенных непосредственно в класс.
KChaloux
1
Разве LINQ не выравнивает поле, добавляя большую часть этой функциональности для любого IEnumerable (включая массив)? Что-нибудь осталось в современном C # (4+), что вы можете делать только со списком <T>, а не с массивом?
Дейв
1
@ Дейв Расширение массива / списка кажется такой вещью. Кроме того, я бы сказал, что синтаксис для создания / обработки списка намного лучше, чем для массивов.
Кристиан Зауэр
2

Никто не упомянул эту часть, хотя: «И здесь я уже получаю исключение нехватки памяти». Что полностью связано с

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

Понятно, почему. Я не знаю, собирались ли вы добавить в другой список, или вам нужно просто сохранить ItemNumberList.Countкак переменную перед циклом, чтобы получить желаемый результат, но это просто не работает.

Programmers.SE для «... интересующихся концептуальными вопросами о разработке программного обеспечения ...», и другие ответы рассматривали его как таковой. Вместо этого попробуйте http://codereview.stackexchange.com , где этот вопрос подойдет. Но даже там это ужасно, так как мы можем только предполагать, что этот код начинается с того _Click, что нет вызова, multiValue1где вы говорите, что произошла ошибка.

Wolfzoon
источник