График интеллектуального прогресса ETA

Ответ 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%, но я, вероятно, пропустил какой-то постоянный фактор).

Ответ 2

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

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

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

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

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

Ответ 3

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

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

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

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

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

Ответ 4

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

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

Mozilla Firefox

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

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

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

Google Chrome

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

Одна вещь, которая мне нравится в Chrome, - это то, как они форматируют оставшееся время. В течение > 1 часа он говорит "1 час слева" Для < 1 час он говорит '59 минут слева ' Для < 1 минута говорит "52 секунды слева"

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

DownThemAll! Менеджер

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

Смотрите код здесь

pySmartDL (загрузчик питона)

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

Смотрите код здесь/blob/916f2592db326241a2bf4d8f2e0719c58b71e385/pySmartDL/pySmartDL.py#L651)

Передача

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

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

Смотрите код здесь

Ответ 5

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

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

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

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

Просто мои $0.02

Ответ 6

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

Чтобы сделать это, храните кучу образцов вокруг (круговой буфер или список), каждая пара прогресса и времени. Сохраняйте последние 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;
}    

Ответ 7

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

Ответ 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 раз. Сам С. Уорли предложил аналогичную модификацию предложения Гооли, хотя и применил его к неправильному термину. Экспоненциальное среднее для эквидистантных измерений:

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. Другими словами, эта константа определяет ширину окна сглаживания в области прогресса, а не во временной области. Следовательно, этот метод не зависит от масштаба времени и имеет постоянное пространственное разрешение.

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

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

Ответ 9

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

Ответ 10

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

t / p - t

В Python:

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

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

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

Ответ 11

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