Vaut il mieux utiliser un Dictionary ou une Liste? (Performance)

**takinelinfo** · 03/08/2011, 22h48

Bonjour,
Je me pose une petite question. Je ne sais pas s’il vaut mieux que j’utilise une List<T> ou un Dictionary<int,T>. Je vais vous exposer mon cas.

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
 
//Mes classes
public class User
{
	public int Id { get; set; }
	public string Fullname { get; set; }
	public City City { get; set; }
}
 
public class City
{
	public int Id { get; set; }
	public string Type { get; set; }
}
 
//Ma méthode côté business
public void Blablalal()
{
	//Cas N°1
	List<User> userAll = DAL.Manager.GetUser();
	List<City> cityAll = DAL.Manager.GetCity();
 
	foreach (var oneUser in userAll)
		if (oneUser.City != null && oneUser.City.Id > 0)
			oneUser.City = cityAll.FirstOrDefault(c => c.Id == oneUser.City.Id);
 
 
	//Cas N°2
	Dictionary<int,User> userAll = DAL.Manager.GetUser();
	Dictionary<int,City> cityAll = DAL.Manager.GetCity();
 
	foreach (var oneUser in userAll.Values)
		if (oneUser.City != null && oneUser.City.Id > 0)
			if(cityAll.ContainsKey(oneUser.City.Id))
				oneUser.City = cityAll[oneUser.City.Id];
 
}

La question que je me pose est la suivante. Imaginons un nombre important de villes et de personnes, laquelle des deux méthodes sera la plus rapide d'après vous?
Merci d'avance pour vos conseils.

**giova_fr** · 03/08/2011, 22h56

il me semble (à confirmer) que si tu as un tres grand nombre d'elements, le dictionnaire deviendra lent que la list (probleme de collision de hashcode).

**jeremm** · 03/08/2011, 23h15

+1 pour le List<>.
De base il est toujours plus rapide de comparer des int que des strings.

**takinelinfo** · 04/08/2011, 00h22

Envoyé par jeremm

+1 pour le List<>.
De base il est toujours plus rapide de comparer des int que des strings.

Dans mes 2 cas, il y a une comparaison sur un int non?

Code c# :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
if(cityAll.ContainsKey(oneUser.City.Id))
    oneUser.City = cityAll[oneUser.City.Id];

C'est marrant, j'aurais dit que c'était le Dictionary le plus rapide.
Je pensais qu'accéder à un indice était plus rapide que de tout parcourir pour trouver un élément. Mais je ne connais pas le fonctionnement de ContainsKey et je me lance en C#. En tout cas merci pour vos réponses.

**takinelinfo** · 04/08/2011, 00h23

Dictionary plus performant?!?!
Je viens de tomber sur ça C# Dictionary Versus List Lookup Time

**brachior** · 04/08/2011, 09h40

une List et un Dictionary (Table de hachage) sont deux choses bien différentes ...
Au seul point qu'un Dictinary peut "simuler" une List ...

##################################
Pour une List :
- L'ajout en fin est en temps constant,
- L'ajout à un index précis doit l'être aussi (je ne connais pas l'implémentation de C#)

- La suppression d'un élément est elle en O(N) (où N est le nombre d'élément de la liste)
- Ou en temps constant si suppression d'un indice.

- La recherche d'un élément est en O(N) (possibilité d'améliorer par dichotomie si la liste est triée (O(log(N)))
- Ou en temps constant si demande d'un index

- Elle garde l'ordre d'entrée

##################################
Pour un Dictionary (Table de hachage)
- L'ajout, la suppression et la recherche sont en temps constant amorti
C'est à dire que le temps dépend de la fonction de hachage et de ses probabilités de collisions.

- Elle ne garde pas l'ordre d'entrée
- Difficulté pour trier

##################################
En principe, si les éléments doivent rester ordonnés, sont identifiables par un numéro unique et ordonné (0, 1, 2, 3, 4, ...), on préfèrera une liste : accès plus rapide ...

Si après, l'ordre importe peu, et que les éléments doivent être identifiable de façon plus complexe (id, nom, ...), il est préférable d'utiliser une table de hachage.

Dans ton exemple, je dirais sans hésiter que le Dictionary ira plus vite à long terme car il ne parcourra jamais la totalité de ta collection, tandis que la liste, si l'élément n'existe pas, elle ne le saura qu'en parcourant la totalité ...

EDIT :

Envoyé par giova_fr

il me semble (à confirmer) que si tu as un tres grand nombre d'elements, le dictionnaire deviendra lent que la list (probleme de collision de hashcode).

Pour qu'une table de hachage soit plus lent qu'une liste, il faut que ta fonction de hachage soit truquée ...

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
 
public override int GetHashCode()
{
  return 45;
}

Et encore, si la table est à hachage ouvert, alors tu auras la même complexité qu'avec une liste (car tu n'auras en réalité qu'un table d'une liste ^^)

**meziantou** · 04/08/2011, 09h43

Un dictionnaire permet de faire une recherche de clé en temps contant (en général). Si la fonction de hash est mal faite, tu peux avoir beaucoup de collisions et dans ce cas tu perds l'intérêt du dictionnaire. Si elle est trop longue à calculer la recherche prendra aussi beaucoup de temps.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
 
if(cityAll.ContainsKey(oneUser.City.Id))
    oneUser.City = cityAll[oneUser.City.Id];

Tu peux utiliser la fonction TryGetValue à la place. Ca te fera gagner un peu de temps

Dans ton cas tu dois pouvoir utiliser une table de hashage à la place d'un dictionnaire.

Autre solution : faire une liste triée et une recherche dichotomique.

**meziantou** · 04/08/2011, 09h57

Envoyé par brachior

Pour une List :
- L'ajout en fin est en temps constant,
- L'ajout à un index précis doit l'être aussi (je ne connais pas l'implémentation de C#)

- La suppression d'un élément est elle en O(N) (où N est le nombre d'élément de la liste)
- Ou en temps constant si suppression d'un indice.

- Elle garde l'ordre d'entrée

L'ajout d'un élément ne peut pas être en temps constant dans une List<T>. En effet ce type de liste utilise un tableau pour stocker les valeurs. Si celui-ci est plein avant d'ajouter un nouvel élément, il faut en allouer un nouveau et y copier toutes les valeurs.
Pour ce qui est de la suppression, leur implémentation conserve l'ordre des éléments donc si tu supprimes le premier élément, il faut décaler tous les éléments du tableau donc en O(N).

**brachior** · 04/08/2011, 10h13

Envoyé par meziantou

L'ajout d'un élément ne peut pas être en temps constant dans une List<T>. En effet ce type de liste utilise un tableau pour stocker les valeurs. Si celui-ci est plein avant d'ajouter un nouvel élément, il faut en allouer un nouveau et y copier toutes les valeurs.
Pour ce qui est de la suppression, leur implémentation conserve l'ordre des éléments donc si tu supprimes le premier élément, il faut décaler tous les éléments du tableau donc en O(N).

C# étant un gentil petit langage propriétaire,
Je ne sais pas comment il est codé à l'intérieur (et je ne vais pas m'amuser à le désassembler ...)
Mais je doute que le GC s'amuse à faire des recopies à tout va (du moins je l'espère ...)
Qui plus est, la recopie sera faite dans un langage plus bas niveau que C# (via la VM, par exemple avec un memset en C)
De plus, l'agrandissement d'une liste, ou tout autre collection, est fait de manière à éviter des allocations multiples.
Pour cela, en règle générale, la taille de la collection est doublée (diffère selon les langage ^^)
Ajoutant à ça que le GC est sensé gérer la mémoire, et prévoir certaines allocations.
Donc on peut considérer qu'un ajout est en temps constant.

Pour la suppression, même combat ^^
Je ne sais pas comment C# l'implémente,
Mais il a bien des façons de gérer des listes, et si List<T> ne diffère pas de T[] ...
Alors oui, ça pose un soucis ...

**Nathanael Marchand** · 04/08/2011, 10h27

Envoyé par brachior

C# étant un gentil petit langage propriétaire,
Je ne sais pas comment il est codé à l'intérieur (et je ne vais pas m'amuser à le désassembler ...)

C'est de .Net la dont on parle et les sources de .Net sont en libre consultation!

**meziantou** · 04/08/2011, 10h31

Envoyé par brachior

Qui plus est, la recopie sera faite dans un langage plus bas niveau que C# (via la VM, par exemple avec un memset en C)
De plus, l'agrandissement d'une liste, ou tout autre collection, est fait de manière à éviter des allocations multiples.
Pour cela, en règle générale, la taille de la collection est doublée (diffère selon les langage ^^)
Ajoutant à ça que le GC est sensé gérer la mémoire, et prévoir certaines allocations.
Donc on peut considérer qu'un ajout est en temps constant.

Pour la suppression, même combat ^^
Je ne sais pas comment C# l'implémente,
Mais il a bien des façons de gérer des listes, et si List<T> ne diffère pas de T[] ...
Alors oui, ça pose un soucis ...

L'ajout est en temps constant amorti.

Voila le code pour le changement de taille du tableau

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
 if (value != this._items.Length)
        {
            if (value > 0)
            {
                T[] destinationArray = new T[value];
                if (this._size > 0)
                {
                    Array.Copy(this._items, 0, destinationArray, 0, this._size);
                }
                this._items = destinationArray;
            }
            else
            {
                this._items = List<T>._emptyArray;
            }
         }

et celui pour la suppression

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
 
    this._size--;
    if (index < this._size)
    {
        Array.Copy(this._items, index + 1, this._items, index, this._size - index);
    }
    this._items[this._size] = default(T);
    this._version++;

**Nathanael Marchand** · 04/08/2011, 10h39

Ah tiens c'est rigolo, j'ai pas la même chose

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
 
public class List<T> : IList<T>, ICollection<T>, IEnumerable<T>, IList, ICollection, IEnumerable
  {
    private static readonly T[] _emptyArray = new T[0];
    private const int _defaultCapacity = 4;
    private T[] _items;
    private int _size;
    private int _version;
 
    public int Capacity
    {
      get
      {
        return this._items.Length;
      }
      set
      {
        if (value < this._size)
          ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.value, ExceptionResource.ArgumentOutOfRange_SmallCapacity);
        if (value == this._items.Length)
          return;
        if (value > 0)
        {
          T[] objArray = new T[value];
          if (this._size > 0)
            Array.Copy((Array) this._items, 0, (Array) objArray, 0, this._size);
          this._items = objArray;
        }
        else
          this._items = List<T>._emptyArray;
      }
    }
 
    static List()
    {
    }
 
    public List()
    {
      this._items = List<T>._emptyArray;
    }
 
    public void Add(T item)
    {
      if (this._size == this._items.Length)
        this.EnsureCapacity(this._size + 1);
      this._items[this._size++] = item;
      ++this._version;
    }
 
    private void EnsureCapacity(int min)
    {
      if (this._items.Length >= min)
        return;
      int num = this._items.Length == 0 ? 4 : this._items.Length * 2;
      if (num < min)
        num = min;
      this.Capacity = num;
    }
 
    public void Insert(int index, T item)
    {
      if ((uint) index > (uint) this._size)
        ThrowHelper.ThrowArgumentOutOfRangeException(ExceptionArgument.index, ExceptionResource.ArgumentOutOfRange_ListInsert);
      if (this._size == this._items.Length)
        this.EnsureCapacity(this._size + 1);
      if (index < this._size)
        Array.Copy((Array) this._items, index, (Array) this._items, index + 1, this._size - index);
      this._items[index] = item;
      ++this._size;
      ++this._version;
    }
 
    public bool Remove(T item)
    {
      int index = this.IndexOf(item);
      if (index < 0)
        return false;
      this.RemoveAt(index);
      return true;
    }
 
    public void RemoveAt(int index)
    {
      if ((uint) index >= (uint) this._size)
        ThrowHelper.ThrowArgumentOutOfRangeException();
      --this._size;
      if (index < this._size)
        Array.Copy((Array) this._items, index + 1, (Array) this._items, index, this._size - index);
      this._items[this._size] = default (T);
      ++this._version;
    }
  }

Edit: Au temps pour moi, j'ai sorti l'implem' du runtime Silverlight

Edit2: Ah si tiens c'est la meme chose, je regardais pas au bon endroit

**meziantou** · 04/08/2011, 10h47

J'utilise reflector 6.8 pour décompiler.

**brachior** · 04/08/2011, 10h49

Donc C# est écrit en ... 100% C# Oo ... ... ...

J'aime décidément pas ce langage =/
En espérant que le Array.Copy soit pas une simple boucle Oo

@Nathanael : Ta capacité est en dur ... C'est pas normal Oo

**meziantou** · 04/08/2011, 11h00

Envoyé par brachior

Donc C# est écrit en ... 100% C# Oo ... ... ...

Ta phrase ne veut pas dire grand chose.

Envoyé par brachior

En espérant que le Array.Copy soit pas une simple boucle Oo

Le copy est un appel vers une fonction native.

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
[MethodImpl(MethodImplOptions.InternalCall), SecurityCritical, ReliabilityContract(Consistency.MayCorruptInstance, Cer.MayFail)]
internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);

**Nathanael Marchand** · 04/08/2011, 11h04

J'ai fait quelques changements, il manquait des bouts interessants.

Pour le Array.Copy, voici la définition:

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
[MethodImplAttribute(MethodImplOptions.InternalCall)]
        internal static extern void Copy(Array sourceArray, int sourceIndex, Array destinationArray, int destinationIndex, int length, bool reliable);

On remarque le MethodImplOptions.InternalCall qui signifie que c'est une opération bas niveau.

Edit: Roh meziantou, t'as pas fini de me doubler ??

**brachior** · 04/08/2011, 11h41

Reste à savoir comme il gère les tableau maintenant ^^

Enfin, reste que pour la question de takinelinfo,
Un Dictionary est à privilégier ^^

**Guulh** · 04/08/2011, 13h49

Envoyé par brachior

Donc C# est écrit en ... 100% C# Oo ... ... ...

Non, comme te le montre meziantou. Sans compter qu'une assembly n'a pas de langage; c'est du bytecode .Net en MSIL.

Et même: qu'est ce qui te choque ?
La STL est écrite en C++.
La lib java, comme celle de C#, est constituée d'un wrapping de fonctions natives et de code java.
Les libs python, ruby, perl, .. pareil.

Pas de quoi vomir, hein.

Un Dictionary est à privilégier ^^

Ca dépend de la volumétrie et des traitements faits dessus. Si on doit souvent récupérer les objets par leur id, par exemple au sein d'un parcours O(n²) ou pire, on pourra y gagner. Mais si ce n'est que quelques milliers de records, c'est peanuts de toutes façons

La doc est complète, auatnt aller la voir, non ?
List -> http://msdn.microsoft.com/en-us/library/6sh2ey19.aspx
List.Add -> http://msdn.microsoft.com/en-us/library/3wcytfd1.aspx

Add: If Count is less than Capacity, this method is an O(1) operation. If the capacity needs to be increased to accommodate the new element, this method becomes an O(n) operation, where n is Count.

Vaut il mieux utiliser un Dictionary ou une Liste? (Performance)

C#

Discussions similaires

Partager

Partager