Hashtable.ContainsKey(Expression régulière) ?

[Allan007]

Bonjour a tous,

voilà le titre est assez explicite, comment faire un .ContainsKey dans une hashtable avec une expression régulière ? Par exemple:

Code :

1
2
3
4
5
6
7
Public leHashTable As New Hashtable()
Dim reg As New Regex("aKey")
 
leHashTable.Add("maKey1", "maValue1")
leHashTable.Add("Key2", "Value2")
 
leHashTable.ContainsKey(reg) 'dois resortir maValue1

Dois-je faire un boucle avec IDictionaryEnumerator pour y arriver ? ça me parait assez lourd vue que ma hashtable peux contenir des centaines voir millier d'entrée.. ;\

En vous remerciant par avance de votre aide

[tomlev]

Il n'y a pas d'autre moyen que de parcourir toute la hashtable. Si tu regardes comment une hashtable est construite, tu comprendras vite pourquoi...

Envoyé par Allan007

ça me parait assez lourd vue que ma hashtable peux contenir des centaines voir millier d'entrée.. ;\

Quelques centaines ou milliers, c'est pas grand chose, ça ira très vite... Ca ne deviendra problématique que si tu effectues cette recherche très souvent.

[Er3van]

A priori je procéderai comme ça :

Code C# :

1
2
 
List<String> matches = leHashTable.Values.Cast<String>().ToList().FindAll(u => reg.Match(u).Success);

EDIT : Je n'avais pas fait attention... tu fais ta recherches sur la clé, mais tu veux la valeur...

[Allan007]

@tomlev,

Merci pour ta réponse, effectivement cette opération de recherche sera effectuer assez souvent...
Y'a t'il un autre système pour faire cette recherche rapidement ? Par exemple utilisé les tableaux Array ?


@Er3van,

Merci mais j'utilise VB.Net pas C#.. ! ;\

[tomlev]

Envoyé par Allan007

Merci pour ta réponse, effectivement cette opération de recherche sera effectuer assez souvent...

C'est quoi "assez souvent" ? Si c'est en réponse à une action de l'utilisateur (même si c'est une action fréquente), ce n'est pas ce que j'appelle souvent... "souvent", ce serait plusieurs fois (voire plusieurs centaines de fois) par seconde.

Envoyé par Allan007

Y'a t'il un autre système pour faire cette recherche rapidement ? Par exemple utilisé les tableaux Array ?

Ce sera peut-être un peu plus rapide avec un tableau, mais je suis même pas sûr... As-tu une raison particulière d'utiliser une hashtable ?

Envoyé par Allan007

Merci mais j'utilise VB.Net pas C#.. ! ;\

http://www.developerfusion.com/tools.../csharp-to-vb/

[Allan007]

@tomlev

Merci encore pour ta réponse, bien alors tu m'as convaincu de procéder a une boucle avec IDictionaryEnumerator !
Car cette opération sera exécuté par l'utilisateur, ça peux aller jusqu'à 5 fois par secondes je pense.

En faite, je développe un client IRC, et cette recherche sur hashtable se fera quand l'utilisateur commence a écrire quelques lettres et qu'il appuie sur la touche TAB, ce qui fera cette boucle pour aller chercher le pseudo de la personne pour l'écrire dans la textbox.

Pourquoi utiliser hashtable, car il me semble que c'est le moyen le plus rapide pour stocker et récupérer des données stocké.
Cette hashtable contient "lePseudo" en key et en value "lePseudo!ident@host.fr" a chaque fois que quelqu'un fais une action sur le réseaux irc, je stock c'est information s'il n'y sont pas déjà présente.

Voilà !

Merci encore


EDIT : J'viens de réfléchir .. (oui ça m'arrive parfois)
J'vais pas faire une boucle sur le hashtable mais sur la nicklist des personnes connecter au salon (!) Car sinon il va me sortir des personnes non connecter.. xD

[Er3van]

Pour info, je viens de faire un petit test, car ça me titillait...

J'alimente le Dictionnaire et le Hastable avec 100 000 entrées.

Code c# :

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
 
var hashTable = new Hashtable();
Dictionary<string, string> dico = new Dictionary<string, string>();
List<string> resultsHasTable = new List<string>();
System.Text.RegularExpressions.Regex searchTerm = new System.Text.RegularExpressions.Regex("11");
 
Stopwatch sw = Stopwatch.StartNew();
 
int oldR1 = 0;
try
{
      for (int i = 0; i < 100000; i++)
      {
            int r1 = oldR1 + new Random().Next(1, 10);
            int r2 = new Random().Next(0, r1);
            oldR1 = r1;
 
            hashTable.Add(r1.ToString(), r2.ToString());
            dico.Add(r1.ToString(), r2.ToString());
       }
}
catch (Exception ex)
{
       ResultsTextBox.Text += "Ex : " + ex.Message;
}
 
sw.Stop();
ResultsTextBox.Text += "\nRemplissage : " + sw.Elapsed ;

Ensuite, je récupère via un IDictionaryEnumerator dans le hashtable :

Code C# :

1
2
3
4
5
6
7
8
9
10
11
12
13
 
sw.Reset();
sw.Start();
IDictionaryEnumerator ide = hashTable.GetEnumerator();
while(ide.MoveNext()) {
	if (searchTerm.Match((String)ide.Key).Success)
	{
		resultsHasTable.Add((String)ide.Value);
	}
}
 
sw.Stop();
ResultsTextBox.Text += "\nRécupération des valeurs via clé avec Hashtable/IDictionaryEnumerator : " + sw.Elapsed;

Et après, je fais de même, avec Linq, dans mon dico :

Code C# :

1
2
3
4
5
6
 
sw.Reset();
sw.Start();
var resultDico = dico.Where(u => searchTerm.Match(u.Key).Success).Select(i => i.Value).ToList();
sw.Stop();
ResultsTextBox.Text += "\nRécupération des valeurs via clé avec Dico/Linq : " + sw.Elapsed;

Et j'obtiens le résultat suivant :

Remplissage : 00:00:01.1639071
Récupération des valeurs via clé avec Hashtable/IDictionaryEnumerator : 00:00:00.0243843
Récupération des valeurs via clé avec Dico/Linq : 00:00:00.0325695

Donc un écart d'environ 50%.
Seulement, si ne caste pas en List<String> mon résultat Linq (puisqu'on ne veut que lire de toute façon), j'obtiens cela :

Remplissage : 00:00:01.0785094
Récupération des valeurs via clé avec Hashtable/IDictionaryEnumerator : 00:00:00.0259971
Récupération des valeurs via clé avec Dico/Linq : 00:00:00.0006187

Donc un écart de 1 pour 40. (Il y a bien autant de valeurs dans les deux résultats)
Et si je passe à 1 million d'entrées, ça fait x10 pour le hashtable, mais seulement x1,3 pour le dictionnaire :

Remplissage : 00:00:12.0008506
Récupération des valeurs via clé avec Hashtable/IDictionaryEnumerator : 00:00:00.3174830
Récupération des valeurs via clé avec Dico/Linq : 00:00:00.0008470

Peut-être y a-t-il moyen d'améliorer le code pour la récupération des données dans le hashtable, ou alors j'ai raté un truc...

[Sehnsucht]

Bonjour,

Quelques remarques sur ce dernier code :

Il vaudrait mieux compiler la Regex (RegexOptions.Compiled en second param du constructeur) si elle doit servir souvent

Créer un seul générateur de nombres aléatoires (un seul new Random avant le chrono) améliorerait peut-être le temps de remplissage

La différence d'écart sans appel à ToList pour Linq provient du fait que les résultats ne sont pas évalués, c'est juste la création d'une "requête" qui enverra les données quand elles seront nécessaires (foreach, calculs (agrégats), etc.) cela revient au même que comparer la création d'un string contenant une requête SQL ("SELECT ...") avec l'exécution de celle-ci

Finalement, je me suis décidé à faire quelques tests (sauf que je finis avec du code un brin complexe ... influence F# sort de ce corps code )

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
public static void Measure<T>(Func<T> body, Action<T, TimeSpan> cont)
{
    var sw = Stopwatch.StartNew();
    T result = body();
    cont(result, sw.Elapsed);
}
 
public static void Measure(Action body, Action<TimeSpan> cont)
{
    var sw = Stopwatch.StartNew();
    body();
    cont(sw.Elapsed);
}

Je commence par définir deux méthodes qui me permettront de mesurer le temps d'exécution d'une méthode (resp. retournant un résultat ou void) et en même temps de passer une "continuation" aka se que je veux faire du "retour" (le temps mesuré avec le résultat resp. seul)

Code :

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
public static class SampleExtensions
{
    public static IEnumerable<string> ContainsPattern(this Hashtable table, string pattern = ".*")
    {
        var rgx = new Regex(pattern, RegexOptions.Compiled);
 
        IDictionaryEnumerator ide = table.GetEnumerator();
        while (ide.MoveNext())
        {
            if (rgx.Match(ide.Key.ToString()).Success)
            {
                yield return ide.Value.ToString();
            }
        }
    }
 
    public static IEnumerable<string> ContainsPattern(this Dictionary<string, string> dico, string pattern = ".*")
    {
        var rgx = new Regex(pattern, RegexOptions.Compiled);
 
        return dico.Where(kvp => rgx.Match(kvp.Key).Success).Select(kvp => kvp.Value);
    }
}

Je définis ensuite deux méthodes d'extension (donc dans une classe statique) me permettant de faire le boulot resp. sur une HashTable et sur un Dictionary (fixé à <string, string> pour simplifier ) avec le pattern à rechercher en paramètre (fixé à .* autrement dit tout)
J'use au passage du yield return ce qui me permettra de montrer que ce n'est pas spécifiquement Linq le "problème" mais plutôt l'évaluation tardive.

Viens enfin le code principal :

Code :

1
2
3
4
5
6
7
8
9
10
11
Dictionary<string, string> dico = null;
Hashtable table = null;
 
Measure(() =>
{
    dico = Enumerable.Range(1, 100000)
        .ToDictionary(n =>
            n.ToString(),
            n => n.ToString());
    table = new Hashtable(dico);
}, time => Console.WriteLine("{0} (Populate)\n", time));

Je commence par définir mon Dictionary et ma HashTable ; pour ce faire je prend juste la séquence des 100000 premiers nombres (vu que de toute façon je matcherai tout ensuite) que je mappe en clef et valeur en tant que string (et je passe simplement mon Dictionary au constructeur de la HashTable)
Le tout s'effectue au sens de ma méthode de mesure (par le biais d'une lambda) ainsi le temps sera utilisé par la continuation que je passe en second paramètre, qui se contente de l'afficher.

Et c'est là qu'on arrive au truc qui fait peur (que je pourrais sans doute factoriser)

Code :

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
Measure(() =>
    table.ContainsPattern(),
    (results, time) =>
        Measure(() =>
            results.Count(),
            lengthTime =>
                Console.WriteLine("HashTable (w/out ToList)\n{0} (Time)\n{1} (Length time)\n", time, lengthTime)));
 
Measure(() =>
    table.ContainsPattern().ToList(),
    (results, time) =>
        Measure(() =>
            results.Count(),
            lengthTime =>
                Console.WriteLine("HashTable (w/ ToList)\n{0} (Time)\n{1} (Length time)\n", time, lengthTime)));
 
Measure(() =>
    dico.ContainsPattern(),
    (results, time) =>
        Measure(() =>
            results.Count(),
            lengthTime =>
                Console.WriteLine("Dictionary (w/out ToList)\n{0} (Time)\n{1} (Length time)\n", time, lengthTime)));
 
Measure(() =>
    dico.ContainsPattern().ToList(),
    (results, time) =>
        Measure(() =>
            results.Count(),
            lengthTime =>
                Console.WriteLine("Dictionary (w/ ToList)\n{0} (Time)\n{1} (Length time)\n", time, lengthTime)));

Je repars dans une mesure dont le code appelle la méthode d'extension de la HashTable (resp. du Dictionary) et ce en version ToList ou pas (4 cas donc) ; j'en "récupère" donc les valeurs (dans results) qui correspondent (toutes à cause de mon pattern) ainsi que le temps que cela a pris (dans time).
En fait c'est la continuation qui les utilisent ; et effectue une autre mesure du nombre d'éléments ; à noter que la méthode d'extension Count() utilisée ici à une implémentation différente pour IEnumerable et List, pour le premier elle énumère en incrémentant un compteur ; pour la seconde elle récupère juste la propriété Count de la List. Cette mesure là ne "récupère" que le temps (j'aurais pu récupérer aussi le nombre d'éléments mais il était inutile pour moi ici). Ainsi la seconde continuation (grâce au jeu des "closure" a accès aux deux temps ; que j'affiche, ce qui permet de voir un peu mieux où se fait vraiment l'itération des résultats.

Ainsi chez moi, voici ce que j'obtiens:

00:00:00.0910834 (Populate)

HashTable (w/out ToList)
00:00:00.0005511 (Time)
00:00:00.0820158 (Length time)

HashTable (w/ ToList)
00:00:00.0450565 (Time)
00:00:00.0001234 (Length time)

Dictionary (w/out ToList)
00:00:00.0014698 (Time)
00:00:00.0343342 (Length time)

Dictionary (w/ ToList)
00:00:00.0382130 (Time)
00:00:00.0001014 (Length time)

Cordialement !

P.S. j'offre ceci si vous avez tout lu, tout compris, et que vous trouvez mon code joli

[Er3van]

Mouhahaha, je veux le cookie !

En fait je me suis mal exprimé... je ne voulais pas dire que Dico+Linq était plus rapide en soit, ma conclusion s'était bien que ça mettait 50% de plus dans le cas nominal, mais qu'en soit ce n'est pas si horrible. Pis le code pour l'alimentation c'était juste pour mettre des données dedans, les perf de ce bout de code ne m'intéressait guère, mais en effet, ça peut s'améliorer.

Ma dernière partie n'était pas très utile, ou alors j'aurais du préciser qu'avec un Array on divisait quand même par 5 le temps d’exécution et que c'était vraiment la liste le problème... bref.

Mais du coup ton code est très intéressant.
Si je comprends tout ce que tu as fais, ça confirme quand même que la hastable n'est pas performante dans ce cas d'utilisation (si on fait la somme des deux temps on arrive toujours au dessus).

J'ai un peu de mal à comprendre le "cont()" dans Measure ceci étant... :/

[Sehnsucht]

C'est ce qu'on appelle une continuation
perso j'ai vu ça depuis que je regarde de la programmation fonctionnelle, et je l'adapte parfois ailleurs (C# a de plus en plus de fonctionnalités fonctionnelles )

J'aurais très bien pu faire ma méthode Measure comme ceci :

Code C# :

1
2
3
4
5
6
7
public static T Measure<T>(Func<T> body, out TimeSpan time)
{
    var sw = Stopwatch.StartNew();
    T result = body();
    time = sw.Elapsed;
    return result;
}

Ou renvoyer un Tuple<T, TimeSpan> mais c'est lors de l'utilisation que ça m'aurait un peu plus gêner (personnellement)

Code C# :

1
2
3
4
5
6
7
8
9
10
TimeSpan t;
var res = Measure(() =>
    table.ContainsPattern(),
    out t);
Console.Write("HashTable (w/out ToList)\n{0} (Time)\n", t);
 
Measure(() =>
    res.Count(),
    out t);
Console.WriteLine("{0} (Length time)\n", t);

Alors que là je peux chainer le tout (ce qui rend au passage C# un peu verbeux je l'admets)

Ainsi pour faire un exemple simple et court (afin d'éviter de trop dévier le sujet) et donc présentant très peu d'intérêt tel quel.
Si on a ce code "classique"

Code C# :

1
2
3
4
5
6
7
8
9
static int Add(int x, int y)
{
    return x + y;
}
 
static void Main(string[] args)
{
    Console.WriteLine(Add(32, 10));
}

On peut le remplacer (ou lui adjoindre, car grâce aux surcharges il n'y a pas de conflit) par :

Code C# :

1
2
3
4
5
6
7
8
9
static void Add(int x, int y, Action<int> cont)
{
    cont(x + y);
}
 
static void Main(string[] args)
{
    Add(32, 10, Console.WriteLine); // ou mais plus long Add(32, 10, z => Console.WriteLine(z));
}

L'idée derrière les continuations (comme expliqué dans le lien) c'est qu'une méthode ne renvoie plus de résultat mais prend un argument supplémentaire qui représente "la suite du programme" (c'est d'ailleurs comme ça que fonctionnent en gros les exceptions et également la voie empruntée par Task<T>)

Après j'aurais très bien pu m'en passer, mais 1) j'aime bien 2) je trouve ça plus clair (mais c'est très subjectif) 3) vu le type de progression du langage (introduction graduelle de concept "fonctionnels" (même si les continuations c'est pas spécifiquement du paradigme fonctionnel)) ça peut pas faire de mal de jongler avec.

Cordialement !