## Sunday, August 22, 2010

### Extension method: IEnumerable<DateTime?>.AreChronological()

In this post you can find an extension method which extends IEnumerable<DateTime?>. The AreChronological extension method tests if the items in the IEnumerable<DateTime?> are in chronological order.

There are multiple ways you can solve this problem.

Imperative solution

`   1:  public static class DateTimeExtensions`
`   2:  {     `
`   3:      public static bool AreChronological(this IEnumerable<DateTime?> dateTimes)`
`   4:      {`
`   5:          var prev = (DateTime?)DateTime.MinValue;`
`   6:   `
`   7:          foreach (var dateTime in dateTimes)`
`   8:          {`
`   9:              if (dateTime != null)`
`  10:              {`
`  11:                  if (prev > dateTime)`
`  12:                  {`
`  13:                      return false;`
`  14:                  }`
`  15:                  prev = dateTime;`
`  16:              }`
`  17:          }`
`  18:   `
`  19:          return true;`
`  20:      }`
`  21:  }`

Functional solution

After I finished the imperative solution, I asked Bart De Smet if he knew a sexier solution. He completely Linqified the solution and came up with this.

`   1:  public static bool AreChronological(this IEnumerable<DateTime?> dateTimes)`
`   2:  {`
`   3:      return dateTimes.Where(d => d != null)`
`   4:                      .Aggregate(new { c = (DateTime?)DateTime.MinValue, b = true },`
`   5:                                  (a, d) => new { c = d, b = a.b && a.c <= d }).b;`
`   6:  }`

Usage

You can use the extension method like this.

`   1:  DateTime?[] dateTimesChronological = new DateTime?[] { new DateTime(2010, 5, 15), `
`   2:                                                         null, `
`   3:                                                         new DateTime(2010, 6, 20) }; `
`   4:  DateTime?[] dateTimesNotChronological = new DateTime?[] { new DateTime(2010, 6, 20), `
`   5:                                                            null, `
`   6:                                                            new DateTime(2010, 5, 15) }; `
`   7:   `
`   8:  Console.WriteLine(dateTimesChronological.AreChronological());`
`   9:  Console.WriteLine(dateTimesNotChronological.AreChronological());`

Which solution do you like best? The imperative or the functional solution? Any ideas on how I could improve this code?

1. I like your imperative solution a lot more than the functional one because the functional one isn't really readable.

public static class DateTimeExtensions
{
public static bool AreChronological(this IEnumerable<DateTime?> dateTimes)
{
return dateTimes.SequenceEqual(dateTimes.OrderBy(d => d);
}
}

2. Ok, just tried it. It doens't work when there are null's in the list. This one works though:

public static class DateTimeExtensions
{
public static bool AreChronological(this IEnumerable<DateTime?> dateTimes)
{
var nonNull = dateTimes.Where(d => d.HasValue);
return nonNull.SequenceEqual(nonNull.OrderBy(d => d));
}
}

3. Solid solution, Kristof. I didn't even know the SequanceEqual method existed!

4. Also the imperative solution for me, thank's
Though Kristof's solution rocks also

5. I have just done some performance tests, and the imperative solution is a lot faster than the other two the functional one and the one I came up with.

I will post a follow up with some timing results.

6. Haha I intented on doing the same. You can e-mail me the results if you want. I'll make a follow-up post.

7. Kristof's solution has a problem that's not mentioned: Your Imperative method in O(N). His SequenceEqual method is O(N*N ln N), so for a simple 10 element array, time goes from O(10) to O(230)

8. Here's the test I have done:

Create three arrays with 500.000 dates each and 10% nulls. One array has the dates already in chronological order, one has them in reversed chronological order and one has them in a complete random order.

Here are the results from the Belgian vote :-)

Chronological:
- Imperative: 18ms
- Functional: 67ms
- SequenceEqual: 185ms

Reversed chronological:
- Imperative: 185ms
- Functional: 42ms
- SequenceEquals: 159ms

Random:
- Imperative: 159ms
- Functional: 41ms
- SequenceEquals: 277ms

So when they are already chronologically ordered, the imperative method is the fastest. When they are reversed or randomized, the functional one is faster.

9. Very interesting. So depending on the scenario and expected input you should pick a different solution.

If the arrays are smaller it probably makes no difference at all?

10. An array with 100 dates instead of 500.000 gives these results:

Chronological:
- Imperative: 1ms
- Functional: 7ms
- SequenceEqual: 6ms

Reversed chronological:
- Imperative: 6ms
- Functional: 0ms
- SequenceEquals: 0ms

Random:
- Imperative: 0ms
- Functional: 0ms
- SequenceEquals: 0ms

11. Something is wrong with your tests. Given a reverse chronologic list, the imperative method should be extremely fast --- it only has to look at two items to realize that it's not in order, and return false.

12. I think you are right James. I totally looked over that.

Do you see something wrong Kristof?

13. Ok, I've run my own tests. These seem to confirm what I'd assumed about them: Those using early-out are very fast, and the one using sorting is slowest.

Array of 500,000, repeated 10 times.

(I've also added my own take on a functional version, which takes advantage of early-out)

Full code given below.

Ordered:
00.5251852 : Imperative
01.9033203 : Bart's Functional
00.8058041 : My Functional
04.3834949 : SequentialEquals

Reversed:
00.0002125 : Imperative
00.6319280 : Bart's Functional
00.0002948 : My Functional
05.7310351 : SequentialEquals

Random:
00.0003984 : Imperative
01.2203456 : Bart's Functional
00.0002948 : My Functional
10.0460219 : SequentialEquals

(It's not letting me post the whole source code file here. I've uploaded it to

14. I guess I should post my functional method here:

public static bool AreChronological_Func2(this IEnumerable dateTimes)
{
var prev = DateTime.MinValue;
return dateTimes.Where(d => d != null)
.All(d => { var b = prev <= d.Value; prev = d.Value; return b; });
}

15. Nice findings James. Thanks a lot.

Your functional solution is very solid!

16. To take it to the next step, we can generalize it:

public static bool IsAscending<T>(this IEnumerable<T> coll)
where T: IComparable<T>
{
var prev = coll.First();
return coll.All(d =>
{
var b = prev.CompareTo(d) <= 0;
prev = d;
return b;
});
}
Note that I've removed the check for null, so to use this as I direct replacement for AreChronological, we'd need to do:

dateTimes.Where(d => d!=null)
.Select(d=> d.Value)
.IsAscending();