C# Valeur du paramètre de performance pour chaque élément de la liste

Question

J'essaie de trouver le moyen le plus rapide de définir une propriété spécifique de chaque élément d'une liste générique. Fondamentalement, l'exigence est d'itérer sur une liste d'éléments et de réinitialiser la propriété IsHit sur FALSE. Seuls les éléments d'une deuxième liste "hit" doivent être mis à TRUE par la suite.

Ma première tentative ressemblait à ceci:

listItems.ForEach(delegate(Item i) { i.IsHit = false; }); 

foreach (int hitIndex in hits) 
{ 
    listItems[hitIndex - 1].IsHit = true; 
} 

Note: succès est basé sur 1, la liste des articles est base 0.

Alors j'ai essayé d'améliorer la vitesse et est venu avec ceci:

for (int i = 0; i < listItems.Count; i++) 
{ 
    bool hit = false; 
    for (int j = 0; j < hits.Count; j++) 
    { 
     if (i == hits[j] - 1) 
     { 
      hit = true; 
      hits.RemoveAt(j); 
      break; 
     } 
    } 

    if (hit) 
    { 
     this.listItems[i].IsHit = true; 
    } 
    else 
    { 
     this.listItems[i].IsHit = false; 
    } 
} 

Je sais que c'est un micro optimisation, mais il est vraiment temps de code sensible, donc il serait logique d'améliorer ce code au-delà readibility ... et juste pour le plaisir bien sûr ;-)

Malheureusement, je ne vois vraiment pas comment améliorer le code. Mais j'ai probablement manqué quelque chose.

Merci

PS: Code en C#/.NET 2.0 serait préférable. J'ai fini par passer à la solution Eamon Nerbonne. Mais j'ai remarqué quelque chose de bizarre dans mes benchmarks.

Le délégué:

listItems.ForEach(delegate(Item i) { i.IsHit = false; }); 

est plus rapide que:

foreach (Item i in listItems) 
{ 
    i.IsHit = false; 
} 

Comment est-ce possible?

J'ai essayé de regarder IL mais c'est juste au-dessus de ma tête ... Je vois seulement que les délégués obtiennent moins de lignes, peu importe ce que cela signifie.

Answer 1

Une imbriquée pour boucle est surpuissant , et en particulier, l'appel "remove" lui-même représente encore une autre for-loop. Dans l'ensemble, votre deuxième version optimisée a une complexité temporelle pire que la première solution, en particulier lorsqu'il y a beaucoup de résultats.

La solution la plus rapide est susceptible d'être la suivante:

foreach(var item in listItems) 
    item.IsHit = false; 
foreach (int hitIndex in hits) 
    listItems[hitIndex - 1].IsHit = true; 

On évite ainsi le imbriquée inefficace pour-boucles, et il évite la surcharge du délégué de la méthode fondée .ForEach (qui est une méthode bien, mais pas dans le code critique de performance). Cela implique de mettre un peu plus souvent IsHit, mais la plupart des setters de la propriété sont triviaux et donc ce n'est probablement pas un goulot d'étranglement. Un micro-benchmark rapide sert de test de santé mentale dans tous les cas.

Seulement si IsHit est vraiment lent, ce qui suit sera plus rapide:

bool[] isHit = new bool[listItems.Count]; //default:false. 
//BitArray isHit = new BitArray(listItems.Count); 
//BitArray is potentially faster for very large lists. 
foreach (int hitIndex in hits) 
    isHit [hitIndex - 1] = true; 
for(int i=0; i < listItems.Count; i++) 
    listItems[i].IsHit = isHit[i]; 

Enfin, envisagez d'utiliser un tableau plutôt qu'un List<>. Les tableaux sont généralement plus rapides si vous pouvez éviter d'avoir besoin des méthodes d'insertion/suppression du type List<>. Le mot-clé var est C# 3.5 mais peut être utilisé dans .NET 2.0 (les nouvelles fonctionnalités de langage ne nécessitent pas de nouvelles versions de bibliothèques, en général - c'est juste qu'elles sont les plus utiles avec ces nouvelles bibliothèques). Bien sûr, vous connaissez le type avec lequel List<> est spécialisé, et vous pouvez le spécifier explicitement.

Answer 2

Pouvez-vous mettre les éléments de votre deuxième liste dans un dictionnaire? Si oui, vous pouvez le faire:

for(int i = 0; i < firstList.Count; i++) 
{ 
    firstList[i].IsHit = false; 

    if(secondList.Contains (firstList[i].Id)) 
    { 
     secondList.Remove (firstList[i].Id); 
     firstList[i].IsHit = true; 
    } 
} 

Où secondList est un dictionnaire biensur.

En mettant les éléments de votre histlist dans un dictionnaire, vous pouvez vérifier avec une opération O (1) si un élément est contenu dans cette liste. Dans le code ci-dessus, j'utilise une sorte d'identifiant unique d'un élément comme clé dans le dictionnaire.

Answer 3

Vous pourriez peut-être trier les hits collection et d'effectuer une recherche binaire, alors vous seriez O (n log n) au lieu de O (n)