Aidez-moi à optimiser cet extrait de calcul moyen

Question

Est-il possible d'accélérer cet extrait?

firstSample et lastSample est la partie du tableau que je suis intéressé par cette itération. C'est quand cet intervalle atteint> 3000 que je reçois un ralentissement notable. Le tableau _average peut contenir 6-60 millions de valeurs int.

minY et maxY est le résultat que je l'utilise après ce calcul est terminée.

int minY = Int32.MaxValue; 
int maxY = Int32.MinValue; 
int Y = 0; 
int sample = firstSample + 1; 

while (sample <= lastSample) 
{ 
     Y = _average[sample]; 
     minY = Math.Min(Y, minY); 
     maxY = Math.Max(Y, maxY); 
     sample++; 
} 

Answer 1

L'expression _average [sample] est un goulot d'étranglement énorme, car elle contient une vérification implicite des limites chaque itération. Utilisez un pointeur vers le tableau "_average" (et le mot-clé dangereux). Évitez ensuite d'appeler des fonctions, alors débarrassez-vous des appels Math.Min/Max et faites-le vous-même.

Sans compilateur mes mains en ce moment, je pense que cela est la façon dont il devrait ressembler à:

unsafe 
{ 
    fixed (int* paverage = _average) 
    { 
     int* p = paverage + firstSample + 1; 
     for (int sample = firstSample+1 ; sample <= lastSample ; sample++) 
     { 
      if (*p < minY) 
       minY = *p; 
      if (*p > maxY) 
       maxY = *p; 
      p++; 
     } 
    } 
} 

Puis finalement, puisque « échantillon » n'est pas réellement utilisé dans la boucle, vous pouvez le changer à un variable de boucle qui compte jusqu'à zéro, de sorte que la vérification de la fin de la boucle se fasse par rapport à une constante (zéro) au lieu d'une variable.

Answer 2

Vous pouvez utiliser pour est plus rapide que tout ou parallèle d'utilisation si vous avez 3.5+ cadre

Answer 3

Je vais tenir mon cou et dire Non, je ne pense pas qu'il y ait aucune façon pour que cela soit beaucoup plus rapide (à moins d'inclure les appels à Min et Max, mais j'espère que l'optimiseur s'en chargera). Mais cela dit, si vous faites cela plusieurs fois sur les mêmes données, le tri des données (ou des morceaux de données que vous traitez à chaque fois) pourrait rendre le processus plus rapide.

Il est plus lent de trier que de trouver le minimum, mais il est plus rapide de trier une fois que de trouver le minimum mille fois.

(Pardonnez-moi si je vous enseigne à faire des grimaces ici. 8-)

Answer 4

D'une part, je le réécrire comme une simple boucle for et évitez d'utiliser une variable locale tubé Pascal, y compris un avec plus de portée que nécessaire:

int minY = int.MaxValue; 
int maxY = int.MinValue; 

for (int sample = firstSample + 1; sample <= lastSample; sample++) 
{ 
    int y = _average[sample]; 
    minY = Math.Min(y, minY); 
    maxY = Math.Max(y, maxY); 
} 

C'est juste pour le rendre plus familier et conventionnel. Le JIT connaît le bouclage sur les tableaux dans certaines situations, mais je ne sais pas si cela aidera dans ce cas - pourrait juste vérifier firstSample >= -1 && lastSample < _average.length et ensuite éliminer les contrôles de limites, mais je ne sais pas si c'est le cas. Maintenant, les échantillons qui sont déjà dans la gamme min courant/max ne nécessitent pas d'effets secondaires, alors débarrassons des missions dans ce cas:

for (int sample = firstSample + 1; sample <= lastSample; sample++) 
{ 
    int y = _average[sample]; 
    if (y < minY) 
    { 
     minY = y; 
    } 
    if (y > maxY) 
    { 
     maxY = y; 
    } 
} 

Je ne sais pas si cela ou non aider - Et je pense que ça ne marchera pas, mais ça vaut le coup d'essayer ...

(Comme une autre réponse dit, c'est une opération très facile à paralléliser - il devrait améliorer la vitesse presque linéairement avec le nombre de CPU, à savoir 2 processeurs ~ = deux fois plus vite etc, mis à part les échecs de cache, etc.)

Answer 5

Vous pouvez essayer la boucle for comme d'autres l'ont suggéré.

Il aura besoin de profilage, mais vous pouvez aussi essayer d'éliminer les invocations de méthode et de branchement:

Y = _average[sample]; 
    minY = minY + ((Y-minY) & (Y-minY)>>31); 
    maxY = maxX - ((X-maxX) & (X-maxX)>>31); 
    sample++; 

Effectuez ces modifications que si le gain de performance est vraiment important pour vous, puisque la maintenabilité du code se dégrade avec constructions similaires.

Answer 6

Un code non sécurisé vous permettrait d'utiliser des pointeurs pour indexer le tableau, car le compilateur JIT ne pourra pas supprimer la vérification des limites dans ce cas particulier. Regardez here sur la façon de le faire.

Vous pouvez également essayer de définir vous-même les appels Min/Max, mais il y a de fortes chances que le JIT le fasse déjà pour vous.

Enfin, il est assez facile de paralléliser ceci avec les extensions parallèles de .NET 4 (vous pouvez utiliser le CTP pour .NET 3.5). Assurez-vous de ne pas écrire dans les valeurs min/max de plusieurs threads en même temps. Ne vous verrouillez pas dessus non plus, j'aurais une valeur min/max par thread et ferais une comparaison finale entre les valeurs min/max de chaque thread/tâche quand tous les threads seront terminés.

Answer 7

Utilisez une boucle for comme d'autres l'ont dit, mais réglez-la pour que la comparaison soit à zéro. C'est une comparaison plus rapide dans la plupart des implémentations.

Answer 8

Vous avez écrit ce qui suit dans un commentaire:

Je ne suis pas le tri. Seulement trouver le maximum et le minimum d'un intervalle. Et l'intervalle se déplace tous les 20ms

Il semble que vous voulez vraiment un minimum de déplacement et déplacement maximal. Je crois que cela peut être fait plus efficacement que de chercher à nouveau l'intervalle entier à chaque fois, en supposant que l'intervalle ne se déplace que dans une direction, et qu'il y a un chevauchement significatif entre les intervalles suivants.

Une façon serait de garder une file d'attente spéciale, où chaque nouvelle copie des éléments de sa valeur à chaque élément dans la file d'attente qui est plus grand (pour le minimum mobile), par exemple:

 
(5 8 4 7 7 0 7 0 4 4 3 4 0 9 7 9 5 4 2 0) ; this is the array 
(4 4 4 4) ; the interval is 4 elements long, and initialized to the minimum 
      ; of the first 4 elements 
    (4 4 4 7) ; next step, note that the current minimum is always the first element 
    (4 7 7 0) ; now something happens, as 0 is smaller than the value before 
    (4 7 0 0) ; there are still smaller values ... 
    (4 0 0 0) ; and still ... 
    (0 0 0 0) ; done for this iteration 
     (0 0 0 7) 
     (0 0 0 0) ; the 0 again overwrites the fatties before 
      (0 0 0 4) 
      (0 0 4 4) 
       (0 3 3 3) ; the 3 is smaller than the 4s before, 
         ; note that overwriting can be cut short as soon as a 
         ; value not bigger than the new is found 
       (3 3 3 4) 
        (0 0 0 0) ; and so on... 

Si vous déplacez par Plus d'un élément à chaque fois, vous pouvez d'abord calculer le minimum de toutes les nouvelles valeurs et l'utiliser pour la réécriture.

Le pire des cas pour cet algorithme est lorsque le tableau est trié par ordre décroissant, alors il est O (nm), où m est la longueur de l'intervalle et n la longueur du tableau. Le meilleur des cas est quand il est trié par ordre décroissant, alors c'est O (n). Pour le cas moyen, je conjecture O (n log (m)).

Answer 9

Vous pourriez vous débarrasser des comparaisons en double dans les situations où vous trouvez un nouveau min. Si vous définissez votre min/max à la première valeur, alors si vous trouvez un nouveau min, il n'y a aucune raison de vérifier s'il s'agit également d'un nouveau max. C'est essentiellement le code de @ Skeet avec l'initialisation et une autre instruction 'else'.

int firstIndex = firstSample + 1; 
if (firstIndex <= lastSample) 
{ 
    minY = _average[firstIndex]; 
    maxY = minY; 

    for (int sample = firstIndex + 1; sample <= lastSample; sample++) 
    { 
     int y = _average[sample]; 
     if (y < minY) 
     { 
      minY = y; 
     } 
     else if (y > maxY) 
     { 
      maxY = y; 
     } 
    } 
}