Умный индикатор выполнения ETA
Во многих приложениях у нас есть некоторые индикаторы выполнения для загрузки файла, задачи сжатия, поиска и т. Д. Мы все часто используем индикаторы выполнения, чтобы пользователи знали, что что-то происходит. И если мы знаем некоторые детали, например, сколько работы было проделано и сколько еще осталось сделать, мы можем даже дать оценку времени, часто путем экстраполяции того, сколько времени понадобилось, чтобы добраться до текущего уровня прогресса.
http://jameslao.com/wp-content/uploads/2008/01/winrar-progress-bar.png
Но мы также видели программы, которые на этом оставленном "ETA" дисплее времени оставляют просто комично. Он утверждает, что копирование файла будет сделано через 20 секунд, затем через одну секунду он говорит, что это займет 4 дня, а затем снова мигает, чтобы быть 20 минут. Это не только бесполезно, но и сбивает с толку! Причина, по которой ETA варьируется так сильно, заключается в том, что сам уровень прогресса может меняться, а математика программиста может быть слишком чувствительной.
Apple обходит это, просто избегая любых точных прогнозов и просто давая неопределенные оценки! http://download.autodesk.com/esd/mudbox/help2009/images/MED/DaliSP1/English/Install_licensing/install_progress_MAC.png
Это тоже раздражает, у меня есть время для быстрого перерыва, или моя задача будет выполнена еще через 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 часа? Какая-то искусственная фильтрация типа "если моя новая оценка слишком сильно отличается от предыдущей оценки, уменьшите ее, не дайте ей слишком сильно отскочить"? Какой-то необычный анализ истории, в котором вы интегрируете прогресс и прогресс по времени, чтобы найти стандартное отклонение скорости, чтобы получить статистические показатели ошибок по завершении?
Что вы пробовали и что работает лучше всего?
11 ответов
Оригинальный ответ
Компания, которая создала этот сайт, по- видимому, создает систему планирования, которая отвечает на этот вопрос в контексте написания кода сотрудниками. Как это работает, так это симуляция будущего Монте-Карло, основанная на прошлом.
Приложение: объяснение Монте-Карло
Вот как этот алгоритм будет работать в вашей ситуации:
Вы моделируете свою задачу как последовательность микрозадач, скажем, 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%, но я, вероятно, пропустил некоторый постоянный коэффициент), все закончится.
Вот то, что я нашел, работает хорошо! Для первых 50% задания вы предполагаете, что показатель постоянен, и экстраполируете. Прогноз времени очень стабильный и не сильно подпрыгивает.
Как только вы пройдете 50%, вы переключите вычислительную стратегию. Вы берете часть оставшейся работы (1-p), затем оглядываетесь назад во времени в истории своего собственного прогресса и находите (с помощью бинарного поиска и линейной интерполяции), сколько времени вам потребовалось, чтобы выполнить последнее (1 -p) процент и использовать это как ваше время оценки завершения.
Так что, если вы сделали 71%, у вас осталось 29%. Вы оглядываетесь назад в своей истории и обнаруживаете, как давно вы были (71-29=42%) завершения. Сообщите это время как ваше ETA.
Это естественно адаптивно. Если у вас есть Х объем работы, он выглядит только в то время, которое потребовалось для выполнения Х объема работы. В конце, когда вы закончите на 99%, он использует только очень свежие, самые последние данные для оценки.
Конечно, он не идеален, но плавно меняется и особенно точен в самом конце, когда он наиболее полезен.
Хотя все примеры верны, для конкретного случая "оставшегося времени для загрузки" я подумал, что было бы неплохо взглянуть на существующие проекты с открытым исходным кодом, чтобы увидеть, что они делают.
Из того, что я вижу, Mozilla Firefox является лучшим в оценке оставшегося времени.
Mozilla Firefox
Firefox отслеживает последнюю оценку оставшегося времени и, используя эту и текущую оценку оставшегося времени, выполняет функцию сглаживания времени. Смотрите код ETA здесь. При этом используется "скорость", которая здесь предварительно рассчитана и является сглаженным средним значением последних 10 показаний.
Это немного сложно, поэтому перефразирую:
- Возьмите сглаженное среднее значение скорости на основе 90% от предыдущей скорости и 10% от новой скорости.
- При такой сглаженной средней скорости отработайте расчетное оставшееся время.
- Используйте это расчетное оставшееся время и предыдущее расчетное время, оставшееся до создания нового расчетного оставшегося времени (чтобы избежать прыжков)
Гугл Хром
Chrome, кажется, прыгает повсюду, и код показывает это.
Что мне нравится в Chrome, так это то, как они форматируют оставшееся время. В течение> 1 часа он говорит: "осталось 1 час". В течение< 1 часа - "осталось 59 минут". В течение < 1 минуты - "осталось 52 секунды".
Вы можете увидеть, как это отформатировано здесь
DownThemAll!Менеджер
Он не использует ничего умного, то есть ETA прыгает повсюду.
Смотрите код здесь
pySmartDL (загрузчик Python)
Принимает среднее ETA из последних 30 расчетов ETA. Похоже, разумный способ сделать это.
Смотрите код здесь/blob/916f2592db326241a2bf4d8f2e0719c58b71e385/pySmartDL/pySmartDL.py#L651)
коробка передач
Дает довольно хорошее ETA в большинстве случаев (кроме как при запуске, как и следовало ожидать).
Использует коэффициент сглаживания за последние 5 чтений, похожий на Firefox, но не такой сложный. Принципиально похоже на ответ Гули.
Смотрите код здесь
Я обычно использую экспоненциальную скользящую среднюю для вычисления скорости операции с коэффициентом сглаживания, скажем, 0,1, и использую ее для вычисления оставшегося времени. Таким образом, все измеренные скорости влияют на текущую скорость, но недавние измерения имеют гораздо больший эффект, чем в далеком прошлом.
В коде это будет выглядеть примерно так:
alpha = 0.1 # smoothing factor
...
speed = (speed * (1 - alpha)) + (currentSpeed * alpha)
Если ваши задачи одинаковы по размеру, currentSpeed будет просто время, необходимое для выполнения последней задачи. Если задачи имеют разные размеры, и вы знаете, что одна задача должна быть i, e, вдвое длиннее другой, вы можете разделить время, необходимое для выполнения задачи, на ее относительный размер, чтобы получить текущую скорость. С помощью speed Вы можете вычислить оставшееся время, умножив его на общий размер оставшихся задач (или просто на их количество, если задачи одинаковы).
Надеюсь, мои объяснения достаточно ясны, уже немного поздно.
Во-первых, это помогает генерировать скользящую среднюю. Это отягощает более свежие события последних лет.
Чтобы сделать это, держите кучу сэмплов (круговой буфер или список), каждая пара прогресса и времени. Сохраняйте последние 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;
}
В некоторых случаях, когда вам нужно выполнять одно и то же задание на регулярной основе, может быть хорошей идеей использовать прошедшее время завершения для усреднения.
Например, у меня есть приложение, которое загружает библиотеку iTunes через интерфейс COM. Размер данной библиотеки iTunes, как правило, резко не увеличивается от запуска к запуску с точки зрения количества элементов, поэтому в этом примере может быть возможным отследить последние три времени загрузки и скорости загрузки, а затем усреднить их и вычислить текущее время ETA.
Это было бы гораздо более точным, чем мгновенное измерение, и, вероятно, также более последовательным.
Однако этот метод зависит от того, насколько размер задачи относительно схож с предыдущими, поэтому он не будет работать для метода декомпрессии или чего-то еще, где любой данный поток байтов является данными, которые должны быть обработаны.
Просто мои $0,02
Равномерное усреднение
Простейший подход заключается в линейном прогнозировании оставшегося времени:
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. Сам С. Уорли предложил аналогичную модификацию предложения Гооли, хотя и применил его к неправильному термину. Экспоненциальное среднее для эквидистантных измерений:
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. Другими словами, эта константа определяет ширину окна сглаживания в области прогресса, а не во временной области. Поэтому этот метод не зависит от масштаба времени и имеет постоянное пространственное разрешение.
Дальнейшие исследования: адаптивное экспоненциальное сглаживание
Теперь вы можете попробовать различные алгоритмы адаптивного экспоненциального сглаживания. Только не забудьте применить это к медлительности, а не оценивать.
Ваш вопрос хороший. Если проблема может быть разбита на отдельные единицы, точный расчет часто работает лучше всего. К сожалению, это может быть не так, даже если вы устанавливаете 50 компонентов, каждый из которых может быть 2%, но один из них может быть массивным. Одна вещь, с которой я добился умеренного успеха, - это синхронизировать процессор и диск и дать достойную оценку на основе данных наблюдений. Знание того, что определенные контрольные точки действительно являются точкой x, дает вам некоторую возможность скорректировать факторы среды (сеть, активность диска, нагрузка на процессор). Однако это решение не носит общего характера из-за его зависимости от данных наблюдений. Использование вспомогательных данных, таких как размер файла rpm, помогло мне сделать мои индикаторы выполнения более точными, но они никогда не являются пуленепробиваемыми.
Я всегда хотел бы, чтобы эти вещи говорили мне диапазон. Если он сказал: "Скорее всего, эта задача будет выполнена за 8–30 минут", тогда у меня есть представление о том, какой перерыв сделать. Если он подпрыгивает повсюду, я испытываю желание наблюдать за ним, пока он не успокоится, что является большой тратой времени.
Я попробовал и упростил вашу формулу "легко"/"неправильно"/"ОК", и она лучше всего работает для меня:
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%.
Я не переживаю, это очень маленькая часть приложения. Я говорю им, что происходит, и позволяю им делать что-то еще.