How to speed up this algorithm? [closed]

Question

Closed. This question needs to be more focused. It is not currently accepting answers.

---

Want to improve this question? Update the question so it focuses on one problem only by editing this post.

Closed 8 years ago.

Improve this question

This counting method is quite slow in one unit test. Can it be improved, perhaps by parallelisation?

Edit: To be clear, I can't change the calendar interface or the implementations. I'm interested in the counting algorithm.

public static int CountBusinessDays(ICalendar calendar, DateTime start, DateTime end)
{
    int nBusinessDays = 0;

    for (DateTime current = start; current <= end; current = current.AddDays(1))
    {
        if (calendar.IsBusinessDay(current))
            ++nBusinessDays;
    }

    return nBusinessDays;
}

public interface ICalendar
{
    bool IsBusinessDay(DateTime day);
}

Answer 1

So to start with here's a simple helper method to generate an infinite sequence of days starting at a given point:

public static IEnumerable<DateTime> Days(DateTime start)
{
    while (true)
    {
        yield return start;
        start = start.AddDays(1);
    }
}

We can then generate a sequence of days representing your range using TakeWhile:

var allDays = Days(start).TakeWhile(day => day <= end);

Next we can use PLINQ to parallelize the computation on each day:

return allDays.AsParallel()
    .Where(day => calendar.IsBusinessDay(day))
    .Count();

Note that the computation of whether a given date is a business day might not be particularly time consuming. If this is the case then it's quite possible that the overhead of managing all of the different threads actually takes more time than you gain from parallelizing the work. The size of the underlying collection also matters as well; if it's longer there's a greater chance of parallelization being worthwhile. You should run some tests to see if this is actually a win by adding/removing the AsParallel call.

Answer 2

If you cannot change the implementation, your only possible means of speeding things up is via parallelization (whether or not your handle your multiple threads via application code).

Since we don't know what takes place in calendar.IsBusinessDay(), we can't tell you whether it would be faster. Maybe you have implicit serialization, maybe you are resource starved, maybe it just breaks because it is not thread safe. If you don't know the answer, you have 4 options that I can think of. 1) Try parallelization and see if it works and is factor. 2) Modify or eliminate the test case to make it faster. 3) Throw more/faster hardware at it, 4) Live with it.