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

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

compression ETA screenshot
(источник: jameslao.com)

Но мы также видели программы, которые на этот раз Левый дисплей "ETA" просто комично плох. Это утверждает, что копия файла будет сделана через 20 секунд, затем одну секунду спустя это говорит, что собирается занять 4 дня, затем это мерцает снова, чтобы быть 20 минутами. Это не только бесполезно, это сбивает с толку! Причина ETA варьируется, так много - то, что сам уровень прогресса может варьироваться, и математика программиста может быть чрезмерно чувствительной.

Apple обходит это, просто избежав любого точного прогноза и просто дав неопределенные оценки! Apple's vague evasion
(источник: autodesk.com)

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

Легкие но неправильные методы

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

Когда это происходит, можно думать для изменения вычисления для использования недавней скорости, не средней скорости, для оценки ETA. Вы берете средний уровень загрузки или степень выполнения за прошлые 10 секунд, и используете тот уровень для проекта, какой длины завершение будет. Это работает вполне хорошо в предыдущем overnight-download-which-sped-up-at-the-end примере, так как он даст очень хорошие оценки полного завершения в конце. Но это все еще имеет большие проблемы.. это заставляет Ваш ETA возвращаться дико, когда Ваш уровень варьируется быстро за короткий промежуток времени, и Вы становитесь "сделанными за 20 секунд, сделанных за 2 часа, сделанные за 2 секунды, сделанные за 30 минут" быстрый дисплей программирования позора.

Фактический вопрос:

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

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

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

72
задан Glorfindel 20 July 2019 в 08:08
поделиться

7 ответов

Исходный ответ

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

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

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

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

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

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

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

31
ответ дан 24 November 2019 в 12:45
поделиться

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

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

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

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

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

8
ответ дан 24 November 2019 в 12:45
поделиться

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

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

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

Однако этот метод зависит от размера задачи, будучи относительно аналогичным предыдущим,

3
ответ дан 24 November 2019 в 12:45
поделиться

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

2
ответ дан 24 November 2019 в 12:45
поделиться

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

0
ответ дан 24 November 2019 в 12:45
поделиться

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

-4
ответ дан 24 November 2019 в 12:45
поделиться

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

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

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

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

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

14
ответ дан 24 November 2019 в 12:45
поделиться
Другие вопросы по тегам:

Похожие вопросы: