Dois-je utiliser une liste ou un tableau?

22

Je travaille sur un formulaire Windows pour calculer le CUP pour les numéros d'articles.

J'ai réussi à en créer un qui gérera un numéro d'article / UPC à la fois, maintenant je veux développer et le faire pour plusieurs numéros d'article / UPC.

J'ai commencé et essayé d'utiliser une liste, mais je reste bloqué. J'ai créé une classe d'aide:

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

}

Ensuite, j'ai commencé avec mon code, mais le problème est que le processus est incrémentiel, ce qui signifie que j'obtiens le numéro d'article d'une vue de grille via des cases à cocher et que je les mets dans la liste. Ensuite, j'obtiens le dernier UPC de la base de données, supprime le chiffre de contrôle, puis incrémente le nombre de un et le mets dans la liste. Ensuite, je calcule le chiffre de contrôle pour le nouveau numéro et le mets dans la liste. Et ici, je reçois déjà une exception de mémoire insuffisante. Voici le code que j'ai jusqu'à présent:

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

Est-ce la bonne façon de procéder, en utilisant une liste, ou devrais-je envisager une manière différente?

campagnolo_1
la source
L'utilisation d'une liste est très bien. Itérer la liste tout en l'ajoutant est un moyen infaillible de faire exploser votre code et indique un problème dans votre logique (ou écriture de code). C'est aussi votre bug et il est peu probable qu'il aide les futurs visiteurs. Voter pour clore.
Telastyn
2
En passant, tous ces champs privés (dans votre Codeclasse) sont redondants et rien que du bruit vraiment, { get; private set; }serait suffisant.
Konrad Morawski
5
Le titre de la question est-il vraiment exact? Cela ne semble pas vraiment être une question liste vs tableau , autant qu'une question Comment améliorer ma question d' implémentation . Cela étant dit, si vous ajoutez ou supprimez des éléments, vous voulez une liste (ou une autre structure de données flexible). Les tableaux ne sont vraiment bons que lorsque vous savez exactement de combien d'éléments vous avez besoin au début.
KChaloux
@KChaloux, c'est à peu près ce que je voulais savoir. Une liste est-elle la bonne façon de procéder, ou aurais-je dû envisager une autre façon de procéder? Il semble donc qu'une liste soit un bon moyen, je dois juste ajuster ma logique.
campagnolo_1
1
@Telastyn, je ne demandais pas tant à améliorer mon code qu'à montrer ce que j'essaie de faire.
campagnolo_1

Réponses:

73

Je développerai mon commentaire:

... si vous ajoutez ou supprimez des éléments, vous voulez une liste (ou une autre structure de données flexible). Les tableaux ne sont vraiment bons que lorsque vous savez exactement de combien d'éléments vous avez besoin au début.

Une ventilation rapide

Les tableaux sont efficaces lorsque vous disposez d'un nombre fixe d'éléments qui ne changeront probablement pas et que vous souhaitez y accéder de manière non séquentielle.

  • Taille fixe
  • Accès rapide - O (1)
  • Redimensionnement lent - O (n) - doit copier chaque élément dans un nouveau tableau!

Les listes liées sont optimisées pour des ajouts et des suppressions rapides à chaque extrémité, mais leur accès est lent au milieu.

  • Taille variable
  • Accès lent au milieu - O (n)
    • Doit traverser chaque élément à partir de la tête pour atteindre l'indice souhaité
  • Accès rapide en tête - O (1)
  • Accès potentiellement rapide à Tail
    • O (1) si une référence est stockée à l'extrémité arrière (comme avec une liste à double liaison)
    • O (n) si aucune référence n'est stockée (même complexité que l'accès à un nœud au milieu)

Les listes de tableaux (comme List<T>en C #!) Sont un mélange des deux, avec des ajouts assez rapides et un accès aléatoire. List<T> sera souvent votre collection préférée lorsque vous ne savez pas quoi utiliser.

  • Utilise un tableau comme structure de support
  • Est intelligent dans son redimensionnement - alloue le double de son espace actuel lorsqu'il en manque.
    • Cela entraîne des redimensionnements O (log n), ce qui est mieux que le redimensionnement chaque fois que nous ajoutons / supprimons
  • Accès rapide - O (1)

Fonctionnement des tableaux

La plupart des langages modélisent les tableaux sous forme de données contiguës en mémoire, dont chaque élément a la même taille. Disons que nous avions un tableau de ints (affiché comme [adresse: valeur], en utilisant des adresses décimales parce que je suis paresseux)

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

Chacun de ces éléments est un entier 32 bits, nous savons donc combien d'espace il prend en mémoire (32 bits!). Et nous connaissons l'adresse mémoire du pointeur vers le premier élément.

Il est trivialement facile d'obtenir la valeur de tout autre élément de ce tableau:

  • Prenez l' adresse du premier élément
  • Prendre le décalage de chaque élément (sa taille en mémoire)
  • Multipliez le décalage par l'index souhaité
  • Ajoutez votre résultat à l'adresse du premier élément

Disons que notre premier élément est à '0'. Nous savons que notre deuxième élément est à '32' (0 + (32 * 1)), et notre troisième élément est à 64 (0 + (32 * 2)).

Le fait que nous puissions stocker toutes ces valeurs côte à côte en mémoire signifie que notre tableau est aussi compact que possible. Cela signifie également que tous nos éléments doivent rester ensemble pour que les choses continuent à fonctionner!

Dès que nous ajoutons ou supprimons un élément, nous devons récupérer tout le reste et les copier dans un nouvel emplacement en mémoire, pour nous assurer qu'il n'y a pas d'espace entre les éléments et que tout a assez de place. Cela peut être très lent , surtout si vous le faites chaque fois que vous souhaitez ajouter un seul élément.

Listes liées

Contrairement aux tableaux, les listes liées n'ont pas besoin que tous leurs éléments soient côte à côte en mémoire. Ils sont composés de nœuds, qui stockent les informations suivantes:

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

La liste elle-même conserve une référence à la tête et à la queue (premier et dernier nœuds) dans la plupart des cas, et garde parfois une trace de sa taille.

Si vous souhaitez ajouter un élément à la fin de la liste, tout ce que vous avez à faire est d'obtenir la queue et de la modifier Nextpour référencer un nouveau Nodecontenant votre valeur. La suppression de la fin est également simple - il suffit de déréférencer la Nextvaleur du nœud précédent.

Malheureusement, si vous avez un LinkedList<T>avec 1000 éléments et que vous voulez l'élément 500, il n'y a pas de moyen facile de passer directement au 500e élément comme il en existe avec un tableau. Vous devez commencer par la tête et continuer jusqu'au Nextnœud jusqu'à ce que vous l'ayez fait 500 fois.

C'est pourquoi l'ajout et la suppression d'un LinkedList<T>fichier est rapide (lorsque vous travaillez aux extrémités), mais l'accès au milieu est lent.

Edit : Brian souligne dans les commentaires que les listes liées ont un risque de provoquer une erreur de page, car elles ne sont pas stockées dans la mémoire contiguë. Cela peut être difficile à évaluer et peut rendre les listes liées encore plus lentes que vous ne le pensez, étant donné leur complexité temporelle.

Le meilleur des deux mondes

List<T>compromis pour les deux T[]et LinkedList<T>propose une solution raisonnablement rapide et facile à utiliser dans la plupart des situations.

En interne, List<T>c'est un tableau! Il doit encore sauter à travers les cercles de copie de ses éléments lors du redimensionnement, mais il tire quelques astuces soignées.

Pour commencer, l'ajout d'un seul élément ne provoque généralement pas la copie du tableau. List<T>s'assure qu'il y a toujours assez de place pour plus d'éléments. Lorsqu'il s'épuise, au lieu d'allouer un nouveau tableau interne avec un seul nouvel élément, il alloue un nouveau tableau avec plusieurs nouveaux éléments (souvent deux fois plus qu'il ne le contient actuellement!).

Les opérations de copie sont coûteuses, donc les List<T>réduisent autant que possible, tout en permettant un accès aléatoire rapide. En tant qu'effet secondaire, cela peut finir par perdre un peu plus d'espace qu'un tableau droit ou une liste liée, mais cela vaut généralement le compromis.

TL; DR

Utilisez List<T>. C'est normalement ce que vous voulez, et cela semble être correct pour vous dans cette situation (où vous appelez .Add ()). Si vous n'êtes pas sûr de ce dont vous avez besoin, List<T>c'est un bon point de départ.

Les tableaux sont bons pour les choses hautes performances, "Je sais que j'ai besoin d'exactement les éléments X". Alternativement, ils sont utiles pour des structures rapides et uniques "J'ai besoin de regrouper ces X choses que j'ai déjà définies ensemble afin que je puisse les parcourir".

Il existe un certain nombre d'autres classes de collecte. Stack<T>est comme une liste chaînée qui fonctionne uniquement par le haut. Queue<T>fonctionne comme une liste premier entré, premier sorti. Dictionary<T, U>est un mappage associatif non ordonné entre les clés et les valeurs. Jouez avec eux et apprenez à connaître les forces et les faiblesses de chacun. Ils peuvent faire ou défaire vos algorithmes.

KChaloux
la source
2
Dans certains cas, il peut être avantageux d'utiliser une combinaison d'un tableau et d' intindiquer le nombre d'éléments utilisables. Entre autres, il est possible de copier en bloc plusieurs éléments d'un tableau à un autre, mais la copie entre les listes nécessite généralement de traiter les éléments individuellement. De plus, les éléments du tableau peuvent être passés refà des choses comme Interlocked.CompareExchange, contrairement aux éléments de liste.
supercat
2
J'aimerais pouvoir donner plus d'une voix positive. Je connaissais les différences de cas d'utilisation et le fonctionnement des tableaux / listes liées, mais je n'ai jamais su ni pensé à comment cela List<>fonctionnait sous le capot.
Bobson
1
L'ajout d'un seul élément à une liste <T> est amorti O (1); l'efficacité de l'ajout d'éléments n'est normalement pas une justification suffisante pour utiliser une liste chaînée (et une liste circulaire vous permet d'ajouter au recto ET au verso en O amorti (1)). Les listes liées ont beaucoup d'idiosyncrasies de performances. Par exemple, le fait de ne pas être stocké de manière contiguë dans la mémoire signifie que l'itération sur une liste chaînée entière est plus susceptible de déclencher un défaut de page ... et cela est difficile à évaluer. La plus grande justification de l'utilisation d'une liste liée est lorsque vous souhaitez concaténer deux listes (cela peut être fait dans O (1)) ou ajouter des éléments au milieu.
Brian
1
Je devrais clarifier. Quand j'ai dit liste circulaire, je voulais dire une liste de tableaux circulaires, pas une liste chaînée circulaire. Le terme correct serait deque (file d'attente à double extrémité). Ils sont souvent implémentés à peu près de la même manière qu'un List (tableau sous le capot), à une exception près: il existe une valeur entière interne, "first" qui indique quel index du tableau est le premier élément. Pour ajouter un élément à l'arrière, il suffit de soustraire 1 de "premier" (en enroulant autour de la longueur du tableau si nécessaire). Pour accéder à un élément, il vous suffit d'accéder (index+first)%length.
Brian
2
Il y a quelques choses que vous ne pouvez pas faire avec une liste que vous pouvez faire avec un tableau simple, par exemple, en passant un élément d'index en tant que paramètre ref.
Ian Goldby
6

Bien que la réponse de KChaloux soit excellente, je voudrais souligner une autre considération: List<T>est beaucoup plus puissant qu'un tableau. Les méthodes de List<T>sont très utiles dans de nombreuses circonstances - un tableau n'a pas ces méthodes et vous pouvez passer beaucoup de temps à implémenter des solutions de contournement.

Donc, du point de vue du développement, j'utilise presque toujours List<T>parce que lorsqu'il y a des exigences supplémentaires, elles sont souvent beaucoup plus faciles à mettre en œuvre lorsque vous utilisez a List<T>.

Cela conduit à un dernier problème: mon code (je ne connais pas le vôtre) contient 90% List<T>, donc les tableaux ne sont pas vraiment adaptés. Quand je les passe, je dois appeler leur .toList()méthode et les convertir en une liste - ce est ennuyeux et si lent que tout gain de performances lié à l'utilisation d'un tableau est perdu.

Christian Sauer
la source
C'est vrai, c'est une autre bonne raison d'utiliser List <T> - elle fournit beaucoup plus de fonctionnalités pour vous directement intégrées à la classe.
KChaloux
1
LINQ ne nivelle-t-il pas le champ en ajoutant beaucoup de cette fonctionnalité pour tout IEnumerable (y compris un tableau)? Y a-t-il quelque chose qui reste dans le C # (4+) moderne que vous ne pouvez faire qu'avec une liste <T> et non un tableau?
Dave
1
@Dave L'extension du tableau / liste semble une telle chose. De plus, je dirais que la syntaxe pour construire / gérer une liste est beaucoup plus agréable que pour les tableaux.
Christian Sauer
2

Personne n'a mentionné cette partie cependant: "Et ici, je reçois déjà une exception de mémoire insuffisante." Ce qui est entièrement dû à

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

Il est clair de voir pourquoi. Je ne sais pas si vous vouliez ajouter à une liste différente, ou si vous devez simplement stocker en ItemNumberList.Counttant que variable avant la boucle pour obtenir le résultat souhaité, mais cela est tout simplement cassé.

Programmers.SE est pour "... intéressé par les questions conceptuelles sur le développement de logiciels ...", et les autres réponses l'ont traité comme tel. Essayez plutôt http://codereview.stackexchange.com , où cette question pourrait convenir. Mais même là, c'est horrible, car nous pouvons seulement supposer que ce code commence à _Click, qui n'a aucun appel à l' multiValue1endroit où vous dites que l'erreur se produit.

Wolfzoon
la source