Умный индикатор выполнения ETA

Question

Во многих приложениях у нас есть индикатор выполнения загрузки файла, задачи сжатия, поиска и т. Д. Мы все часто используем индикатор выполнения, чтобы пользователи знали, что что-то происходит. И если мы знаем некоторые детали, например, сколько работы было проделано и сколько еще осталось сделать, мы можем даже дать оценку времени, часто путем экстраполяции того, сколько времени понадобилось, чтобы добраться до текущего уровня прогресса.

скриншот ETA сжатия http://jameslao.com/wp-content/uploads/2008/01/winrar-progress-bar.png

Но мы также видели программы, которые отображают «оставшееся время» «ETA» просто комично. Он утверждает, что копирование файла будет сделано через 20 секунд, затем через одну секунду он говорит, что это займет 4 дня, затем он снова начнет мигать, чтобы быть 20 минут. Это не только бесполезно, но и сбивает с толку! Причина, по которой ETA так сильно различается, заключается в том, что скорость выполнения может меняться, а математика программиста может быть слишком чувствительной.

Apple обходит это, просто избегая любых точных прогнозов и просто давая неопределенные оценки!
_{(источник: autodesk.com )}

Это тоже раздражает, у меня есть время для быстрого перерыва, или моя задача будет выполнена еще через 2 секунды? Если предсказание слишком нечеткое, делать какие-либо прогнозы вообще бессмысленно.

Простые, но неправильные методы

В качестве вычисления первого прохода ETA, вероятно, мы все просто создаем функцию, например, если p - это уже сделанный дробный процент, а t - это время, которое требуется для этого, мы выводим t * (1-p) / p как оценка того, сколько времени потребуется, чтобы закончить. Это простое соотношение работает «ОК», но оно также ужасно, особенно в конце вычислений. Если из-за низкой скорости загрузки происходит медленное продвижение копии в одночасье и, наконец, утром, что-то срабатывает, и копия начинает работать на полной скорости со скоростью 100Х, ваш ETA на 90% завершится, может сказать «1 час» и 10 секунд позже вы наберете 95%, и ETA скажет «30 минут», что явно смущающе плохое предположение… в этом случае «10 секунд» - намного, намного, намного лучшая оценка.

Когда это происходит, вы можете подумать о том, чтобы изменить вычисление, чтобы использовать недавнюю скорость, а не среднюю скорость, для оценки ETA. Вы берете среднюю скорость загрузки или скорость завершения за последние 10 секунд и используете эту частоту, чтобы прогнозировать, как долго будет выполняться. Это довольно хорошо работает в предыдущем примере «загрузка за ночь, который ускорился в конце», поскольку в конце он даст очень хорошие окончательные оценки завершения. Но у этого все еще есть большие проблемы ... это заставляет ваш ETA сильно подпрыгивать, когда ваша скорость быстро меняется в течение короткого периода времени, и вы получаете "сделано за 20 секунд, сделано за 2 часа, сделано за 2 секунды, сделано за 30 минут "быстрое отображение позора программирования.

Актуальный вопрос:

Каков наилучший способ вычисления предполагаемого времени выполнения задачи, учитывая историю вычислений? Я не ищу ссылки на наборы инструментов GUI или библиотеки Qt. Я спрашиваю об алгоритме , чтобы генерировать наиболее разумные и точные оценки времени завершения.

У вас были успехи с математическими формулами? Какое-то усреднение, может быть, с использованием среднего значения ставки за 10 секунд со скоростью более 1 минуты со скоростью более 1 часа? Какой-то искусственный фильтр типа «если моя новая оценка слишком сильно отличается от предыдущей оценки, уменьшите ее, не дайте ей слишком сильно отскочить»? Какой-то необычный анализ истории, в котором вы интегрируете прогресс и прогресс по времени, чтобы найти стандартное отклонение скорости, чтобы получить статистические показатели ошибок по завершении?

Что вы пробовали и что работает лучше всего?

Answer 1

Оригинальный ответ

Компания, создавшая этот сайт , по-видимому, делает системой планирования, которая отвечает на этот вопрос в контексте написания кода сотрудниками. Это работает с помощью симуляции будущего Монте-Карло, основанной на прошлом.

Приложение: объяснение Монте-Карло

Вот как этот алгоритм будет работать в вашей ситуации:

Вы моделируете свою задачу как последовательность микрозадач, скажем, 1000 из них. Предположим, через час вы завершили 100 из них. Теперь вы запустите симуляцию для оставшихся 900 шагов, случайным образом выбрав 90 выполненных микрозадач, добавив их время и умножив на 10. Здесь у вас есть оценка; повторите N раз, и у вас будет N оценок за оставшееся время. Обратите внимание, что среднее между этими оценками будет около 9 часов - здесь никаких сюрпризов. Но, представив полученный дистрибутив пользователю, вы честно сообщите ему шансы, например, «с вероятностью 90% это займет еще 3-15 часов»

Этот алгоритм, по определению, дает полный результат, если рассматриваемая задача может быть смоделирована как набор независимых, случайных микрозадач. Вы можете получить лучший ответ, только если знаете, как задача отличается от этой модели: например, установщики обычно имеют список задач для загрузки / распаковки / установки, и скорость для одного не может предсказать другое.

Приложение: Упрощение Монте-Карло

Я не гуру статистики, но я думаю, что если вы посмотрите подробнее на симуляцию в этом методе, он всегда вернет нормальное распределение в виде суммы большого числа независимых случайных величин. Поэтому вам не нужно выполнять это вообще. На самом деле вам даже не нужно хранить все завершенные времена, так как вам понадобится только их сумма и сумма их квадратов.

В, возможно, не очень стандартной записи,

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)

При этом вы можете вывести сообщение о том, что с этого момента между [lowerBound, upperBound] с некоторой фиксированной вероятностью (с вероятностью около 95%, но я, вероятно, пропустил некоторый постоянный коэффициент), вещь будет заканчиваться.

Answer 2

Вот то, что я нашел, работает хорошо! Для первых 50% задания вы предполагаете, что показатель постоянен, и экстраполируете. Прогноз времени очень стабилен и не сильно отскакивает.

Как только вы пройдете 50%, вы переключитесь на вычислительную стратегию. Вы берете часть оставшейся работы (1-p), затем оглядываетесь назад во времени в истории своего собственного прогресса и находите (с помощью бинарного поиска и линейной интерполяции), сколько времени вам потребовалось, чтобы выполнить последнее (1 -p) в процентах и ​​использовать , что , в качестве оценки времени выполнения.

Так что, если вы сделали 71%, у вас осталось 29%. Вы оглядываетесь назад в своей истории и обнаруживаете, как давно вы завершили (71-29 = 42%). Сообщите это время как ваше ETA.

Это естественно адаптивно. Если у вас есть Х объем работы, он выглядит только в то время, которое потребовалось для выполнения Х объема работы. В конце, когда вы закончите на 99%, он использует только очень свежие, самые последние данные для оценки.

Конечно, он не идеален, но плавно меняется и особенно точен в самом конце, когда он наиболее полезен.

Answer 3

Я обычно использую Экспоненциальное скользящее среднее , чтобы вычислить скорость операции с коэффициентом сглаживания, скажем, 0,1, и использую ее для вычисления оставшегося времени. Таким образом, все измеренные скорости влияют на текущую скорость, но недавние измерения имеют гораздо больший эффект, чем в далеком прошлом.

В коде это будет выглядеть примерно так:

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

Если ваши задачи одинакового размера, currentSpeed будет просто временем, которое потребовалось для выполнения последней задачи. Если задачи имеют разные размеры, и вы знаете, что одна задача должна быть i, e, вдвое длиннее другой, вы можете разделить время, необходимое для выполнения задачи, на ее относительный размер, чтобы получить текущую скорость. Используя speed, вы можете вычислить оставшееся время, умножив его на общий размер оставшихся задач (или просто на их количество, если задачи одинаковы).

Надеюсь, мои объяснения достаточно ясны, немного поздно.

Answer 4

Хотя все примеры верны, для конкретного случая «оставшегося времени для загрузки» я подумал, что было бы неплохо взглянуть на существующие проекты с открытым исходным кодом, чтобы увидеть, что они делают.

Из того, что я вижу, Mozilla Firefox лучше всего оценивает оставшееся время.

Mozilla Firefox

Firefox отслеживает последнюю оценку оставшегося времени и, используя эту и текущую оценку оставшегося времени, выполняет функцию сглаживания времени. Смотрите ETA код здесь . При этом используется «скорость», которая ранее рассчитана здесь и является сглаженным средним значением последних 10 показаний.

Это немного сложно, поэтому перефразирую:

• Возьмите сглаженное среднее значение скорости на основе 90% от предыдущей скорости и 10% от новой скорости.
• С этой сглаженной средней скоростью рассчитайте оставшееся время.
• Используйте это расчетное оставшееся время и предыдущее расчетное время, оставшееся до создания нового расчетного оставшегося времени (во избежание прыжков)

Google Chrome

Хром, кажется, прыгает повсюду, и код показывает это .

Что мне нравится в Chrome, так это то, как они форматируют оставшееся время. В течение> 1 часа написано «осталось 1 час» В течение <1 часа написано «59 минут осталось» <1 минута «52 секунд осталось» </p>

Вы можете посмотреть, как он отформатирован здесь

DownThemAll! Менеджер

Он не использует ничего умного, то есть ETA прыгает повсюду.

См. код здесь

pySmartDL (загрузчик Python)

Принимает среднее ETA из последних 30 расчетов ETA. Похоже, разумный способ сделать это.

См. Код здесь / blob / 916f2592db326241a2bf4d8f2e0719c58b71e385 / pySmartDL / pySmartDL.py # L651)

Трансмиссия

В большинстве случаев дает довольно хорошее ETA (кроме как при запуске, как и следовало ожидать).

Использует коэффициент сглаживания за последние 5 чтений, аналогичный Firefox, но не такой сложный. Принципиально похож на ответ Голи.

См. Код здесь

Answer 5

Во-первых, это помогает генерировать скользящую среднюю. Это отягощает более поздние события в большей степени.

Чтобы сделать это, держите кучу семплов (круговой буфер или список), каждая пара прогресса и времени. Сохраняйте последние N секунд выборок. Затем сгенерируйте средневзвешенное значение выборок:

totalProgress += (curSample.progress - prevSample.progress) * scaleFactor
totalTime += (curSample.time - prevSample.time) * scaleFactor

, где scaleFactor идет линейно от 0 ... 1 как обратная функция времени в прошлом (таким образом, более взвешенные более свежие выборки). Конечно, вы можете поиграть с этим весом.

В конце вы можете получить среднюю скорость изменения:

 averageProgressRate = (totalProgress / totalTime);

Вы можете использовать это, чтобы выяснить ETA, разделив оставшийся прогресс на это число.

Однако, хотя это дает вам хорошее число трендов, у вас есть еще одна проблема - джиттер. Если из-за естественных отклонений ваша скорость прогресса немного меняется (например, шумно) - например, возможно, вы используете это для оценки загрузки файлов - вы заметите, что шум может легко заставить ваш ETA перепрыгнуть, особенно если это довольно далеко в будущем (несколько минут или больше).

Чтобы джиттер не оказывал слишком сильного влияния на ваше ETA, вы хотите, чтобы средняя скорость изменения медленно реагировала на обновления. Одним из способов решения этой проблемы является сохранение кэшированного значения averageProgressRate, и вместо того, чтобы мгновенно обновлять его до только что рассчитанного числа трендов, вы моделируете его как тяжелый физический объект с массой, применяя смоделированную «силу» для медленного переместите его к трендовому номеру. Что касается массы, она имеет небольшую инерцию и меньше подвержена влиянию джиттера.

Вот примерный пример:

// 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;
}    

Answer 6

В некоторых случаях, когда вам нужно выполнять одно и то же задание на регулярной основе, рекомендуется использовать среднее время завершения за прошлые периоды.

Например, у меня есть приложение, которое загружает библиотеку iTunes через интерфейс COM. Размер данной библиотеки iTunes, как правило, резко не увеличивается от запуска к запуску с точки зрения количества элементов, поэтому в этом примере может быть возможным отслеживать последние три времени загрузки и скорости загрузки, а затем усреднять их и вычислите текущее ETA.

Это было бы гораздо более точным, чем мгновенное измерение, и, вероятно, также более последовательным.

Однако этот метод зависит от того, насколько размер задачи относительно схож с предыдущими, поэтому он не будет работать для метода декомпрессии или чего-то еще, где любой данный поток байтов является данными, которые будут обработаны.

Только мои $ 0,02

Answer 7

Ваш вопрос хороший. Если проблема может быть разбита на отдельные единицы, точный расчет часто работает лучше всего. К сожалению, это может быть не так, даже если вы устанавливаете 50 компонентов, каждый из которых может быть 2%, но один из них может быть массивным. Одна вещь, с которой я добился умеренного успеха, - это синхронизировать процессор и диск и дать достойную оценку на основе данных наблюдений. Знание того, что определенные контрольные точки действительно являются точкой x, дает вам некоторую возможность скорректировать факторы среды (сеть, активность диска, загрузка процессора). Однако это решение не носит общего характера из-за его зависимости от данных наблюдений. Использование вспомогательных данных, таких как размер файла rpm, помогло мне сделать мои индикаторы выполнения более точными, но они никогда не являются пуленепробиваемыми.

Answer 8

равномерное усреднение

Простейшим подходом будет линейное прогнозирование оставшегося времени:

t_rem := t_spent ( n - prog ) / prog

, где t_rem - это прогнозируемое ETA, t_spent - время, прошедшее с начала операции, prog - количество выполненных микрозадач из их полного количества n. Для объяснения - n может быть числом строк в таблице для обработки или количеством файлов для копирования.

В этом методе, не имеющем параметров, не нужно беспокоиться о точной настройке показателя ослабления. Компромисс - плохая адаптация к изменяющейся скорости прогресса, потому что все выборки имеют равный вклад в оценку, тогда как только встречается, что последние выборки должны иметь больший вес, чем старые, что приводит нас к

Экспоненциальное сглаживание курса

, в котором стандартным методом является оценка скорости прогресса путем усреднения предыдущих точечных измерений:

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;

где dt обозначает продолжительность последней выполненной микрозадачи и равно времени, прошедшему с момента предыдущего обновления прогресса. Обратите внимание, что weight не является постоянной величиной и должна быть отрегулирована в соответствии с периодом времени, в течение которого наблюдалось определенное rate, поскольку чем дольше мы наблюдали определенную скорость, тем выше экспоненциальный спад предыдущих измерений. Константа DECAY_T обозначает промежуток времени, в течение которого вес образца уменьшается в e . SPWorley сам предложил аналогичную модификацию предложения gooli , хотя и применил его к неправильному термину. Экспоненциальное среднее для эквидистантных измерений:

Avg_e(n) = Avg_e(n-1) * alpha + m_n * (1 - alpha)

а что если сэмплы не равноудалены, как в случае со временем в типичном индикаторе выполнения? Примите во внимание, что alpha выше является лишь эмпирическим частным, истинное значение которого:

alpha = Exp( - lambda * dt ),

, где lambda - это параметр экспоненциального окна, а dt - величина изменения с предыдущей выборки, которая должна быть не временем, а любым линейным и аддитивным параметром. alpha является постоянным для эквидистантных измерений, но изменяется с dt.

Отметьте, что этот метод основан на предварительно определенной постоянной времени и не масштабируется во времени. Другими словами, если точно такой же процесс будет равномерно замедлен с постоянным коэффициентом, этот основанный на скорости фильтр станет пропорционально более чувствительным к изменениям сигнала, потому что на каждом шаге weight будет уменьшаться. Однако, если мы хотим сглаживания, независимого от масштаба времени, нам следует рассмотреть

Экспоненциальное сглаживание медленности

, что, по сути, является сглаживанием курса, перевернутым с добавлением упрощения константы weight, поскольку prog растет с равноудаленными приращениями:

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;

Безразмерная константа DECAY_P обозначает нормированную разность хода между двумя выборками, вес которых находится в соотношении один к e . Другими словами, эта константа определяет ширину окна сглаживания в области прогресса, а не во временной области. Поэтому этот метод не зависит от масштаба времени и имеет постоянное пространственное разрешение.

Дальнейшие исследования: адаптивное экспоненциальное сглаживание

Теперь у вас есть возможность попробовать различные алгоритмы адаптивного экспоненциального сглаживания . Только не забудьте применить его к медлительности , а не к скорости .

Answer 9

Я попробовал и упростил вашу формулу «легко» / «неправильно» / «ОК», и она лучше всего работает для меня:

t / p - t

В Python:

>>> done=0.3; duration=10; "time left: %i" % (duration / done - duration)
'time left: 23'

Это спасает одну операцию по сравнению с (dur * (1-done) / done). И в крайнем случае, который вы описываете, возможно, игнорирование диалога в течение 30 дополнительных минут вряд ли имеет значение после ожидания всю ночь.

Сравнивая этот простой метод с тот, который использовался Transmission , я обнаружил, что он с точностью до 72%.

Answer 10

Я всегда хотел бы, чтобы эти вещи говорили мне о диапазоне. Если он сказал: «Скорее всего, это задание будет выполнено за 8–30 минут», тогда у меня есть представление о том, какой перерыв сделать. Если он подпрыгивает повсюду, я испытываю желание наблюдать за ним, пока он не успокоится, что является большой тратой времени.