¿Debo usar una lista o una matriz?

Estoy trabajando en un formulario de Windows para calcular el UPC para los números de artículo.

Creé con éxito uno que manejará un número de artículo / UPC a la vez, ahora quiero expandirlo y hacerlo para múltiples números de artículo / UPC.

Empecé e intenté usar una lista, pero sigo atascado. Creé una clase auxiliar:

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

}

Luego comencé con mi código, pero el problema es que el proceso es incremental, lo que significa que obtengo el número de artículo de una vista de cuadrícula a través de casillas de verificación y los pongo en la lista. Luego obtengo el último UPC de la base de datos, quito el dígito de control, luego incremento el número en uno y lo pongo en la lista. Luego calculo el dígito de control para el nuevo número y lo pongo en la lista. Y aquí ya tengo una excepción de memoria insuficiente. Aquí está el código que tengo hasta ahora:

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

¿Es esta la forma correcta de hacerlo, usando una lista, o debería mirar de otra manera?

c# array winforms list campagnolo_1
fuente

Usar una lista está bien. Iterar la lista mientras se agrega es una forma segura de hacer explotar su código e indica un problema en su lógica (o escritura de código). Además, este es su error y no es probable que ayude a futuros visitantes. Votación para cerrar.

Telastyn

Como nota al margen, todos estos campos privados (en su Codeclase) son redundantes y nada más que ruido realmente { get; private set; }sería suficiente.

Konrad Morawski

¿El título de la pregunta para esto es realmente preciso? Esto realmente no parece una pregunta de lista vs matriz , sino una pregunta sobre cómo puedo mejorar mi pregunta de implementación . Dicho esto, si está agregando o eliminando elementos, desea una lista (u otra estructura de datos flexible). Las matrices solo son realmente buenas cuando sabes exactamente cuántos elementos necesitas al principio.

KChaloux

@KChaloux, eso es más o menos lo que quería saber. ¿Es una lista la forma correcta de hacer esto, o debería haber buscado una forma diferente de seguir esto? Parece que una lista es una buena manera, solo tengo que ajustar mi lógica.

campagnolo_1

@Telastyn, no pedía tanto mejorar mi código como mostrar lo que estoy tratando de hacer.

campagnolo_1

Respuestas:

Ampliaré mi comentario:

... si agrega o elimina elementos, desea una lista (u otra estructura de datos flexible). Las matrices solo son realmente buenas cuando sabes exactamente cuántos elementos necesitas al principio.

Un desglose rápido

Las matrices son buenas cuando tiene un número fijo de elementos que es poco probable que cambie, y desea acceder a él de manera no secuencial.

Tamaño fijo
Acceso rápido - O (1)
Cambio de tamaño lento - O (n) - ¡necesita copiar cada elemento a una nueva matriz!

Las listas enlazadas están optimizadas para adiciones y eliminaciones rápidas en cualquier extremo, pero son de acceso lento en el medio.

Tamaño variable
Acceso lento en el medio - O (n)
- Necesita atravesar cada elemento comenzando desde la cabeza para alcanzar el índice deseado
Acceso rápido a la cabeza - O (1)
Acceso potencialmente rápido en Tail
- O (1) si una referencia se almacena al final de la cola (como con una lista doblemente vinculada)
- O (n) si no se almacena ninguna referencia (misma complejidad que acceder a un nodo en el medio)

Las listas de matrices (como List<T>en C #!) Son una mezcla de las dos, con adiciones bastante rápidas y acceso aleatorio. List<T> a menudo será su colección favorita cuando no esté seguro de qué usar.

Utiliza una matriz como estructura de respaldo
Es inteligente acerca de su cambio de tamaño: asigna el doble de su espacio actual cuando se queda sin él.
- Esto conduce a un cambio de tamaño de O (log n), que es mejor que cambiar el tamaño cada vez que agregamos / eliminamos
Acceso rápido - O (1)

Cómo funcionan las matrices

La mayoría de los lenguajes modelan matrices como datos contiguos en la memoria, de los cuales cada elemento tiene el mismo tamaño. Digamos que teníamos una matriz de ints (mostrada como [dirección: valor], usando direcciones decimales porque soy vago)

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

Cada uno de estos elementos es un número entero de 32 bits, por lo que sabemos cuánto espacio ocupa en la memoria (¡32 bits!). Y sabemos la dirección de memoria del puntero al primer elemento.

Es trivialmente fácil llegar al valor de cualquier otro elemento en esa matriz:

Toma la dirección del primer elemento
Tome el desplazamiento de cada elemento (su tamaño en la memoria)
Multiplica el desplazamiento por el índice deseado
Agregue su resultado a la dirección del primer elemento

Digamos que nuestro primer elemento está en '0'. Sabemos que nuestro segundo elemento está en '32' (0 + (32 * 1)), y nuestro tercer elemento está en 64 (0 + (32 * 2)).

El hecho de que podamos almacenar todos estos valores uno al lado del otro en la memoria significa que nuestra matriz es lo más compacta posible. ¡También significa que todos nuestros elementos deben permanecer juntos para que las cosas sigan funcionando!

Tan pronto como agreguemos o eliminemos un elemento, debemos recoger todo lo demás y copiarlos en algún lugar nuevo en la memoria, para asegurarnos de que no haya espacios entre los elementos y que todo tenga suficiente espacio. Esto puede ser muy lento , especialmente si lo hace cada vez que desea agregar un solo elemento.

Listas vinculadas

A diferencia de las matrices, las listas enlazadas no necesitan que todos sus elementos estén uno al lado del otro en la memoria. Están compuestos por nodos, que almacenan la siguiente información:

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

La lista en sí misma mantiene una referencia a la cabeza y la cola (primer y último nodo) en la mayoría de los casos, y a veces realiza un seguimiento de su tamaño.

Si desea agregar un elemento al final de la lista, todo lo que necesita hacer es obtener la cola y cambiarla Nextpara hacer referencia a una nueva que Nodecontenga su valor. Eliminar desde el final es igualmente simple: simplemente desreferenciar el Nextvalor del nodo anterior.

Desafortunadamente, si tiene un LinkedList<T>elemento con 1000 elementos y desea el elemento 500, no hay una manera fácil de saltar directamente al elemento número 500 como lo hay con una matriz. Debe comenzar en la cabeza y continuar hacia el Nextnodo, hasta que lo haya hecho 500 veces.

Esta es la razón por la cual agregar y eliminar de a LinkedList<T>es rápido (cuando se trabaja en los extremos), pero acceder al medio es lento.

Editar : Brian señala en los comentarios que las listas enlazadas tienen el riesgo de causar un error de página, debido a que no se almacenan en la memoria contigua. Esto puede ser difícil de evaluar, y puede hacer que las Listas Vinculadas sean incluso un poco más lentas de lo que cabría esperar dada su complejidad de tiempo.

Lo mejor de ambos mundos

List<T>compromete a ambos T[]y LinkedList<T>presenta una solución razonablemente rápida y fácil de usar en la mayoría de las situaciones.

Internamente, List<T>es una matriz! Todavía tiene que saltar a través de los aros de copiar sus elementos al cambiar el tamaño, pero hace algunos trucos geniales.

Para empezar, agregar un solo elemento generalmente no hace que la matriz se copie. List<T>se asegura de que siempre haya suficiente espacio para más elementos. Cuando se agota, en lugar de asignar una nueva matriz interna con un solo elemento nuevo, asignará una nueva matriz con varios elementos nuevos (¡a menudo el doble de lo que tiene actualmente!).

Las operaciones de copia son caras, por lo que debe List<T>reducirlas tanto como sea posible, al tiempo que permite un acceso aleatorio rápido. Como efecto secundario, puede terminar desperdiciando un poco más de espacio que una matriz directa o una lista vinculada, pero generalmente vale la pena el compromiso.

TL; DR

Uso List<T>. Normalmente es lo que desea, y parece ser correcto para usted en esta situación (donde está llamando .Add ()). Si no está seguro de lo que necesita, List<T>es un buen lugar para comenzar.

Las matrices son buenas para cosas de alto rendimiento, "Sé que necesito exactamente elementos X". Alternativamente, son útiles para estructuras rápidas y únicas "Necesito agrupar estas X cosas que ya he definido juntas para poder recorrerlas".

Hay varias otras clases de colección. Stack<T>es como una lista vinculada que solo opera desde arriba. Queue<T>funciona como una lista de primero en entrar, primero en salir. Dictionary<T, U>es un mapeo asociativo desordenado entre claves y valores. Juega con ellos y conoce las fortalezas y debilidades de cada uno. Pueden hacer o deshacer sus algoritmos.

KChaloux
fuente

En algunos casos, puede haber ventajas al usar una combinación de una matriz e intindicar el número de elementos utilizables. Entre otras cosas, es posible copiar en masa múltiples elementos de una matriz a otra, pero la copia entre listas generalmente requiere el procesamiento de elementos individualmente. Además, los elementos de la matriz pueden pasarse refa cosas como Interlocked.CompareExchange, mientras que los elementos de la lista no.

supercat

Desearía poder dar más de un voto a favor. Sabía las diferencias de casos de uso y cómo funcionaban las matrices / listas vinculadas, pero nunca supe ni pensé en cómo List<>funcionaba bajo el capó.

Bobson

Agregar un solo elemento a una Lista <T> se amortiza O (1); la eficiencia de agregar elementos normalmente no es justificación suficiente para usar una lista vinculada (y una Lista circular le permite agregar al frente Y atrás en O (1) amortizado). Las listas vinculadas tienen muchas idiosincrasias de rendimiento. Por ejemplo, no estar almacenado de forma contigua en la memoria significa que iterar sobre una lista vinculada completa es más probable que provoque un error de página ... y esto es difícil de comparar. La mayor justificación para usar una Lista Vinculada es cuando desea concatenar dos listas (se puede hacer en O (1)) o agregar elementos en el medio.

Brian

Debo aclarar. Cuando dije lista circular, me refería a una lista de matriz circular, no a una lista enlazada circular. El término correcto sería deque (cola de doble extremo). A menudo se implementan casi de la misma manera que una Lista (matriz bajo el capó), con una excepción: hay un valor entero interno, "primero", que indica qué índice de la matriz es el primer elemento. Para agregar un elemento a la parte posterior, solo resta 1 de "primero" (si es necesario, ajusta la longitud de la matriz). Para acceder a un elemento, solo tienes que acceder (index+first)%length.

Brian

Hay algunas cosas que no puede hacer con una Lista que puede hacer con una matriz simple, por ejemplo, pasar un elemento de índice como parámetro de referencia.

Ian Goldby

Si bien la respuesta de KChaloux es excelente, me gustaría señalar otra consideración: List<T>es mucho más poderosa que una matriz. Los métodos de List<T>son muy útiles en muchas circunstancias: una matriz no tiene estos métodos y es posible que pase mucho tiempo para implementar soluciones alternativas.

Entonces, desde una perspectiva de desarrollo, casi siempre uso List<T>porque cuando hay requisitos adicionales, a menudo son mucho más fáciles de implementar cuando está utilizando a List<T>.

Esto lleva a un problema final: mi código (no sé sobre el suyo) contiene 90% List<T>, por lo que las matrices no encajan realmente. Cuando las paso, tengo que llamar a su .toList()método y convertirlos en una Lista: esto es molesto y es tan lento que se pierde cualquier ganancia de rendimiento al usar una matriz.

Christian Sauer
fuente

Es cierto, esta es otra buena razón para usar List <T>: proporciona mucha más funcionalidad incorporada directamente a la clase.

KChaloux

¿LINQ no nivela el campo al agregar mucha de esa funcionalidad para cualquier IEnumerable (incluida una matriz)? ¿Queda algo en C # (4+) moderno que solo pueda hacer con una Lista <T> y no con una matriz?

Dave

@Dave Extender la matriz / lista parece tal cosa. Además, diría que la sintaxis para construir / manejar una Lista es mucho mejor que para las matrices.

Christian Sauer

Sin embargo, nadie mencionó esta parte: "Y aquí ya tengo una excepción de memoria insuficiente". Lo cual se debe enteramente a

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

Es claro ver por qué. No sé si pretendía agregar a una lista diferente, o simplemente debe almacenar ItemNumberList.Countcomo una variable antes del ciclo para obtener el resultado deseado, pero esto simplemente se rompe.

Programmers.SE es para "... interesados en preguntas conceptuales sobre desarrollo de software ...", y las otras respuestas lo trataron como tal. Pruebe http://codereview.stackexchange.com en su lugar, donde encajaría esta pregunta. Pero incluso allí es horrible, ya que solo podemos suponer que este código comienza en _Click, que no tiene ninguna llamada a multiValue1donde usted dice que ocurre el error.

Wolfzoon
fuente