c# - IndexDe trop lent sur la liste. Une solution plus rapide?

11

Si ce n'est pas triée, mais l'ordre doit être préservéalors vous pourriez avoir un Dictionary<YourClass, int> qui contiendra l'index de chaque élément.

Si vous voulez une liste triée, puis vérifier les messages précédents - vous pouvez utiliser SortedList<Tkey, TValue>.Net 3.5, ou de les trier et de les utiliser BinarySearch en plus .Net versions.

[Edit] Vous pouvez trouver des exemples similaires sur le web, par exemple: OrderedList. Cela on utilise en interne une liste de tableaux et d'une table de hachage, mais vous pouvez facilement vous rendre générique.

[Edit2] Ooops.. l'exemple que je vous ai donné n'est pas de mettre en œuvre IndexOf la façon dont je l'ai décrit au début... Mais vous obtenez le point - une liste devrait être commandés, l'autre celui utilisé pour la recherche rapide.
6

De tri à l'aide de List<T>.Trierpuis utilisez le List<T>.BinarySearch méthode: "Recherche à l'ensemble triés List(T) pour un élément [...] Cette méthode est un O(log n), où n est le nombre d'éléments dans la gamme."
4

Voir le bas de cet article ici.

Il semble que la rédaction de votre propre méthode pour récupérer l'indice est beaucoup plus rapide que d'utiliser la méthode IndexOf, en raison du fait que l'appel d'une méthode virtuelle selon le type.

Quelque chose comme cela peut donc améliorer vos performances. J'ai écrit une petite unité de test pour vérifier que cela améliore les performances de la recherche, et il n'a, par environ 15x dans une liste avec les 10 000 éléments.
```
static int GetIndex(IList<Item> list, Item value)
{
    for (int index = 0; index < list.Count; index++)
    {
        if (list[index] == value)
        {
             return index;
        } 
    }
    return -1;
}
```
3

Peut-être vous êtes à la recherche pour SortedList<TKey, TValue>?
2

Je vous suggérons d'utiliser le SortedList<TKey, TValue> ou SortedDictionary<TKey, TValue> classe si vous avez besoin des éléments triés. Les différences sont les suivantes.
- SortedList<TKey, TValue> utilise moins de mémoire que SortedDictionary<TKey, TValue>.
- SortedDictionary<TKey, TValue> a plus rapide de l'insertion et de la suppression des opérations de
  des données non triées: O(log n) au lieu de O(n) pour SortedList<TKey, TValue>.
- Si la liste est remplie tout à la fois à partir des données triées,SortedList<TKey, TValue> est
  plus rapide que SortedDictionary<TKey, TValue>.
Si vous voulez juste pour préserver la commande, vous pouvez simplement utiliser un Dictionnaire<TKey, TValue> et stocker l'élément clé et l'index de la valeur. L'inconvénient est que la remise en ordre des éléments, des insertions ou de suppression sont très coûteux à faire.
1

Bien il n'y a aucune raison que vous ne devrait jamais avoir à commander un hachage de la liste...c'est le genre de point. Toutefois, une table de hachage liste devrait faire le tour assez facilement.
1

Si vous êtes à l'aide de la Liste de classe puis vous pouvez utiliser la méthode de Tri pour trier après est initialement rempli d'utiliser ensuite la Méthode BinarySearch pour trouver le bon élément.
1

Je ne suis pas sûr au sujet des particularités en C#, mais vous pourriez être en mesure de faire le tri (QuickSort?) et puis utiliser une recherche binaire (BinarySearch performance est O(log2(N)), par rapport à Séquentielle, comme indexOf, qui est O(n)). (IMPORTANT: Pour une Recherche Binaire, votre structure doit être triée)

Lorsque vous insérez des éléments de la structure de données, vous pouvez essayer une version modifiée de recherche binaire pour trouver le point d'insertion, ou si vous êtes l'ajout d'un grand groupe, vous pouvez ajouter et ensuite de les trier.

Le seul problème est que l'insertion sera plus lent.
1

Si l'ordre des objets dans la liste a être préservée, alors la seule façon que je peux penser à où vous allez obtenir le plus rapidement possible l'accès est-à-dire l'objet que sa position d'index est quand il ajouté, etc à la liste. De cette façon, vous pouvez interroger l'objet pour obtenir son index dans la liste. Le revers de la médaille, et c'est un gros point négatif à mon avis, est que les objets insérés maintenant avoir une dépendance sur la liste.

Vous devez vous connecter pour publier un commentaire.