Calcul rapide du min, max, moyenne des numéros entrants

Question

Programme reçoit environ 50 000 numéros à chaque seconde.

À un moment donné, j'ai besoin de calculer le minimum, le maximum et la moyenne des valeurs (nombres) qui sont arrivés à la dernière seconde (concernant pour le moment).

Est-il un moyen de le faire sans l'aide du tableau ou de la liste (tampon) pour stocker l'arrivée de chiffres et de calculer les résultats?

Si j'ai besoin d'utiliser la mémoire tampon, ce qui serait le moyen efficace pour y parvenir?

(Notez que les numéros de tampon doit également être éliminées efficacement de temps en temps)

Answer 1

Voici un algorithme qui sera un peu le travail à économiser de l'efficacité dans certains cas:

1. Comme les événements de venir dans, le tampon complètement, et de calculer un exécutant sum, count, min, max (trivial).

2. Lorsqu'une demande d' average, minou max est faite, en boucle à partir de l'arrière de la zone tampon et de commencer à supprimer les valeurs vieux de plus d'une seconde. Soustraire sum et count comme vous allez.

   • Si les valeurs sont toutes au-dessus de min vous pouvez garder votre min. Si les valeurs sont inférieures max, vous pouvez garder votre max. Dans ce scénario, vous avez average, min, et max mis à jour de manière efficace.

   • Si les valeurs sont inférieures min ou au-dessus de max, vous aurez besoin d'une boucle sur le reste de la matrice et de calcul.

3. L'étape deux fois une seconde également, de sorte que le tampon ne soit pas trop plein. Ce code peut être effectuée sur chaque tampon d'insérer également, ou partout où cela fait sens.

La meilleure structure pour ce type de travail est une mémoire tampon circulaire, afin d'éviter les allocations de mémoire et GC obtenir de la manière. Il devrait être assez grand pour couvrir le pire scénario pour la taille des messages par seconde.

Les mises à jour

En fonction du scénario d'utilisation d'un autre chose à faire serait de exécuter l'algorithme ci-dessus, mais en 10 x 100ms morceaux plutôt que 1 x 1000ms pièce. C'est, garder la course min, max, sum et count sur ces 10 morceaux. Ensuite, lorsque vous atteignez une 'invalidation du scénario, en général seulement besoin de regarder à travers la dernière 100ms de données ou un passage rapide à travers le min et le max de les 9 autres morceaux.

---

@ja72 fourni une excellente idée d'enregistrer sur la recherche sur les valeurs min et max s'ils sont invalidés:

Au lieu de garder les valeurs min/max x_min, x_max garder au lieu de l'indice de l'endroit où ils sont situés dans le x[i] tableau avec i_min et i_max. Puis de les trouver, peut-être trivial, parfois, mais lors de la dernière valeur considérée comme détient les min et max, l'ensemble de la liste doit être analysé pour établir de nouvelles limites.

---

Sam Titulaire a eu une autre bonne idée dans les commentaires - maintenir un réseau parallèle qui est toujours triée, cela vous permet de lop nombre le haut ou le bas pour trouver de nouveaux minimums et maximums plus facile. Cependant, insérez la vitesse ici est compromis un peu (il doit rester dans l'ordre).

---

En fin de compte, le bon choix dépend de l'utilisation des caractéristiques du programme. Quelle sera la fréquence des valeurs de vs lire comment souvent ils sont insérées?

Answer 2

Utiliser le tampon circulaire avec chaque élément d'horodatage et de données, ayant nombre maximum d'éléments par seconde que la taille de la mémoire tampon circulaire.

Chaque élément est inséré dans le buffer de la tête, vérifiez la date d'expiration de l'autre côté de la mémoire tampon, de supprimer l'élément.

Si l'élément est supprimé de minimum ni de maximum, vous aurez à calculer de nouveaux min/max. Si ce n'est pas le cas, vous allez mettre à jour min/max selon les nouveaux arrivants.

Pour avg, maintenir le total, gardez le comte, et de se diviser.

Answer 3

ne pouvez-vous pas de garder une file d'attente avec vos numéros et leur heure d'arrivée, ainsi que le courant maximum et minimum des valeurs dans la file d'attente (aurez probablement besoin de compter le nombre de valeurs min/max), et la valeur totale de tous les nombres dans la file d'attente et le nombre d'éléments.

Puis, quand un certain nombre arrivée de l'ajouter à la file d'attente et d'ajuster le min/max/valeur et à compter. Ensuite, regardez à l'autre bout de la file d'attente et de supprimer tous les éléments qui ne sont pas moins de 1 sec de l'arrivée du dernier numéro, et encore ajuster le max/min/temps/valeur totale.

Ensuite, vous n'avez pas besoin de continuer à calculer quelque chose à un instant, il suffit de retourner le précalculées trucs (c'est à dire de lire la valeur courante de la fonction min/max ou total/nombre)

Comme @yaman a souligné vous ne pouvez pas retenir seulement le min et le max que quand quelqu'un est enlevé, vous ne connaissez pas la nouvelle. dans ce cas, je serais probablement juste de garder une copie de tous les nombres dans la liste, mais plutôt que prescrit par l'arrivée j'ai le temps, par ordre de valeur. Alors que vous venez d'ajouter et de supprimer chaque numéro de cette liste, de sorte que vous saurez toujours le max et les valeurs minimales. Cela vous évite d'avoir à analyser tous les éléments dans la mémoire tampon de trouver le nouveau max/min, au lieu de garder en 2 exemplaires, mais les mises à jour de cette liste devrait être bon comme il est déjà commandé.

Answer 4

@DanRedux est correct; vous aurez besoin de les calculer à chaque fois parce que votre entrée est en train de changer. Maintenant, vous pouvez calculer ces chiffres, sur demande ou à l'avant (c'est à dire, lorsque vous recevez un nouveau lot) en fonction de la façon dont souvent les résultats sont nécessaires.

Par exemple, si la moyenne de votre cas d'utilisation des sondages pour ces stats toutes les ~30 secondes, puis je serais probablement juste de les calculer sur la demande et de mettre en cache le résultat jusqu'à ce qu'un nouveau lot vient dans. Il s'agit vraiment de scénario d'utilisation si.

Quant à la façon de les stocker, vous n'avez pas vraiment le choix, pensez-vous? Vous avez besoin d'espace pour tous les 50.000 numéros en mémoire. Alors... vous avez besoin d'une partie de la mémoire assez grand pour les contenir. Pour éviter de devoir constamment l'allocation de 2 KO à chaque fois une nouvelle séquence vient dans vous êtes probablement mieux de déclarer un tableau assez grand pour contenir le plus grand ensemble de données possible et juste de le réutiliser. Encore une fois, cela revient à vos exigences, à savoir, savez-vous ce que votre plus grand ensemble de données sera? Ne attribution d'un nouveau bloc de mémoire jamais deuxième causer des problèmes dans votre application au fil du temps?

Answer 5

Si la moyenne de la dernière N valeurs x[0] .. x[N-1] est m_1 (x[0] est la dernière valeur, et x[N-1] de la dernière valeur considérée) alors la moyenne de m_2 des valeurs tout en poussant en arrière, d'un index et en ajoutant la valeur x est

 m_2 = m_1+(x-x[N-1])/N;
 for(i=N-1;i>0;i--) { x[i]=x[i-1]; }
 x[0] = x;

Au lieu de garder les valeurs min/max x_min, x_max garder au lieu de l'indice de l'endroit où ils sont situés dans l' x[i] tableau avec i_min et i_max. Puis de les trouver, peut-être trivial, parfois, mais lors de la dernière valeur considérée comme détient les min et max, l'ensemble de la liste doit être analysé pour établir de nouvelles limites.