algorithm - Smart progress bar ETA computation
user-interface language-agnostic (11)
Promedio uniforme
El enfoque más simple sería predecir el tiempo restante linealmente:
t_rem := t_spent ( n - prog ) / prog
donde t_rem es la ETA pronosticada, t_spent es el tiempo transcurrido desde el comienzo de la operación, el número de microtasks finalizadas en su cantidad total n . Explicar puede ser la cantidad de filas en una tabla para procesar o la cantidad de archivos para copiar.
Este método no tiene parámetros, uno no necesita preocuparse por el ajuste del exponente de la atenuación. El trade-off es una adaptación pobre a una tasa de progreso cambiante porque todas las muestras tienen una contribución igual a la estimación, mientras que solo se cumple que las muestras recientes deberían tener más peso que las anteriores, lo que nos lleva a
Alisamiento exponencial de la tasa
en el que la técnica estándar es estimar la tasa de progreso promediando mediciones de puntos previos:
rate := 1 / (n * dt); { rate equals normalized progress per unit time }
if prog = 1 then { if first microtask just completed }
rate_est := rate; { initialize the estimate }
else
begin
weight := Exp( - dt / DECAY_T );
rate_est := rate_est * weight + rate * (1.0 - weight);
t_rem := (1.0 - prog / n) / rate_est;
end;
donde dt denota la duración de la última microtaxis completada y es igual al tiempo transcurrido desde la actualización de progreso anterior. Tenga en cuenta que el weight no es una constante y debe ajustarse de acuerdo con el período de tiempo durante el cual se observó una cierta rate , porque cuanto más tiempo observamos una cierta velocidad, mayor es la disminución exponencial de las mediciones anteriores. La constante DECAY_T indica el tiempo durante el cual el peso de una muestra disminuye por un factor de e . SPWorley mismo sugirió una modificación similar a la propuesta de Gooli , aunque la aplicó al término equivocado. Un promedio exponencial para mediciones equidistantes es:
Avg_e(n) = Avg_e(n-1) * alpha + m_n * (1 - alpha)
pero, ¿y si las muestras no son equidistantes, como es el caso con los tiempos en una barra de progreso típica? Tenga en cuenta que alpha arriba no es más que un cociente empírico cuyo verdadero valor es:
alpha = Exp( - lambda * dt ),
donde lambda es el parámetro de la ventana exponencial y dt la cantidad de cambio desde la muestra anterior, que no necesita ser el tiempo, sino cualquier parámetro lineal y aditivo. alpha es constante para mediciones equidistantes pero varía con dt .
Marque que este método se basa en una constante de tiempo predefinida y no es escalable en el tiempo. En otras palabras, si el mismo proceso exactamente se ralentiza uniformemente por un factor constante, este filtro basado en velocidad se volverá proporcionalmente más sensible a las variaciones de la señal porque en cada paso el weight disminuirá. Si, sin embargo, deseamos un alisamiento independiente de la escala de tiempo, debemos considerar
Suavizado exponencial de la lentitud
que es esencialmente el alisado de la velocidad al revés con la simplificación añadida de un weight constante de porque el prog está creciendo en incrementos equidistantes:
slowness := n * dt; { slowness is the amount of time per unity progress }
if prog = 1 then { if first microtask just completed }
slowness_est := slowness; { initialize the estimate }
else
begin
weight := Exp( - 1 / (n * DECAY_P ) );
slowness_est := slowness_est * weight + slowness * (1.0 - weight);
t_rem := (1.0 - prog / n) * slowness_est;
end;
La constante adimensional DECAY_P denota la diferencia de progreso normalizada entre dos muestras cuyos pesos están en la proporción de uno a e . En otras palabras, esta constante determina el ancho de la ventana de suavizado en el dominio de progreso, en lugar de en el dominio de tiempo. Esta técnica es por lo tanto independiente de la escala de tiempo y tiene una resolución espacial constante.
Futher research: suavizado exponencial adaptativo
Ahora está equipado para probar los diversos algoritmos de suavizado exponencial adaptativo . Solo recuerde aplicarlo a la lentitud en lugar de a la velocidad .
En muchas aplicaciones, tenemos alguna barra de progreso para la descarga de archivos, para una tarea de compresión, para una búsqueda, etc. Todos usamos barras de progreso para que los usuarios sepan que algo está sucediendo. Y si conocemos algunos detalles, como cuánto trabajo se ha hecho y cuánto queda por hacer, incluso podemos dar una estimación del tiempo, a menudo mediante la extrapolación de cuánto tiempo se tarda en llegar al nivel de progreso actual.
Pero también hemos visto programas que esta pantalla de "Time Left" "ETA" es cómicamente mala. Afirma que se realizará una copia de archivo en 20 segundos, luego, un segundo después, indica que tardará 4 días, luego parpadeará de nuevo en 20 minutos. No solo es inútil, ¡es confuso! La razón por la que ETA varía tanto es que la tasa de progreso en sí misma puede variar y las matemáticas del programador pueden ser demasiado sensibles.
¡Apple evita esto simplemente evitando cualquier predicción precisa y simplemente dando estimaciones vagas! Evasión vaga de Apple http://download.autodesk.com/esd/mudbox/help2009/images/MED/DaliSP1/English/Install_licensing/install_progress_MAC.png
Eso también es molesto, ¿tengo tiempo para un descanso rápido, o mi tarea se va a hacer en 2 segundos más? Si la predicción es demasiado confusa, no tiene sentido hacer ninguna predicción.
Métodos fáciles pero equivocados
Como cálculo de ETA de primer paso, probablemente todos hagamos una función como si p es el porcentaje fraccional que ya se ha hecho, yt es el tiempo que se ha tardado hasta ese momento, sacamos t * (1-p) / p como la estimación de cuánto tiempo tomará terminar. Esta simple relación funciona "OK", pero también es terrible, especialmente al final de la computación. Si su velocidad de descarga lenta mantiene una copia lentamente avanzando durante la noche, y finalmente en la mañana, algo comienza y la copia comienza a toda velocidad a 100X más rápido, su ETA al 90% puede decir "1 hora" y 10 segundos más tarde estás en el 95% y el ETA dirá "30 minutos", lo que es claramente una conjetura vergonzosamente pobre ... en este caso, "10 segundos" es una estimación mucho, mucho, mucho mejor.
Cuando esto suceda, puede pensar en cambiar el cálculo para usar la velocidad reciente , no la velocidad promedio, para estimar la ETA. Tomas la tasa de descarga promedio o la tasa de finalización en los últimos 10 segundos, y usas esa tasa para proyectar cuánto tiempo durará la finalización. Eso funciona bastante bien en el ejemplo anterior de descarga de una noche que se aceleró al final, ya que dará muy buenas estimaciones finales de finalización al final. Pero esto todavía tiene grandes problemas ... hace que tu ETA rebote violentamente cuando tu velocidad varía rápidamente en un corto período de tiempo, y obtienes el "hecho en 20 segundos, hecho en 2 horas, hecho en 2 segundos, hecho en 30 minutos "pantalla rápida de la vergüenza de programación.
La verdadera pregunta:
¿Cuál es la mejor manera de calcular un tiempo estimado de finalización de una tarea, dado el historial de tiempo del cálculo? No estoy buscando enlaces a kits de herramientas GUI o bibliotecas Qt. Estoy preguntando sobre el algoritmo para generar las estimaciones de tiempo de finalización más sanas y precisas.
¿Has tenido éxito con las fórmulas matemáticas? ¿Algún tipo de promedio, tal vez utilizando la media de la tasa en más de 10 segundos con la tasa de más de 1 minuto con la tasa de más de 1 hora? ¿Algún tipo de filtrado artificial como "si mi nueva estimación varía demasiado con respecto a la estimación anterior, rebaje el tono, no la deje rebotar demasiado"? ¿Algún tipo de análisis de historia sofisticado en el que se integra el progreso frente al avance del tiempo para encontrar la desviación estándar de la tasa para proporcionar métricas estadísticas de error una vez completada?
¿Qué has intentado y qué funciona mejor?
Respuesta original
La compañía que creó este sitio aparentemente hace un sistema de programación que responde a esta pregunta en el contexto de los empleados que escriben código. La forma en que funciona es con la simulación de futuro de Monte Carlo basada en el pasado.
Apéndice: Explicación de Monte Carlo
Así es como funcionaría este algoritmo en su situación:
Usted modela su tarea como una secuencia de microtasks, digamos 1000 de ellas. Supongamos que una hora más tarde completa 100 de ellos. Ahora ejecuta la simulación de los 900 pasos restantes seleccionando aleatoriamente 90 microtask completas, sumando sus tiempos y multiplicando por 10. Aquí tiene una estimación; repite N veces y tiene N estimaciones para el tiempo restante. Tenga en cuenta que el promedio entre estas estimaciones será de aproximadamente 9 horas, sin sorpresas aquí. Pero al presentar la distribución resultante al usuario, honestamente le comunicará las probabilidades, por ejemplo, ''con la probabilidad del 90% esto tomará otras 3-15 horas''
Este algoritmo, por definición, produce un resultado completo si la tarea en cuestión se puede modelar como un conjunto de microtask independientes y aleatorias . Puede obtener una mejor respuesta solo si sabe cómo la tarea se desvía de este modelo: por ejemplo, los instaladores suelen tener una lista de tareas para descargar / desempaquetar / instalar y la velocidad para uno no puede predecir la otra.
Apéndice: Simplificación de Monte Carlo
No soy un gurú de las estadísticas, pero creo que si miras más de cerca a la simulación en este método, siempre devolverá una distribución normal como una suma de un gran número de variables aleatorias independientes. Por lo tanto, no necesita realizarlo en absoluto. De hecho, ni siquiera necesita almacenar todos los tiempos completados, ya que solo necesitará su suma y suma de sus cuadrados.
En una notación quizás no muy estándar,
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)
Con esto, puede dar salida al mensaje diciendo que la cosa terminará entre [lowerBound, upperBound] a partir de ahora con alguna probabilidad fija (debería ser de aproximadamente 95%, pero probablemente haya pasado por alto algún factor constante).
¡Esto es lo que he encontrado funciona bien! Para el primer 50% de la tarea, asume que la velocidad es constante y extrapola. La predicción de tiempo es muy estable y no rebota mucho.
Una vez que pase el 50%, cambia la estrategia de cálculo. Tomas la fracción del trabajo que queda por hacer (1-p), luego miras atrás en el tiempo en un historial de tu propio progreso y encuentras (por búsqueda binaria e interpolación lineal) cuánto tiempo te lleva hacer el último (1 -p) porcentaje y utilícelo como su tiempo estimado de finalización.
Entonces, si ahora tienes un 71% de efectividad, te queda un 29%. Miras hacia atrás en tu historial y descubres cuánto tiempo estuviste (71-29 = 42%) completando. Informe ese tiempo como su ETA.
Esto es naturalmente adaptativo. Si tiene que hacer una X cantidad de trabajo, solo se ve el tiempo que tardó en hacer la cantidad de trabajo X. Al final, cuando hayas terminado el 99%, solo está usando datos muy recientes y recientes para la estimación.
No es perfecto, por supuesto, cambia suavemente y es especialmente preciso al final cuando es más útil.
En ciertos casos, cuando necesite realizar la misma tarea de forma regular, podría ser una buena idea utilizar los tiempos de finalización pasados para promediar.
Por ejemplo, tengo una aplicación que carga la biblioteca de iTunes a través de su interfaz COM. El tamaño de una biblioteca de iTunes dada generalmente no aumenta drásticamente desde el lanzamiento hasta el lanzamiento en términos del número de elementos, por lo que en este ejemplo podría ser posible rastrear los últimos tres tiempos de carga y tasas de carga y luego promediar contra eso y calcule su ETA actual.
Esto sería mucho más preciso que una medición instantánea y probablemente también más consistente.
Sin embargo, este método depende de que el tamaño de la tarea sea relativamente similar a los anteriores, por lo que esto no funcionaría para un método de descompresión u otra cosa donde cualquier corriente de bytes dada sea la información que se procesará.
Solo mi $ 0.02
En primer lugar, ayuda a generar un promedio móvil en ejecución. Esto pondera los eventos más recientes con más fuerza.
Para hacer esto, mantenga un montón de muestras alrededor (búfer circular o lista), cada una un par de progreso y tiempo. Mantenga los N segundos más recientes de las muestras. Luego genere un promedio ponderado de las muestras:
totalProgress += (curSample.progress - prevSample.progress) * scaleFactor
totalTime += (curSample.time - prevSample.time) * scaleFactor
donde scaleFactor va linealmente desde 0 ... 1 como una función inversa del tiempo en el pasado (por lo tanto, pesa más las muestras más recientes). Puedes jugar con esta ponderación, por supuesto.
Al final, puede obtener la tasa promedio de cambio:
averageProgressRate = (totalProgress / totalTime);
Puede usar esto para calcular el ETA dividiendo el progreso restante por este número.
Sin embargo, aunque esto le da un buen número de tendencias, tiene otro problema: la inestabilidad. Si, debido a las variaciones naturales, su ritmo de progreso se mueve un poco (es ruidoso), por ejemplo, tal vez esté usando esto para estimar las descargas de archivos, notará que el ruido puede hacer que su ETA salte fácilmente, especialmente si está bastante lejos en el futuro (varios minutos o más).
Para evitar que la trepidación afecte demasiado su ETA, quiere que esta tasa promedio de cambio responda lentamente a las actualizaciones. Una forma de abordar esto es mantener un valor almacenado en caché de averageProgressRate, y en lugar de actualizarlo instantáneamente al número de tendencia que acaba de calcular, simularlo como un objeto físico pesado con masa, aplicando una ''fuerza'' simulada para moverlo hacia el número de tendencia. Con masa, tiene un poco de inercia y es menos probable que se vea afectada por la inestabilidad.
Aquí hay una muestra aproximada:
// desiredAverageProgressRate is computed from the weighted average above
// m_averageProgressRate is a member variable also in progress units/sec
// lastTimeElapsed = the time delta in seconds (since last simulation)
// m_averageSpeed is a member variable in units/sec, used to hold the
// the velocity of m_averageProgressRate
const float frictionCoeff = 0.75f;
const float mass = 4.0f;
const float maxSpeedCoeff = 0.25f;
// lose 25% of our speed per sec, simulating friction
m_averageSeekSpeed *= pow(frictionCoeff, lastTimeElapsed);
float delta = desiredAvgProgressRate - m_averageProgressRate;
// update the velocity
float oldSpeed = m_averageSeekSpeed;
float accel = delta / mass;
m_averageSeekSpeed += accel * lastTimeElapsed; // v += at
// clamp the top speed to 25% of our current value
float sign = (m_averageSeekSpeed > 0.0f ? 1.0f : -1.0f);
float maxVal = m_averageProgressRate * maxSpeedCoeff;
if (fabs(m_averageSeekSpeed) > maxVal)
{
m_averageSeekSpeed = sign * maxVal;
}
// make sure they have the same sign
if ((m_averageSeekSpeed > 0.0f) == (delta > 0.0f))
{
float adjust = (oldSpeed + m_averageSeekSpeed) * 0.5f * lastTimeElapsed;
// don''t overshoot.
if (fabs(adjust) > fabs(delta))
{
adjust = delta;
// apply damping
m_averageSeekSpeed *= 0.25f;
}
m_averageProgressRate += adjust;
}
He intentado y simplificado su fórmula "fácil" / "incorrecta" / "OK" y funciona mejor para mí:
t / p - t
En Python:
>>> done=0.3; duration=10; "time left: %i" % (duration / done - duration)
''time left: 23''
Eso ahorra una operación en comparación con (dur * (1-hecho) / hecho). Y, en el caso de borde que describes, posiblemente ignorar el diálogo durante 30 minutos extra no importa después de esperar toda la noche.
Comparing este método simple con el utilizado por Transmission , encontré que es hasta un 72% más preciso.
No lo sudo, es una parte muy pequeña de una aplicación. Les digo lo que está pasando y los dejo hacer otra cosa.
Si bien todos los ejemplos son válidos, para el caso específico de ''tiempo de descarga'', pensé que sería una buena idea mirar los proyectos de código abierto existentes para ver qué hacen.
Por lo que puedo ver, Mozilla Firefox es el mejor para estimar el tiempo restante.
Mozilla Firefox
Firefox realiza un seguimiento de la última estimación del tiempo restante, y al usar esto y la estimación actual para el tiempo restante, realiza una función de suavizado en el tiempo. Vea el código de ETA here . Utiliza una ''velocidad'' que se calcula previamente here y es un promedio suavizado de las últimas 10 lecturas.
Esto es un poco complejo, parafraseando:
- Tome un promedio suavizado de la velocidad basado en el 90% de la velocidad anterior y el 10% en la nueva velocidad.
- Con esta velocidad promedio suavizada, resuelva el tiempo restante estimado.
- Utilice este tiempo estimado restante y el tiempo restante estimado anterior para crear un nuevo tiempo estimado restante (para evitar saltar)
Google Chrome
Chrome parece saltar por todos lados, y el código muestra esto .
Una cosa que sí me gusta con Chrome es cómo formatear el tiempo restante. Durante> 1 hora, dice ''quedan 1 hora''. Durante <1 hora, dice ''59 minutos restantes ''. Durante <1 minuto, dice ''52 segundos a la izquierda''.
Puedes ver cómo está formateado here
¡Bájenlos a todos! Gerente
No usa nada inteligente, lo que significa que la ETA salta por todos lados.
Vea el código aquí
pySmartDL (un descargador de python)
Toma la ETA promedio de los últimos 30 cálculos de ETA. Suena como una forma razonable de hacerlo.
Vea el código here /blob/916f2592db326241a2bf4d8f2e0719c58b71e385/pySmartDL/pySmartDL.py#L651)
Transmisión
Da una ETA bastante buena en la mayoría de los casos (excepto cuando se inicia, como podría esperarse).
Utiliza un factor de suavizado en las últimas 5 lecturas, similar a Firefox pero no tan complejo. Fundamentalmente similar a la respuesta de Gooli.
Vea el código here
Siempre deseé que estas cosas me dieran un rango. Si dijera: "Esta tarea probablemente se realizará entre 8 minutos y 30 minutos", entonces tengo una idea de qué tipo de descanso tomar. Si está rebotando por todos lados, estoy tentado de verlo hasta que se estabilice, lo que es una gran pérdida de tiempo.
Tu pregunta es buena. Si el problema se puede dividir en unidades discretas que tienen un cálculo preciso a menudo funciona mejor. Desafortunadamente, este puede no ser el caso, incluso si está instalando 50 componentes, cada uno podría ser del 2%, pero uno de ellos puede ser masivo. Una cosa con la que he tenido un éxito moderado es registrar la CPU y el disco y dar una estimación decente basada en datos de observación. El hecho de saber que ciertos puntos de control son realmente el punto x le da la oportunidad de corregir los factores del entorno (red, actividad del disco, carga de la CPU). Sin embargo, esta solución no es de naturaleza general debido a su dependencia de los datos de observación. Usar datos auxiliares como el tamaño del archivo rpm me ayudó a hacer que mis barras de progreso fueran más precisas, pero nunca son a prueba de balas.
Usualmente uso un Promedio móvil exponencial para calcular la velocidad de una operación con un factor de suavizado de, por ejemplo, 0.1 y lo uso para calcular el tiempo restante. De esta forma, todas las velocidades medidas tienen influencia sobre la velocidad actual, pero las mediciones recientes tienen mucho más efecto que las del pasado distante.
En el código se vería algo como esto:
alpha = 0.1 # smoothing factor
...
speed = (speed * (1 - alpha)) + (currentSpeed * alpha)
Si sus tareas son uniformes en tamaño, currentSpeed simplemente sería el tiempo necesario para ejecutar la última tarea. Si las tareas tienen diferentes tamaños y sabe que una tarea se supone que es i, e, el doble que la otra, puede dividir el tiempo necesario para ejecutar la tarea por su tamaño relativo para obtener la velocidad actual. Usando la speed puede calcular el tiempo restante multiplicándolo por el tamaño total de las tareas restantes (o solo por su número si las tareas son uniformes).
Espero que mi explicación sea lo suficientemente clara, es un poco tarde en el día.