Supposons qu'il y ait une alimentation en temps réel des cours boursiers, comment calculez-vous la moyenne d'un sous-ensemble (disons au cours de la dernière semaine)?Sous-ensemble moyen de séries temporelles en temps réel
C'était une question d'entrevue. Je peux trouver un algorithme pour le faire dans O (n^2), mais l'intervieweur voulait un algorithme qui était O (n).
Une approche utile consiste à calculer la somme cumulée de votre tableau. Cela signifie que chaque entrée dans le tableau de somme cumulative est la somme de tous les prix précédents. Ceci est utile car vous pouvez ensuite générer la somme sur n'importe quel sous-tableau de votre entrée en utilisant une seule soustraction.
Notez que lorsqu'une nouvelle entrée arrive, vous n'avez besoin que d'une addition pour calculer la nouvelle somme cumulée (parce que vous ajoutez simplement le nouvel élément à l'ancienne somme cumulative).
Une autre approche s'apparente au calcul de l'asymétrie en génomique.
Si vous souhaitez calculer la moyenne au cours de la dernière semaine, créez une variable qui contient la somme sur une fenêtre mobile. Lorsqu'une entrée est créée, ajoutez l'entrée à la variable sum ci-dessus et soustrayez l'entrée la plus ancienne de la fenêtre mobile. Puisque la taille de la fenêtre est constante, la moyenne de la semaine écoulée est juste la somme mobile par rapport au nombre d'entrées de la semaine dernière.
Intéressant concept. Vous dites de créer un autre tableau avec le même nombre d'entrées que les prix des actions, mais les valeurs contenant la somme cumulative? Ainsi, si je veux calculer la somme au cours de la dernière semaine, il suffit de prendre la dernière valeur du tableau de somme cumulative et de la soustraire de la valeur correspondant à il y a une semaine, et de la faire moyenne sur le nombre d'entrées . Je vous remercie. – user84405
C'est une bonne approche, mais nécessite un mécanisme de maintenance pour gérer le débordement éventuel (vous ne pouvez pas ajouter pour toujours). – Amit
@Amit Bon point: Si vous mettez les prix à l'échelle pour devenir des nombres entiers, vous pouvez utiliser l'arithmétique de bouclage standard et calculer la bonne réponse (si la somme correspond à la taille du type de données) –