[Test] Proposition de Benchmark Hashtable/ArrayList/List ?

**Mose** · 10/08/2006, 15h51

Une petite appli assez con, pour tester les structures de données dynamiques intégrées à .Net :
* Hashtable
* ArrayList
* List generiques
Ca teste :
* ajout
* recherche
* suppression

Note : je n'ai pas .Net 2, j'aimerai beaucoup que qqn fasse le teste pour les List génériques (on peut utiliser les méthodes pour les IList).

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
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
[STAThread]
static void Main(string[] args)
{
    TestLists(100000);
}
 
static void TestLists(int max)
{
    // CREATION DU SAMPLE DE TEST
    string []sample = new string[max];
    // c'est un tableau de chaine uniques (la liste des <max> premier naturels)
    for(int i = 0; i < max; i++)
        sample[i] = i.ToString();
 
    // ma Hashtable de test
    Hashtable myHT = new Hashtable();
    // ajout
    TimeSpan HTadd = TestAjout(myHT, max, sample);
    Console.WriteLine("Hashtable - ajout : " + HTadd.ToString());
    // recherche
    TimeSpan HTsearch = TestRecherche(myHT, max);
    Console.WriteLine("Hashtable - recherche : " + HTsearch.ToString());
    // suppression
    TimeSpan HTsuppr = TestSuppr(myHT, max);
    Console.WriteLine("Hashtable - suppression : " + HTsuppr.ToString());
    Console.ReadLine();
 
    // ma ArrayList de test
    ArrayList myAL = new ArrayList();
    // ajout
    TimeSpan ALadd = TestAjout(myAL, max, sample);
    Console.WriteLine("ArrayList - ajout : " + HTadd.ToString());
    // recherche
    TimeSpan ALsearch = TestRecherche(myAL, max);
    Console.WriteLine("ArrayList - recherche : " + ALsearch.ToString());
    // suppression
    TimeSpan ALsuppr = TestSuppr(myAL, max);
    Console.WriteLine("ArrayList - suppression : " + ALsuppr.ToString());
    Console.ReadLine();
 
    // ajouter ici le code pour les List generiques
    // ##################################
    // #
    // #
    // ##################################
}
static TimeSpan TestAjout(IList list, int max, object[]sample)
{
    // timestamp de départ
    DateTime debut = DateTime.Now;
 
    for(int i = 0; i < max; i++)
        // j'ajoute mon sample dans la liste
        list.Add(sample[i]);
 
    return DateTime.Now - debut;
}
static TimeSpan TestRecherche(IList list, int max)
{
    DateTime debut = DateTime.Now;
 
    bool alors;
    // recherche (dans l'ordre inverse pour plus de complexité)
    for(int i = (max - 1); i >= 0; i--)
        // je lit simplement la valeur
        alors = list.Contains(i.ToString());
 
    return DateTime.Now - debut;
}
static TimeSpan TestSuppr(IList list, int max)
{
    DateTime debut = DateTime.Now;
 
    // supression, ni au début, ni à la fin
    while(list.Count > 5000)
        list.RemoveAt(5000);
 
    return DateTime.Now - debut;
}
static TimeSpan TestAjout(Hashtable list, int max, object[]sample)
{
    DateTime debut = DateTime.Now;
 
    for(int i = 0; i < max; i++)
        // j'ajoute mon sample dans la liste
        list.Add(i, sample[i]);
 
    return DateTime.Now - debut;
}
static TimeSpan TestRecherche(Hashtable list, int max)
{
    DateTime debut = DateTime.Now;
 
    bool alors;
    // recherche (dans l'ordre inverse pour plus de complexité)
    for(int i = (max - 1); i >= 0; i--)
        // je lit simplement la valeur
        alors = list.ContainsKey(i);
 
    return DateTime.Now - debut;
}
static TimeSpan TestSuppr(Hashtable list, int max)
{
    DateTime debut = DateTime.Now;
 
    // supression, ni au début, ni à la fin
    for(int i = 5000; i < max; i++)
        // je supprime la valeur identifiée par la chaine qu'elle représente
        list.Remove(i);
 
    return DateTime.Now - debut;
}

**Mose** · 10/08/2006, 15h53

Résultats pour Hashtable/ArrayList :

Hashtable:
* ajout : 16ms
* recherche : 16ms
* suppression : 16 ms

ArrayList
* ajout : 16ms
* recherche : 1mn 28s

* suppression : 11s 375ms

Moralité : gros tableau, ArrayList au poteau

**cinemania** · 10/08/2006, 22h32

Et il ta fallut tout cela pour t'en rendre compte ?
Cela vient de la nature de ces deux structures de données radicalement différentes.

En fait chacune de ses classe correspond à une structure différente, les dictionary ou hashtables sont fait pour les recherche par clé sur des flot de données plus ou moins gros. Le principe consiste à HASHER la clé et avoir une valeur, qui permet de sélectionner une banque de stockage. Ensuite dans chaque banque, on stoque dans une simple liste (arraylist) (l'implantation peut varier mais c'est le principe)
Donc si ton algorithme de hashage est bien fait... les différentes valeurs sont bien éparpillées dans les banques. et la recherche, sera d'autant plus rapide. Si tu as 10 banque et 10 valeurs et que chaque valeur se retrouve dans une banque différente, la recherche est en temps O(1) (unitaire)

Dans une liste ArrayList, ou n'importe quelle structure basée sur une liste, la recherche est en O(n) soit temps linéaire. Plus tu as d'éléments dans la liste et si l'élément est tout à la fin ,tu parcourera toute la liste pour la recherche, soit "n" opérations.

Voila pourquoi une hashtable EST TOUJOURS plus performante qu'une simple arraylist, en recherche. Après tout c'est le but, sinon ca sert pu à rien.

Ah oui, j'oubliais, si la clé est une chaine de caractère, dans une arraylist, tu dois comparé chaque objet et comparé octet par octet la chaine...
dans une hashtable, tu calcul un hashcode, et si ta du bol, tu as juste une comparaison supplémentaire à faire. C'est quand même nettement mieux.
Maintenant lorsque l'on utilise des chaines de caractères comme clé, on peut considérablement accélérer la recherche, mais ... la par contre c'est la mémoire et la quantité de données à stocker qui grossi, avec une méthode des Index (basé elle meme sur le hashage) Mais bon à ma connaissance, le framework ne possède pas d'implantation des Index, comme il ne possède pas d'implantation des skiplist ou des arbres bicolores.

**smikar** · 11/08/2006, 10h14

J'ajouterai que supprimer des éléments dans un ArrayList est également lent de par sa nature. Un ArrayList étant implémenté à l'aide d'un tableau, lorsque tu supprimes un élément, il faut décaler tous les suivants. Je te laisse imaginer le travail dans ton exemple où tu supprimes un élément en plein tableau un grand nombre de fois de suite. La suppression doit être de plus en plus rapide au fil des itérations étant donné que la fin du tableau se rapproche de ton indice d'effacement d'ailleurs. Tu veux une illustration ? Remplace ton code de suppression par :

Code :

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

1
2
while (l.Count > 5000)
                l.RemoveAt(l.Count-1);

La solution la plus simple et la plus efficace étant tout de même un simple RemoveRange() dans un tel cas.

Bonne journée

**Mose** · 11/08/2006, 15h50

Envoyé par smikar

Un ArrayList étant implémenté à l'aide d'un tableau, ...

Noooooon c'est même pas une liste chaînée ? Quels clowns chez MS.

Envoyé par smikar

La solution la plus simple et la plus efficace étant tout de même un simple RemoveRange() dans un tel cas.

Non non, t'as rien compris. Le but ici est de faire trimer la machine un grand coup, c'est pour faire un benchmark.
En fait je voulais aller taper des cases aléatoirement, mais ça aurait nécessité de faire 100 fois le tests pour avoir une moyenne des résultats, mais j'ai eu la flemme

**smikar** · 11/08/2006, 16h23

Envoyé par Mose

Noooooon c'est même pas une liste chaînée ? Quels clowns chez MS.

Euh

ArrayList : juxtaposition de deux mots, array et list (en français, tableau et liste). Un ArrayList est donc, par définition, l'implémentation d'une liste à l'aide d'un tableau. Je ne vois pas en quoi cela fait des développeurs de Microsoft une bande de clowns. Tu trouveras la classe LinkedList<> (.NET 2.0) qui est une liste doublement chaînée. Mais un LinkedList n'est pas meilleur qu'un ArrayList, chacun est utilisé dans des circonstances différentes, c'est tout.

Non non, t'as rien compris. Le but ici est de faire trimer la machine un grand coup, c'est pour faire un benchmark.
En fait je voulais aller taper des cases aléatoirement, mais ça aurait nécessité de faire 100 fois le tests pour avoir une moyenne des résultats, mais j'ai eu la flemme

Oui, mais ce test n'a pas tellement de sens, à mon avis. Il est normal de par le fonctionnement interne du ArrayList que la suppression d'un élément au début du tableau soit lente, et que dans un Hashtable bien réparti, cela soit très rapide. Il n'y a pas de quoi être surpris par ce résultat.

**Mose** · 11/08/2006, 15h46

Envoyé par cinemania

Et il ta fallut tout cela pour t'en rendre compte ?

Merci pour la leçon, je connais le principe de la Hashtable, et j'avais un vague espoir que l'ArrayList cache une structure arborescente derrière une représentation en liste (plus cher en mémoire, mais tout est en 0(log n)).

C'est surtout pour les listes génériques que je suis intéressé.
Maintenant, si tu as de la doc technique sur leur implémentation, ça m'intéresse beaucoup.

**smikar** · 11/08/2006, 16h25

Envoyé par Mose

Merci pour la leçon, je connais le principe de la Hashtable, et j'avais un vague espoir que l'ArrayList cache une structure arborescente derrière une représentation en liste (plus cher en mémoire, mais tout est en 0(log n)).

C'est surtout pour les listes génériques que je suis intéressé.
Maintenant, si tu as de la doc technique sur leur implémentation, ça m'intéresse beaucoup.

Le framework .NET ne fournit malheureusement pas d'implémentation de collections sous forme d'arbres. Tu en trouveras par contre certainement facilement sur le net (au hasard, codeproject).

**Mose** · 11/08/2006, 16h35

J'ai surtout fait les miennes

En revanche, j'ai des problèmes de perf à cause des types managés. Falloir que je code ça en Win32 et que j'encapsule en .Net. J'espère que l'interopérabilité ne va pas nuire aux perfs...

[Test] Proposition de Benchmark Hashtable/ArrayList/List ?

Framework .NET

Vue hybride

Discussions similaires

Partager

Partager