Discussion :

[takinelinfo]

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]

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]

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

[takinelinfo]

+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]

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

[brachior]

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 :

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]

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.