Discussion :

[losformen]

Bonjour,

J'ai une question simple, mais je n'arrive pas à trouver de réponse satisfaisante.

Je recherche une manière simple de stocker une collection d'objets, triée suivant une propriété de l'objet, de telle sorte que je puisse facilement (recherche en O(Ln(n))) extraire une sous-liste suivant la dite propriété.

Exemple : une classe Animal avec une propriété Nom
J'ai une liste de N Animal, je peux la trier suivant le Nom.
Maintenant je veux extraire les M Animal dont le Nom est égal à "Médor".
2eme possibilité : je veux extraire tous les animaux dont le nom est compris entre "Md*" et "Mf*".

A titre de comparaison, dans une BDD, ce genre de requête serait optimisée par l'ajout d'un index sur la colonne Nom de la table Animal.
Je ne trouve pas une manière de faire élégante en C#.
Dois-je implémenter moi même un algorithme de recherche (par dichotomie par exemple).

Je vous remercie par avance.

[François M.]

Bonjour

La réponse en C# tient en un seul mot : LINQ

Tu peux faire des "select" sur une collection typée, tout comme en SQL sur une table.

[tomlev]

Dois-je implémenter moi même un algorithme de recherche (par dichotomie par exemple).

Si la collection est de type List<T>, il y a une méthode BinarySearch pour faire une recherche dichotomique. Par contre ça ne renvoie que l'index d'un élément, et s'il y en a plusieurs qui correspondent, ce n'est pas forcément le premier qui est renvoyé.

Du coup il faudrait bricoler à partir du résultat de BinarySearch.

Quelque chose comme ça :

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
    int index = animals.BinarySearch(new Animal(0, "Medor"), new AnimalNameComparer());
    if (index >= 0)
    {
        var result = new List<Animal>();
        for (int i = index - 1; i >= 0; i--)
        {
            if (animals[i].Name == "Medor")
                result.Insert(0, animals[i]);
            else
                break;
        }
        for (int i = index; i < animals.Count; i++)
        {
            if (animals[i].Name == "Medor")
                result.Add(animals[i]);
            else
                break;
        }
        result.Dump();
    }

Avec AnimalNameComparer défini comme ceci :

Code :

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

1
2
3
4
5
6
7
class AnimalNameComparer : IComparer<Animal>
{
    public int Compare(Animal a, Animal b)
    {
        return a.Name.CompareTo(b.Name);
    }
}

Autre approche : chercher un nom qui n'existe pas, mais qui serait juste avant le nom recherché (par exemple en remplaçant par la précédente : "Medoq"). Si le nom recherché n'est pas trouvé, BinarySearch renvoie un index négatif qui, si on inverse les bits, renvoie la position où le nom devrait être inséré. Tu peux donc chercher à partir de cette valeur :

Code :

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

1
2
3
4
5
6
7
8
    int index = animals.BinarySearch(new Animal(0, "Medoq"), new AnimalNameComparer());
    if (index < 0)
        index = ~index;
 
    var result =
        animals.Skip(index)
               .SkipWhile(a => a.Name.CompareTo("Medor") < 0) // on skip les "Medoq", "Medoqa", etc...
               .TakeWhile(a => a.Name == "Medor");

Pour le comparer, c'est un peu galère de devoir en écrire un pour chaque propriété recherchée. Dans ma lib Linq.Extras, il y a une classe XComparer qui peut aider :

Code :

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

var comparer = XComparer<Animal>.By(a => a.Name);

Ou alors si tu ne veux pas tenir compte de la casse :

Code :

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

var comparer = XComparer<Animal>.By(a => a.Name, StringComparer.CurrentCultureIgnoreCase);

Si la collection n'est pas une List<T>, il faut implémenter toi-même la recherche dichotomique. L'algo est connu, ça devrait pas être trop difficile.

La réponse en C# tient en un seul mot : LINQ

Tu peux faire des "select" sur une collection typée, tout comme en SQL sur une table.

En l'occurrence ce n'est pas un Select qu'il faudrait faire, mais un Where. Et la recherche serait linéaire (O(n)) alors que losformen voudrait une technique plus efficace qui tire partie du fait que la liste est triée.