Barre de progression intelligente Calcul de l'ETA

Question

Dans de nombreuses applications, nous avons une barre de progression pour le téléchargement d'un fichier, pour une tâche de compression, pour une recherche, etc. Nous utilisons tous souvent des barres de progression pour faire savoir aux utilisateurs que quelque chose est en train de se passer. Nous utilisons tous souvent des barres de progression pour indiquer aux utilisateurs que quelque chose est en train de se passer. Et si nous connaissons certains détails, comme la quantité de travail effectuée et la quantité restante, nous pouvons même donner une estimation du temps, souvent en extrapolant à partir du temps qu'il a fallu pour atteindre le niveau de progression actuel.

_{(source : <a href="http://jameslao.com/wp-content/uploads/2008/01/winrar-progress-bar.png" rel="noreferrer">jameslao.com </a>)}

Mais nous avons également vu des programmes dont l'affichage du temps restant "ETA" est tout simplement comique. Il prétend qu'une copie de fichier sera effectuée en 20 secondes, puis une seconde plus tard il dit que cela va prendre 4 jours, puis il clignote à nouveau pour être de 20 minutes. Ce n'est pas seulement inutile, c'est déroutant ! La raison pour laquelle l'ETA varie autant est que le taux de progression lui-même peut varier et que les calculs du programmeur peuvent être trop sensibles.

Apple contourne ce problème en évitant toute prédiction précise et en ne donnant que de vagues estimations !
_{(source : <a href="https://download.autodesk.com/esd/mudbox/help2009/images/MED/DaliSP1/English/Install_licensing/install_progress_MAC.png" rel="noreferrer">autodesk.com </a>)}

C'est aussi ennuyeux, ai-je le temps de faire une petite pause, ou ma tâche va-t-elle être terminée dans 2 secondes ? Si la prédiction est trop floue, il est inutile de faire une prédiction.

Des méthodes faciles mais erronées

En tant que première passe de calcul de l'ETA, nous pouvons probablement créer une fonction telle que si p est le pourcentage fractionnel de ce qui est déjà fait, et t est le temps que cela a pris jusqu'à présent, nous produisons t*(1-p)/p comme estimation du temps que cela va prendre pour finir. Ce simple ratio fonctionne "bien" mais il est aussi terrible, surtout à la fin du calcul. Si votre vitesse de téléchargement lente maintient une copie qui avance lentement pendant la nuit, et finalement le matin, quelque chose se produit et la copie commence à aller à pleine vitesse à 100X plus rapide, votre ETA à 90% fait peut dire "1 heure", et 10 secondes plus tard vous êtes à 95% et l'ETA dira "30 minutes" qui est clairement une estimation honteusement pauvre. dans ce cas "10 secondes" est une estimation beaucoup, beaucoup, beaucoup mieux.

Lorsque cela se produit, vous pouvez penser à modifier le calcul pour utiliser récent la vitesse, et non la vitesse moyenne, pour estimer l'ETA. Vous prenez le taux de téléchargement moyen ou le taux d'achèvement sur les 10 dernières secondes, et vous utilisez ce taux pour prévoir le temps d'achèvement. Cette méthode fonctionne très bien dans l'exemple précédent du téléchargement pendant la nuit qui s'accélère à la fin, puisqu'elle donne une très bonne estimation de l'achèvement final à la fin. Mais cela présente encore de gros problèmes cela fait rebondir votre ETA de manière sauvage lorsque votre taux varie rapidement sur une courte période de temps, et vous obtenez l'affichage rapide de la honte de la programmation "terminé en 20 secondes, terminé en 2 heures, terminé en 2 secondes, terminé en 30 minutes".

La vraie question :

Quelle est la meilleure façon de calculer le temps estimé d'achèvement d'une tâche, compte tenu de l'historique du calcul ? Je ne cherche pas de liens vers des boîtes à outils GUI ou des bibliothèques Qt. Je m'interroge sur la algorithme pour générer les estimations de temps de réalisation les plus saines et les plus précises.

Avez-vous eu du succès avec les formules mathématiques ? Une sorte de moyenne, peut-être en utilisant la moyenne du taux sur 10 secondes avec le taux sur 1 minute avec le taux sur 1 heure ? Une sorte de filtrage artificiel du type "si ma nouvelle estimation varie trop par rapport à l'estimation précédente, atténuez-la, ne la laissez pas trop rebondir" ? Une sorte d'analyse fantaisiste de l'historique où vous intégrez la progression par rapport à l'avancement du temps pour trouver l'écart type du taux afin de donner des mesures d'erreurs statistiques sur l'achèvement ?

Qu'avez-vous essayé, et qu'est-ce qui fonctionne le mieux ?

Answer 1

Réponse originale

La société qui a créé ce site fait apparemment un système d'ordonnancement qui répond à cette question dans le contexte où les employés écrivent du code. La façon dont il fonctionne est une simulation de Monte Carlo du futur basée sur le passé.

Annexe : Explication de la méthode de Monte Carlo

Voici comment cet algorithme fonctionnerait dans votre situation :

Vous modélisez votre tâche comme une séquence de microtâches, disons 1000. Supposons qu'une heure plus tard, vous en ayez accompli 100. Vous exécutez maintenant la simulation pour les 900 étapes restantes en choisissant au hasard 90 microtâches terminées, en additionnant leurs temps et en les multipliant par 10. Vous obtenez ainsi une estimation ; répétez cette opération N fois et vous obtiendrez N estimations du temps restant. Notez que la moyenne entre ces estimations sera d'environ 9 heures - pas de surprise ici. Mais en présentant la distribution résultante à l'utilisateur, vous lui communiquerez honnêtement les probabilités, par exemple : "avec une probabilité de 90%, cela prendra encore 3 à 15 heures".

Cet algorithme, par définition, produit un résultat complet si la tâche en question peut être modélisée comme un ensemble de indépendant, aléatoire micro-tâches. Vous ne pouvez obtenir une meilleure réponse que si vous savez comment la tâche s'écarte de ce modèle : par exemple, les installateurs ont généralement une liste de tâches de téléchargement/déballage/installation et la vitesse de l'une ne peut pas prédire l'autre.

Annexe : Simplifier Monte Carlo

Je ne suis pas un gourou des statistiques, mais je pense que si vous regardez de plus près la simulation dans cette méthode, elle retournera toujours une distribution normale comme une somme d'un grand nombre de variables aléatoires indépendantes. Par conséquent, vous n'avez pas besoin de l'effectuer du tout. En fait, vous n'avez même pas besoin de stocker tous les temps réalisés, puisque vous n'aurez besoin que de leur somme et de la somme de leurs carrés.

Dans une notation peut-être pas très standard,

sigma = sqrt ( sum_of_times_squared-sum_of_times^2 )
scaling = 900/100          // that is (totalSteps - elapsedSteps) / elapsedSteps
lowerBound = sum_of_times*scaling - 3*sigma*sqrt(scaling)
upperBound = sum_of_times*scaling + 3*sigma*sqrt(scaling)

Avec cela, vous pouvez produire le message disant que la chose se terminera entre [lowerBound, upperBound] à partir de maintenant avec une certaine probabilité fixe (devrait être environ 95%, mais j'ai probablement oublié un facteur constant).

Answer 2

Voici ce que j'ai trouvé qui fonctionne bien ! Pour les premiers 50% de la tâche, vous supposez que le taux est constant et vous extrapolez. La prédiction du temps est très stable et ne rebondit pas beaucoup.

Une fois que vous avez dépassé les 50%, vous commutateur stratégie de calcul. Vous prenez la fraction du travail qu'il vous reste à faire (1-p), puis vous regardez en arrière dans un historique de vos propres progrès, et vous trouvez (par recherche binaire et interpolation linéaire) combien de temps il vous a fallu pour faire le dernier pourcentage (1-p) et vous utilisez que comme votre estimation de temps d'achèvement.

Donc, si vous êtes maintenant à 71%, il vous reste 29%. Vous regardez dans votre historique et trouvez combien de temps il y a eu (71-29=42%) d'achèvement. Vous indiquez ce temps comme étant votre heure d'arrivée prévue.

C'est naturellement adaptatif. Si vous avez une quantité X de travail à faire, il ne regarde que le temps qu'il a fallu pour faire cette quantité X de travail. À la fin, lorsque vous avez terminé à 99 %, il n'utilise que des données très fraîches et très récentes pour l'estimation.

Il n'est pas parfait, bien sûr, mais il évolue en douceur et est particulièrement précis à la toute fin, quand il est le plus utile.

Answer 3

J'utilise généralement un Moyenne mobile exponentielle pour calculer la vitesse d'une opération avec un facteur de lissage de 0,1, par exemple, et l'utiliser pour calculer le temps restant. De cette façon, toutes les vitesses mesurées ont une influence sur la vitesse actuelle, mais les mesures récentes ont beaucoup plus d'effet que celles du passé lointain.

En code, cela ressemblerait à quelque chose comme ceci :

alpha = 0.1 # smoothing factor
...
speed = (speed * (1 - alpha)) + (currentSpeed * alpha)

Si vos tâches sont de taille uniforme, currentSpeed serait simplement le temps qu'il a fallu pour exécuter la dernière tâche. Si les tâches ont des tailles différentes et que vous savez qu'une tâche est censée être i,e, deux fois plus longue qu'une autre, vous pouvez diviser le temps d'exécution de la tâche par sa taille relative pour obtenir la vitesse actuelle. Utilisation de speed vous pouvez calculer le temps restant en le multipliant par la taille totale des tâches restantes (ou simplement par leur nombre si les tâches sont uniformes).

J'espère que mon explication est suffisamment claire, il est un peu tard.

Answer 4

Dans certains cas, lorsque vous devez effectuer la même tâche de manière régulière, il peut être judicieux d'utiliser les temps d'exécution passés pour établir une moyenne.

Par exemple, j'ai une application qui charge la bibliothèque iTunes via son interface COM. La taille d'une bibliothèque iTunes donnée n'augmente généralement pas de façon spectaculaire d'un lancement à l'autre en termes de nombre d'éléments, de sorte que dans cet exemple, il serait possible de suivre les trois derniers temps de chargement et taux de chargement, puis d'en faire la moyenne et de calculer votre ETA actuelle.

Cela serait beaucoup plus précis qu'une mesure instantanée et probablement aussi plus cohérent.

Cependant, cette méthode dépend du fait que la taille de la tâche soit relativement similaire à celle des tâches précédentes. Elle ne fonctionnerait donc pas pour une méthode de décompression ou autre où un flux d'octets donné constitue les données à traiter.

C'est juste mon avis.

Answer 5

Votre question est pertinente. Si le problème peut être décomposé en unités discrètes, un calcul précis est souvent la meilleure solution. Malheureusement, ce n'est pas toujours le cas, même si vous installez 50 composants, chacun d'entre eux peut représenter 2 %, mais l'un d'entre eux peut être énorme. Une chose avec laquelle j'ai eu un succès modéré est de chronométrer le processeur et le disque et de donner une estimation décente basée sur des données d'observation. Le fait de savoir que certains points de contrôle sont en réalité le point x vous donne la possibilité de corriger les facteurs environnementaux (réseau, activité du disque, charge du CPU). Cependant, cette solution n'est pas générale par nature, car elle repose sur des données d'observation. L'utilisation de données auxiliaires telles que la taille du fichier rpm m'a aidé à rendre mes barres de progression plus précises, mais elles ne sont jamais infaillibles.