Performances des tableaux et des listes

Question

Supposons que vous ayez besoin d'une liste/un tableau d'entiers que vous devez itérer fréquemment, et je veux dire extrêmement souvent. Les raisons peuvent varier, mais disons que c'est au cœur de la boucle la plus interne d'un traitement à haut volume.

En général, on opte pour l'utilisation des listes (List) en raison de leur flexibilité en termes de taille. De plus, la documentation msdn affirme que les listes utilisent un tableau en interne et devraient être aussi rapides (un rapide coup d'œil avec Reflector le confirme). Néanmoins, il y a une certaine surcharge.

Est-ce que quelqu'un a réellement mesuré cela ? Est-ce que itérer 6M fois dans une liste prendrait le même temps qu'un tableau ?

Answer 1

Très facile à mesurer...

Dans un petit nombre de code de traitement en boucle serrée où je sais que la longueur est fixe J'utilise les tableaux pour ce petit plus de micro-optimisation ; les tableaux peuvent être marginalement plus rapide si vous utilisez l'indexeur / pour le formulaire - mais IIRC croit que cela dépend du type de données dans le tableau. Mais à moins que vous besoin de de micro-optimiser, de rester simple et d'utiliser List<T> etc.

Bien entendu, cela ne s'applique que si vous lisez toutes les données ; un dictionnaire serait plus rapide pour les recherches par clé.

Voici mes résultats en utilisant "int" (le deuxième chiffre est une somme de contrôle pour vérifier qu'ils ont tous fait le même travail) :

(édité pour corriger le bug)

List/for: 1971ms (589725196)
Array/for: 1864ms (589725196)
List/foreach: 3054ms (589725196)
Array/foreach: 1860ms (589725196)

basé sur le banc d'essai :

using System;
using System.Collections.Generic;
using System.Diagnostics;
static class Program
{
    static void Main()
    {
        List<int> list = new List<int>(6000000);
        Random rand = new Random(12345);
        for (int i = 0; i < 6000000; i++)
        {
            list.Add(rand.Next(5000));
        }
        int[] arr = list.ToArray();

        int chk = 0;
        Stopwatch watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = list.Count;
            for (int i = 0; i < len; i++)
            {
                chk += list[i];
            }
        }
        watch.Stop();
        Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            for (int i = 0; i < arr.Length; i++)
            {
                chk += arr[i];
            }
        }
        watch.Stop();
        Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in list)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in arr)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        Console.ReadLine();
    }
}

Answer 2

Je pense que les performances seront assez similaires. La surcharge qui est impliquée dans l'utilisation d'une liste par rapport à un tableau est, à mon avis, lorsque vous ajoutez des éléments à la liste, et lorsque la liste doit augmenter la taille du tableau qu'elle utilise en interne, lorsque la capacité du tableau est atteinte.

Supposons que vous ayez une liste avec une capacité de 10, alors la liste augmentera sa capacité une fois que vous voudrez ajouter le 11ème élément. Vous pouvez réduire l'impact sur les performances en initialisant la capacité de la liste au nombre d'éléments qu'elle contiendra.

Mais, pour savoir si l'itération sur une liste est aussi rapide que l'itération sur un tableau, pourquoi ne pas l'évaluer ?

int numberOfElements = 6000000;

List<int> theList = new List<int> (numberOfElements);
int[] theArray = new int[numberOfElements];

for( int i = 0; i < numberOfElements; i++ )
{
    theList.Add (i);
    theArray[i] = i;
}

Stopwatch chrono = new Stopwatch ();

chrono.Start ();

int j;

 for( int i = 0; i < numberOfElements; i++ )
 {
     j = theList[i];
 }

 chrono.Stop ();
 Console.WriteLine (String.Format("iterating the List took {0} msec", chrono.ElapsedMilliseconds));

 chrono.Reset();

 chrono.Start();

 for( int i = 0; i < numberOfElements; i++ )
 {
     j = theArray[i];
 }

 chrono.Stop ();
 Console.WriteLine (String.Format("iterating the array took {0} msec", chrono.ElapsedMilliseconds));

 Console.ReadLine();

Sur mon système, l'itération sur le tableau a pris 33msec ; l'itération sur la liste a pris 66msec.

Pour être honnête, je ne m'attendais pas à ce que la variation soit si importante. Donc, j'ai mis mon itération dans une boucle : maintenant, j'exécute les deux itérations 1000 fois. Les résultats sont :

l'itération de la liste a pris 67146 msec L'itération du tableau prend 40821 msec

Aujourd'hui, l'écart n'est plus aussi important, mais il reste...

J'ai donc lancé .NET Reflector, et le getter de l'indexeur de la classe List ressemble à ceci :

public T get_Item(int index)
{
    if (index >= this._size)
    {
        ThrowHelper.ThrowArgumentOutOfRangeException();
    }
    return this._items[index];
}

Comme vous pouvez le constater, lorsque vous utilisez l'indexeur de la liste, cette dernière vérifie si vous ne sortez pas des limites du tableau interne. Cette vérification supplémentaire a un coût.

Answer 3

Si vous ne récupérez qu'une seule valeur de l'un ou l'autre (pas dans une boucle), les deux font le contrôle des limites (vous êtes dans du code géré, rappelez-vous), c'est juste la liste qui le fait deux fois. Voir les notes plus loin pour savoir pourquoi ce n'est pas un gros problème.

Si vous utilisez votre propre for(int i = 0 ; i < x.[Length/Count];i++), la différence essentielle est la suivante :

• Array :
  • la vérification des limites est supprimée
• Listes
  • la vérification des limites est effectuée

Si vous utilisez foreach, la différence essentielle est la suivante :

• Array :
  • aucun objet n'est alloué pour gérer l'itération
  • la vérification des limites est supprimée
• List via une variable connue pour être List.
  • la variable de gestion des itérations est allouée à la pile
  • la vérification des limites est effectuée
• Liste via une variable connue pour être IList.
  • la variable de gestion des itérations est allouée au tas
  • la vérification des limites est effectuée De plus, les valeurs des listes ne peuvent pas être modifiées pendant le foreach alors que celles des tableaux peuvent l'être.

La vérification des limites n'est souvent pas un gros problème (surtout si vous êtes sur un processeur avec un pipeline profond et une prédiction de branchement - la norme pour la plupart de nos jours) mais seul votre propre profilage peut vous dire si c'est un problème. Si vous êtes dans des parties de votre code où vous évitez les allocations de tas (de bons exemples sont les bibliothèques ou les implémentations de hashcode), alors s'assurer que la variable est typée comme List et non IList évitera ce piège. Comme toujours, profitez-en si cela est important.

Answer 4

[ Voir aussi cette question ]

J'ai modifié la réponse de Marc pour utiliser des nombres aléatoires réels et faire le même travail dans tous les cas.

Résultats :

         for      foreach
Array : 1575ms     1575ms (+0%)
List  : 1630ms     2627ms (+61%)
         (+3%)     (+67%)

(Checksum: -1000038876)

Compilé comme Release sous VS 2008 SP1. Fonctionne sans débogage sur un Q6600@2.40GHz, .NET 3.5 SP1.

Code :

class Program
{
    static void Main(string[] args)
    {
        List<int> list = new List<int>(6000000);
        Random rand = new Random(1);
        for (int i = 0; i < 6000000; i++)
        {
            list.Add(rand.Next());
        }
        int[] arr = list.ToArray();

        int chk = 0;
        Stopwatch watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = list.Count;
            for (int i = 0; i < len; i++)
            {
                chk += list[i];
            }
        }
        watch.Stop();
        Console.WriteLine("List/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            int len = arr.Length;
            for (int i = 0; i < len; i++)
            {
                chk += arr[i];
            }
        }
        watch.Stop();
        Console.WriteLine("Array/for: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in list)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("List/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);

        chk = 0;
        watch = Stopwatch.StartNew();
        for (int rpt = 0; rpt < 100; rpt++)
        {
            foreach (int i in arr)
            {
                chk += i;
            }
        }
        watch.Stop();
        Console.WriteLine("Array/foreach: {0}ms ({1})", watch.ElapsedMilliseconds, chk);
        Console.WriteLine();

        Console.ReadLine();
    }
}

Answer 5

Les mesures sont intéressantes, mais vous obtiendrez des résultats très différents selon ce que vous faites exactement dans votre boucle intérieure. Mesurez votre propre situation. Si vous utilisez le multithreading, cela représente à lui seul une activité non triviale.