Fastest way to check a List<T> for a date

Question

I have a list of dates that a machine has worked on, but it doesn't include a date that machine was down. I need to create a list of days worked and not worked. I am not sure of the best way to do this. I have started by incrementing through all the days of a range and checking to see if the date is in the list by iterating through the entire list each time. I am looking for a more efficient means of finding the dates.

class machineday
{
 datetime WorkingDay;
}

class machinedaycollection : List<machineday>
{
public List<TimeCatEvent> GetAllByCat(string cat)
{
  _CategoryCode = cat;


  List<machineday> li = this.FindAll(delegate(machinedaydummy) { return true; });
  li.Sort(sortDate);
  return li;
}

int sortDate(machinedayevent1, machinedayevent2)
{
  int returnValue = -1;
  if (event2.date < event1.date)
  {
    returnValue = 0;
  }
  else if (event2.date == event1.date)
  {
    //descending
    returnValue = event1.date.CompareTo(event2.date);
  }
  return returnValue;
}
}

Answer 1

Build a list of valid dates and subtract your machine day collection from it using LINQ's Enumerable.Except extension method. Something like this:

IEnumerable<DateTime> dates = get_candidate_dates();
var holidays = dates.Except(machinedays.Select(m => m.WorkingDay));

The get_candidate_dates() method could even be an iterator that generates all dates within a range on the fly, rather than a pre-stored list of all dates.

Enumerable's methods are reasonably smart and will usually do a decent job on the performance side of things, but if you want the fastest possible algorithm, it will depend on how you plan to consume the result.

Answer 2

Sort the dates and iterate the resulting list in parallel to incrementing a counter. Whenever the counter does not match the current list element, you've found a date missing in the list.

List<DateTime> days = ...;
days.Sort();
DateTime dt = days[0].Date;
for (int i = 0; i < days.Length; dt = dt.AddDays(1))
{
    if (dt == days[i].Date)
    {
        Console.WriteLine("Worked: {0}", dt);
        i++;
    }
    else
    {
        Console.WriteLine("Not Worked: {0}", dt);
    }
}

(This assumes there are no duplicate days in the list.)

Answer 3

Assuming the list is sorted and the machine was "working" most of the time, you may be able to avoid iterating through all the dates by grouping the dates by month and skipping the dates in between. Something like this (you'll need to clean up):

int chunksize = 60; // adjust depending on data
machineday currentDay = myMachinedaycollection[0];

for (int i = 0; i < myMachinedaycollection.Count; i += chunksize)  
{  
    if (currentDay.WorkingDay.AddDays(chunksize) != myMachinedaycollection[i + chunksize].WorkingDay)  
    {
        // write code to iterate through current chunk and get all the non-working days  
    }
    currentDay = myMachinedaycollection[i + chunksize];  
}  

Answer 4

Sorry dudes, but I do not pretty much like your solutions. I think you should create a HashTable with your dates. You can do this by interating only once the working days.

Then, you interate the full range of of days and for every one you query in the hashtable if the date is there or not, by using

myHashTable.ContainsKey(day); // this is efficient

Simple, elegant and fast.

I think your solution uses an exponencial time, this one is lineal or logarithmical (which is actually a good thing).

Answer 5

I doubt you want a list of days working and not working.

Your question title suggests that you want to know whether the system was up on a particular date. It also seems reasonable to calculate % uptime. Neither of these requires building a list of all time instants in the interval.

Sort the service times. For the first question, do BinarySearch for the date you care about and check whether the preceding entry was the system being taken offline of maintenance or put back into service. For % uptime, take the (down for maintenance, service restored) pair-wise, use subtraction to find the duration of maintenance, add these up. Then use subtraction to find the length of the total interval.

If your question didn't actually mean you were keeping track of maintenance intervals (or equivalently usage intervals) then you can ignore this answer.