Envoyé par
losformen
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 :
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 :
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 :
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 :
var comparer = XComparer<Animal>.By(a => a.Name);
Ou alors si tu ne veux pas tenir compte de la casse :
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.
Envoyé par
François M.
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.
Partager