Calculate Time Remaining

What's a good algorithm for determining the remaining time for something to complete? I know how many total lines there are, and how many have completed already, how should I estimate the time remaining?

Why not?

(linesProcessed / TimeTaken) (timetaken / linesProcessed) * LinesLeft = TimeLeft

TimeLeft will then be expressed in whatever unit of time timeTaken is.

Edit:

Thanks for the comment you're right this should be:

(TimeTaken / linesProcessed) * linesLeft = timeLeft

so we have

(10 / 100) * 200 = 20 Seconds now 10 seconds go past
(20 / 100) * 200 = 40 Seconds left now 10 more seconds and we process 100 more lines
(30 / 200) * 100 = 15 Seconds and now we all see why the copy file dialog jumps from 3 hours to 30 minutes :-)

I'm surprised no one has answered this question with code!

The simple way to calculate time, as answered by @JoshBerke, can be coded as follows:

DateTime startTime = DateTime.Now;
for (int index = 0, count = lines.Count; index < count; index++) {
    // Do the processing
    ...

    // Calculate the time remaining:
    TimeSpan timeRemaining = TimeSpan.FromTicks(DateTime.Now.Subtract(startTime).Ticks * (count - (index+1)) / (index+1));

    // Display the progress to the user
    ...
}

This simple example works great for simple progress calculation.
However, for a more complicated task, there are many ways this calculation could be improved!

For example, when you're downloading a large file, the download speed could easily fluctuate. To calculate the most accurate "ETA", a good algorithm would be to only consider the past 10 seconds of progress. Check out http://github.com/scottrippey/Progression/blob/master/Progression/Extras/ETACalculator.cs">**ETACalculator.cs**</a> for an implementation of this algorithm!

ETACalculator.cs is from http://github.com/scottrippey/Progression"> Progression -- an open source library that I wrote. It defines a very easy-to-use structure for all kinds of "progress calculation". It makes it easy to have nested steps that report different types of progress. If you're concerned about Perceived Performance (as @JoshBerke suggested), it will help you immensely.

Make sure to manage perceived performance.

> Although all the progress bars took exactly the same amount of time in the test, two characteristics made users think the process was faster, even if it wasn't: > > 1. progress bars that moved smoothly towards completion > 2. progress bars that sped up towards the end

Not to revive a dead question but I kept coming back to reference this page.
You could create an extension method on the Stopwatch class to get functionality that would get an estimated remaining time span.

static class StopWatchUtils
{
    /// <summary>
    /// Gets estimated time on compleation. 
    /// </summary>
    /// <param name="sw"></param>
    /// <param name="counter"></param>
    /// <param name="counterGoal"></param>
    /// <returns></returns>
    public static TimeSpan GetEta(this Stopwatch sw, int counter, int counterGoal)
    {
        /* this is based off of:
         * (TimeTaken / linesProcessed) * linesLeft=timeLeft
         * so we have
         * (10/100) * 200 = 20 Seconds now 10 seconds go past
         * (20/100) * 200 = 40 Seconds left now 10 more seconds and we process 100 more lines
         * (30/200) * 100 = 15 Seconds and now we all see why the copy file dialog jumps from 3 hours to 30 minutes :-)
         * 
         * pulled from http://stackoverflow.com/questions/473355/calculate-time-remaining/473369#473369
         */
        if (counter == 0) return TimeSpan.Zero;
        float elapsedMin = ((float)sw.ElapsedMilliseconds / 1000) / 60;
        float minLeft = (elapsedMin / counter) * (counterGoal - counter); //see comment a
        TimeSpan ret = TimeSpan.FromMinutes(minLeft);
        return ret;
    }
}

Example:

int y = 500;
Stopwatch sw = new Stopwatch();
sw.Start();
for(int x = 0 ; x < y ; x++ )
{
    //do something
    Console.WriteLine("{0} time remaining",sw.GetEta(x,y).ToString());
}

Hopefully it will be of some use to somebody.

EDIT: It should be noted this is most accurate when each loop takes the same amount of time.
Edit 2: Instead of subclassing I created an extension method.

Generally, you know three things at any point in time while processing:

1. How many units/chunks/items have been processed up to that point in time (A).
2. How long it has taken to process those items (B).
3. The number of remaining items (C).

Given those items, the estimate (unless the time to process an item is constant) of the remaining time will be

B * C / A

I made this and it works quite good, feel free to change the method signature according to your variable types or also to the return type, probably you would like to get the TimeSpan object or just the seconds...

    /// <summary>
    /// Calculates the eta.
    /// </summary>
    /// <param name="processStarted">When the process started</param>
    /// <param name="totalElements">How many items are being processed</param>
    /// <param name="processedElements">How many items are done</param>
    /// <returns>A string representing the time left</returns>
    private string CalculateEta(DateTime processStarted, int totalElements, int processedElements)
    {
        int itemsPerSecond = processedElements / (int)(processStarted - DateTime.Now).TotalSeconds;
        int secondsRemaining = (totalElements - processedElements) / itemsPerSecond;

        return new TimeSpan(0, 0, secondsRemaining).ToString();
    }

You will require to initialize a DateTime variable when the processing starts and send it to the method on each iteration.

Do not forget that probably your window will be locked if the process is quite long, so when you place the return value into a control, don't forget to use the .Refresh() method of it.

If you are using threads then you can attempt to set the text using the Invoke(Action) method, would be easier to use this extension method to archieve it easily.

If you use a console application, then you should not have problems displaying the output line by line.

Hope it helps someone.

It depends greatly on what the "something" is. If you can assume that the amount of time to process each line is similar, you can do a simple calculation:

TimePerLine = Elapsed / LinesProcessed
TotalTime = TimePerLine * TotalLines
TimeRemaining = TotalTime - LinesRemaining * TimePerLine

there is no standard algorithm i know of, my sugestion would be:

• Create a variable to save the %
• Calculate the complexity of the task you wish to track(or an estimative of it)
• Put increments to the % from time to time as you would see fit given the complexity.

You probably seen programs where the load bar runs much faster in one point than in another. Well that's pretty much because this is how they do it. (though they probably just put increments at regular intervals in the main wrapper)

Where time$("ms") represents the current time in milliseconds since 00:00:00.00, and lof represents the total lines to process, and x represents the current line:

if Ln>0 then
    Tn=Tn+time$("ms")-Ln   'grand total of all laps
    Rn=Tn*(lof-x)/x^2      'estimated time remaining in seconds
end if
Ln=time$("ms")             'start lap time (current time)

That really depends on what is being done... lines are not enough unless each individual line takes the same amount of time.

The best way (if your lines are not similar) would probably be to look at logical sections of the code find out how long each section takes on average, then use those average timings to estimate progress.

If you know the percentage completed, and you can simply assume that the time scales linearly, something like

timeLeft = timeSoFar * (1/Percentage)

might work.

I already knew the percentage complete & time elapsed, so this helped me:

TimeElapsed * ((100 - %complete) / %complete) = TimeRemaining

I then updated this value every time %complete changed, giving me a constant varying ETA.

There is 2 ways of showing time

1. Time elapsed and Time Remaining overall: so elapsed will increase but remaining will be likely stable total time needed (if per second is stable)

2. Time elapsed and Time Left:
   so Time Left = Total Needed - Elapsed

My idea/formula is more likely like this:

Processed - updated from running thread from 0 to Total

I have timer with 1000ms interval that calculates processed per second:

processedPerSecond = Processed - lastTickProcessed;
lastTickProcessed = Processed;  //store state from past call

processedPerSecond and lastTickProcessed are global variables out of timer method

Now if we would like to get how many seconds is required to complete the processing (in ideal constant assumption) totalSecondsNeeded = TotalLines / PerSecond

but we want to show case 2. TimeLeft so TimeLeftSeconds = (TotalLines - Processed) / PerSecond

TimeSpan remaining = new TimeSpan(0, 0, (transactions.Count - Processed) / processedPerSecond);
labelTimeRemaining.Text = remaining.ToString(@"hh\:mm\:ss");

---

Of course TimeLeftSeconds will "jump" if PerSecond jumps, so if past PerSecond was 10 then 30 then back to 10, the user will see it.

There is a way to calculate average, but this may not show real time left if process speeds up at the end

int perSecond = (int)Math.Ceiling((processed / (decimal)timeElapsed.TotalSeconds));  //average not in past second

So it may be the choice for a developer to "pick" a method that will be most accurate based on prediction of how "jumpy" the processing is

We could also calculate and save each PerSecond, then take last 10 second and made average, but in this case user will have to wait 10 seconds to see first calculation or we could show time left starting from first per second and then progressively average summing up to 10 last PerSecond

I hope my "jumpy" thoughts will help someone to build something satisfying

How about this....

I used this to walk through a set of records (rows in an Excel file, in one case)

L is the current row number X is the total number of rows dat_Start is set to Now() when the routine begins

Debug.Print Format((L / X), "percent") & vbTab & "Time to go:" & vbTab & Format((DateDiff("n", dat_Start, Now) / L) * (X - L), "00") & ":" & Format(((DateDiff("s", dat_Start, Now) / L) * (X - L)) Mod 60, "00")

PowerShell function

function CalculateEta([datetime]$processStarted, [long]$totalElements, [long]$processedElements) {
    $itemsPerSecond = $processedElements / [DateTime]::Now.Subtract($processStarted).TotalSeconds
    $secondsRemaining = ($totalElements - $processedElements) / $itemsPerSecond

    return [TimeSpan]::FromSeconds($secondsRemaining)
}

I prefer System.Threading.Timer rather than System.Diagnostics.Stopwatch.

> System.Threading.Timer, which executes a single callback method on a > thread pool thread

The following code is an example of a calculating elapsed time with Threading.Timer.

public class ElapsedTimeCalculator : IDisposable
{
	private const int ValueToInstantFire = 0;

	private readonly Timer timer;
	private readonly DateTime initialTime;

	public ElapsedTimeCalculator(Action<TimeSpan> action)
	{
		timer = new Timer(new TimerCallback(_ => action(ElapsedTime)));
        initialTime = DateTime.UtcNow;
	}

    // Use Timeout.Infinite if you don't want to set period time.
	public void Fire() => timer.Change(ValueToInstantFire, Timeout.Infinite);

	public void Dispose() => timer?.Dispose();

	private TimeSpan ElapsedTime => DateTime.UtcNow - initialTime;
}

BTW You can use System.Reactive.Concurrency.IScheduler (scheduler.Now.UtcDateTime) instead of using DateTime directly, if you would like to mock and virtualize the datetime for unit tests.

public class PercentageViewModel : IDisposable
{
    private readonly ElapsedTimeCalculator elapsedTimeCalculator;

    public PercentageViewModel()
    {
       elapsedTimeCalculator = new ElapsedTimeCalculator(CalculateTimeRemaining))
    }

    // Use it where You would like to estimate time remaining.
    public void UpdatePercentage(double percent)
	{
        Percent = percent;
        elapsedTimeCalculator.Fire();
	}

	private void CalculateTimeRemaining(TimeSpan timeElapsed)
	{
		var timeRemainingInSecond = GetTimePerPercentage(timeElapsed.TotalSeconds) * GetRemainingPercentage;

        //Work with calculated time...	
	}

    public double Percent { get; set; }

	public void Dispose() => elapsedTimeCalculator.Dispose();

	private double GetTimePerPercentage(double elapsedTime) => elapsedTime / Percent;

	private double GetRemainingPercentage => 100 - Percent; 
}

In Python:

First create a array with the time taken per entry, then calculate the remaining elements and calculate average time taken

import datetime from datetime
import time

# create average function**
def average(total):
	return float(sum(total)) / max(len(total), 1)

# create array
time_elapsed = []

# capture starting time
start_time = datetime.now()

# do stuff

# capture ending time
end_time = datetime.now()

# get the total seconds from the captured time (important between two days)
time_in_seconds = (end_time - start_time).total_seconds()

# append the time to a array
time_elapsed.append(time_in_seconds)

# calculate the remaining elements, then multiply it with the average time taken
est_time_left = (LastElement - Processed) * average(time_elapsed)

print(f"Estimated time left: {time.strftime('%H:%M:%S', time.gmtime(est_time_left))}")

** timeit() with k=5000 random elements and number=1000

def average2(total):
	avg = 0
	for e in total:	avg += e
	return avg / max(len(total),1)

>> timeit average          0.014467999999999925
>> timeit average2         0.08711790000000003
>> timeit numpy.mean:      0.16030989999999967
>> timeit numpy.average:   0.16210096000000003
>> timeit statistics.mean: 2.8182458