Je crée un algorithme itératif (méthode de Monte Carlo). L'algorithme renvoie une valeur sur chaque itération, créant ainsi un flux de valeurs.
J'ai besoin d'analyser ces valeurs et d'arrêter l'algorithme lorsque vous dites J'ai décidé de mettre en œuvre le calcul du calcul La première idée de cerveau de hare était d'utiliser une liste Puis j'ai décidé qu'il n'y a aucune utilité à garder plus que alors je me suis souvenu qu'il y a le Avoir toutes ces pensées à l'esprit, j'ai décidé de demander ici:
Comment puis-je résoudre cette tâche le plus efficacement? 1000 les valeurs renvoyées contiennent des epsilon . .
max et min des valeurs de la dernière 1000 , puis calculez l'erreur < / Code> Utilisation de cette formule (max-min) / min et comparez-la sur epsilon : Erreur <= epsilon . Et si cette condition est atteinte, arrêtez les itérations et renvoyez le résultat.
list et appendez de nouvelles valeurs, calculant le max et < code> min valeurs pour le dernier 1000 de celui-ci après chaque annexe.
1000 dernières valeurs. Je me suis donc souvenu de DEQUE . Ce fut une très bonne idée depuis la complexité sur l'ajout et la suppression des deux extrémités de deque est o (1) . Mais cela n'a pas résolu le problème de la nécessité de passer à travers toutes les 1 000 dernières valeurs de chaque itération pour calculer min et max .
tasse Module . Il conserve les données de manière à renvoyer efficacement le plus petit à chaque instant. Mais j'ai besoin à la fois des plus petits et des plus grands. En outre, j'ai besoin de préserver l'ordre des éléments afin que je puisse garder 1000 les derniers éléments retournés de l'algorithme, et je ne vois pas comment je peux y parvenir avec tas .
6 Réponses :
Si vous êtes libre / prêt à modifier votre définition de Vous pouvez calculer la variance progressivement .
True, en utilisant cette méthode, vous ne supprimez aucune valeur de votre flux - la variance dépendra de toutes les valeurs. Mais alors quoi? Avec suffisamment de valeurs, les premiers ne compteront pas beaucoup de la variance et la variance de la moyenne, Donc, vous pouvez choisir de mettre un terme lorsque la variance erreur , vous pouvez envisager d'utiliser la variance au lieu de (max-min) / min .
variance / n sera faible lorsque suffisamment de valeurs se grappes autour d'une valeur fixe.
Il serait également facile de supprimer les valeurs qui tombent de la chute des 1 000 derniers de la variance de fonctionnement de la même manière que vous inclurez les nouvelles, juste avec les signes opposés. Bien sûr, cela nécessiterait toujours de conserver une deque des 1 000 dernières valeurs.
J'aime cette réponse! Se débarrasser du calcul du min et max Nous n'avons pas besoin de modifier les valeurs du dernier 1000 . Nous pouvons même calculer la variance des valeurs du dernier 1000 (grâce à @svenmarnach pour l'idée). Je pense que je vais mettre en œuvre cet algorithme. Mais je pense que je vais me débarrasser des valeurs 1000 et calculera la variance toutes les valeurs (car 1000 était du haut de l'avaient, cela pourrait être 100 ou 10000 . Je ne sais pas quel numéro dois-je choisir).
@ovgolovin: Soyez prudent avec l'approche de garder toutes les valeurs. Les nouvelles valeurs ultérieures apparaissent, moins ils auront du poids sur le résultat final. Cela conduirait à un critère de convergence beaucoup plus strict si la convergence apparaît plus tard.
@Svenmarnach mais comment puis-je choisir le bon nombre de valeurs pour faire une évaluation (j'ai choisi 1000, mais ce n'était qu'un choix aléatoire sans un certain calcul derrière lui). AIX a donné une bonne idée d'utiliser la variance de déménagement exponentiellement pondérée. J'ai besoin de temps à lire et à le contempler. Je pense que c'est une idée très prometteuse.
@ovgolovin: la réponse d'Aix est la voie à suivre. J'étais sur le point de poster une réponse similaire mais je suis perturbé.
J'ai bien peur que je ne sois pas en mesure de fournir une belle réponse python maintenant, mais je vais vous donner le contour de la structure de données dont vous aurez besoin d'utiliser:
Gardez vos 1000 articles dans une file d'attente FIFO. Gardez les pointeurs sur les plus gros et les plus petits articles de la file d'attente. Si l'une d'elles quitte la file d'attente, recherchez la file d'attente du nouveau / plus petit (coût amorti dépendant de vos données). Si une nouvelle valeur la plus grande / la plus petite entre la file d'attente, il suffit de mettre à jour le pointeur (O (1)). En supposant que vos données soient convergentes, cela devrait bien fonctionner.
"Aiguille"? Qu'est-ce que c'est? Peut-être utiliser l'index dans la drique, mais vous devez alors vous rappeler de décrémenter l'index à chaque fois que vous supprimez un élément de l'avant. Ensuite, lorsque l'un des index passe à -1, cela signifie qu'il est temps de recalcuter. De plus, vous devez avoir une logique de cas spéciale tout en construisant les 1000 valeurs initiales.
@Paulmcguire Désolé, j'utilise la langue de la structure de données générique plutôt que la langue de Python, je suis sûr qu'il y a une bonne façon de le faire fonctionner ( importer des pointeurs ?)
Hm. Merci! En supposant que les données convergentes, la valeur MAX Sortez des valeurs de la dernière 1000 sur chaque itération, il y aura donc des numérisons sur chaque itération.
@ovgolovin donc, une fois toutes les 1000 itérations, vous engagez une opération O (n), où n = 1000. Amortissement => O (1) Coût amorti!
Si les données sont convergentes, sur chaque itération max ou min (dépend de la variable augmente ou diminue) sera en train de sortir du dernier 1000 valeurs. Nous aurons donc besoin de la modification des valeurs 1000 pour mettre à jour max ou min . Donc o (n) sur chaque itération.
@ovgolovin, le mot est monotone , pas convergent.
@avakar Si la fonction n'est pas monotone, mais converge toujours à une certaine valeur (oscillant à proximité d'une certaine valeur avec une amplitude décroissante avec des itérations), la valeur suivante à la liste sera max ou min (selon la fonction si la fonction est en train de diminuer ou d'augmenter). Mais les deux max et min nécessitent besoin d'une numérisation lorsqu'ils sont caca dans la liste.
Créer une sous-classe d'une dentque contenant des propriétés Minvalue et MaxValue. Lors de l'ajout ou de l'élimination des entrées, comparez-les au courant MIN et MaxValues - Ensuite, il vous suffit de modifier la dent pour min / max si la valeur que vous retirez est la mine et max. Et lors de l'addition, comparez simplement la nouvelle valeur avec le courant MIN et Max et mettez à jour en conséquence. Cela optimisera la numérisation de votre deque pour les valeurs min / max.
Merci. J'y ai pensé. Cette technique diminuera le nombre moyen de numéros de numérisation nécessaires des 1 000 dernières valeurs. Je pensais peut-être que trois personnes peuvent conserver les données pour revenir efficacement min et max et pour garder l'ordre des éléments permettant de supprimer efficacement la suppression et de l'ajout à la fois dans deque .
Si les données sont proches de Monotonic, le maximum / minimum aura tendance à être au début / à la fin de votre fenêtre de 1000 éléments. Donc, vous devrez modifier presque chaque fois de toute façon.
Comment sur NUMPY?
JUSTE POUR COMPARER LA VITESSE: P>
i = 0
b = np.empty([1000]) + np.nan
your loop:
b[i % 1000] = value
i += 1
Il y a aussi np.ptp , qui englobe les différences de pointe de pointe.
Pouvez-vous fournir une comparaison en termes de complexité (par exemple O (n), O (LG N) etc ...)?
@unutbu - sur un échantillon de 1000 éléments, PTP a à peu près la même vitesse que min et max combiné.
Fredley: la complexité est la même que celle de la deque, O (n) dans chaque itération où n = 1000. C'est "juste" quatre fois plus vite.
@Fredley - L'ajout d'une nouvelle valeur est O (1) et est plus rapide qu'avec la liste / deque, car elle écrase une vieille valeur en même temps. La recherche de min / max est O (n) et est plus rapide qu'avec une liste Python.
+1 J'étais sur le point d'écrire la même solution comme vous mais sans problème.
Un raffinement de l'excellente idée de @ Unutbu, vous pouvez envisager d'utiliser la variance de déplacement exponentiellement pondérée . Il peut être calculé dans Le papier suivant dispose des formules pertinentes: Lien . Voir les équations (140) - (143).
Enfin, vous voudrez peut-être travailler avec l'écart type au lieu de la variance. C'est simplement la racine carrée de la variance et présente l'avantage d'avoir les mêmes unités que les données d'origine. Cela devrait faciliter la formulation d'un critère d'arrêt significatif. O (1) temps par observation, nécessite O (1) espace et a l'avantage de réduire automatiquement le poids de l'observation lorsque l'observation devient plus ancienne.
C'est une bonne idée. J'ai besoin de temps pour le lire et envisager. Je peux poser plus tard quelques questions. Merci!
Vous pouvez utiliser deux fibonacci tas . L'ajout de valeurs est dans O (1), la suppression est dans O (log (n)). Dans votre question, vous suggérez déjà le module HEPQ. Je ne suis pas sûr de ce que cela fournit un tas, mais une normale fonctionnera également très bien.
Le problème que vous ne pouvez extraire que le minimum d'un tas, mais pas le maximum peut être résolu en gardant deux tas. Depuis que je ne connais pas le module HePQ, vous pourriez être en mesure de lui fournir votre propre fonction de comparaison ou vous pouvez simplement utiliser -Value au lieu de la valeur pour la clé de la clé de le deuxième tas.
Super idée d'utilisation de 2 tas. Une seule question: comment puis-je garder l'ordre des éléments? Parce que je dois calculer le min et max uniquement des derniers éléments 1000 ajoutés.
Si vous utilisez une taille finie (comme il semble) et que les objets sont petits (ce qui semble être le cas), utilisez simplement une troisième copie dans un objet de file d'attente. Cela signifie que vous avez triplé vos exigences en matière de mémoire, mais depuis a) la mémoire est bon marché, et b) Vous n'avez besoin que de taille finie, il semble être une solution valide.
@mklauber, mais si nous utilisons deque , nous devons toujours mettre à jour tas . J'ai regardé Le complexit d'opérations avec tas. L'insertion est de O (1) , la suppression est o (journal (n)) . Mais avant de supprimer, nous devons trouver le pointeur sur cette valeur. Quelle est la complexité de cette opération?
@fredley Les données doivent être monotoniques. Mais le L'algorithme de Monte Carlo repose sur un échantillonnage aléatoire, il peut donc avoir des surtensions. Donc, je ne peux pas être complètement sûr que c'est monotonique.