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: }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?
I like your imperative solution a lot more than the functional one because the functional one isn't really readable.
ReplyDeleteHow 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);
}
}
Ok, just tried it. It doens't work when there are null's in the list. This one works though:
ReplyDeletepublic 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));
}
}
Solid solution, Kristof. I didn't even know the SequanceEqual method existed!
ReplyDeleteAlso the imperative solution for me, thank's
ReplyDeleteThough Kristof's solution rocks also
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.
ReplyDeleteI will post a follow up with some timing results.
Haha I intented on doing the same. You can e-mail me the results if you want. I'll make a follow-up post.
ReplyDeleteKristof'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)
ReplyDeleteHere's the test I have done:
ReplyDeleteCreate 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.
Very interesting. So depending on the scenario and expected input you should pick a different solution.
ReplyDeleteIf the arrays are smaller it probably makes no difference at all?
An array with 100 dates instead of 500.000 gives these results:
ReplyDeleteChronological:
- Imperative: 1ms
- Functional: 7ms
- SequenceEqual: 6ms
Reversed chronological:
- Imperative: 6ms
- Functional: 0ms
- SequenceEquals: 0ms
Random:
- Imperative: 0ms
- Functional: 0ms
- SequenceEquals: 0ms
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.
ReplyDeleteI think you are right James. I totally looked over that.
ReplyDeleteDo you see something wrong Kristof?
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.
ReplyDeleteArray 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
I guess I should post my functional method here:
ReplyDeletepublic 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; });
}
Nice findings James. Thanks a lot.
ReplyDeleteYour functional solution is very solid!
To take it to the next step, we can generalize it:
ReplyDeletepublic 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();