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());


Your opinion

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

16 comments:

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

    How about this solution (I haven't tested it, so I'm not completely sure if it works):

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

    ReplyDelete
  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));
    }
    }

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

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

    ReplyDelete
  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.

    ReplyDelete
  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.

    ReplyDelete
  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)

    ReplyDelete
  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.

    ReplyDelete
  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?

    ReplyDelete
  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

    ReplyDelete
  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.

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

    Do you see something wrong Kristof?

    ReplyDelete
  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
    http://www.noveltheory.com/download/chronotest.cs.txt

    And the full project is at http://www.noveltheory.com/download/chronotest.zip

    ReplyDelete
  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; });
    }

    ReplyDelete
  15. Nice findings James. Thanks a lot.

    Your functional solution is very solid!

    ReplyDelete
  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();

    ReplyDelete