Le moyen le plus rapide de trouver un élément dans une liste ?

Question

J'ai une liste non triée de chaînes de caractères. Je peux placer ces éléments dans un tableau, une liste, une liste triée, etc.

Je dois trouver le moyen le plus rapide de rechercher une chaîne dans cette liste. Est-il préférable de placer la liste dans un tableau, de la trier, puis d'effectuer une recherche binaire ? Ou bien le framework fournit-il un moyen de le faire ?

Gracias

P.S. Utilisation de VS2008 contre .NET 2.0

Answer 1

Si votre objectif est simplement de faire en sorte qu'il soit très rapide de trouver les chaînes de caractères dans une collection, mettez-les dans un fichier de type HashSet .

HashSet.Contains est une méthode O(1), et les chaînes ont un bon algorithme de hachage par défaut, il sera donc difficile de faire une routine plus rapide que celle-ci.

---

Editar:

Puisque vous utilisez .NET 2, je ferais simplement Dictionary<string,string> et utiliser la même chaîne pour la clé et la valeur. Dictinoary<TKey,TValue>.Contains est également O(1), et sera beaucoup plus rapide que toute recherche basée sur une liste que vous tenterez.

Answer 2

Si vous ne devez trouver qu'un seul objet, une seule fois, commencez par le début et regardez chaque objet jusqu'à ce que vous le trouviez. Si vous devez répéter cette opération de recherche plusieurs fois sur la même liste, pour trouver différents objets, alors triez-la, gardez la liste triée et faites une recherche binaire...

Answer 3

Je ne sais pas si cela vous sera utile, mais c'est une façon assez simple de procéder, mais je ne suis pas sûr de la "vitesse" exacte.

List<string> collection = new List<string>();

collection.Sort();

foreach(string value in collection)
{
   if(value == "stringToLookFor")
   {
       return value;
   }
{