Самый быстрый способ проверить список <T>на дату - PullRequest
Новая
       40

Самый быстрый способ проверить список <T>на дату

4 голосов
/ 10 апреля 2010

У меня есть список дат, над которыми машина работала, но она не включает в себя дату, когда машина не работала. Мне нужно составить список дней, которые работали, а не работали. Я не уверен в лучшем способе сделать это. Я начал с увеличения всех дней диапазона и проверки наличия даты в списке, каждый раз просматривая весь список. Я ищу более эффективные средства поиска дат. 

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

Ответы [ 5 ]

6 голосов
/ 10 апреля 2010

Сортировка дат и повторение полученного списка параллельно с увеличением счетчика.Всякий раз, когда счетчик не соответствует текущему элементу списка, вы находите в списке отсутствующую дату. 

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

(Предполагается, что в списке нет повторяющихся дней.)

3 голосов
/ 10 апреля 2010

Извините, парни, но мне не очень нравятся ваши решения. Я думаю, что вы должны создать HashTable с вашими датами. Вы можете сделать это, взаимодействуя только один раз в рабочие дни.

Затем вы вводите полный диапазон дней и для каждого запроса в хеш-таблице, если дата есть или нет, с помощью 

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

Простой, элегантный и быстрый.

Я думаю, что ваше решение использует экспоненциальное время, это линейное или логарифмическое (что на самом деле хорошо).

3 голосов
/ 10 апреля 2010

Создайте список действительных дат и вычтите из него вашу коллекцию машинных дней, используя метод расширения Enumerable.Except LINQ. Как то так: 

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

Метод get_candidate_dates() может быть даже итератором, который генерирует все даты в диапазоне на лету, а не предварительно сохраненный список всех дат.

Методы Enumerable достаточно разумны и обычно хорошо справляются с работой, но если вам нужен самый быстрый алгоритм, это будет зависеть от того, как вы планируете использовать результат.

0 голосов
/ 10 апреля 2010

Я сомневаюсь, что вы хотите список рабочих и нерабочих дней.

Название вашего вопроса предполагает, что вы хотите знать, работала ли система в определенную дату. Также кажется разумным рассчитать% времени безотказной работы. Ни один из них не требует составления списка всех временных моментов в интервале.

Сортировать время обслуживания. По первому вопросу выполните BinarySearch на дату, о которой вы заботитесь, и проверьте, была ли предыдущая запись переведена в автономный режим или переведена в эксплуатацию. Для% безотказной работы возьмите попарно (вниз для обслуживания, восстановлено обслуживание), используйте вычитание, чтобы найти продолжительность обслуживания, сложите их. Затем используйте вычитание, чтобы найти длину общего интервала.

Если ваш вопрос на самом деле не означал, что вы отслеживали интервалы обслуживания (или эквивалентные интервалы использования), то вы можете проигнорировать этот ответ.

0 голосов
/ 10 апреля 2010

Предполагая, что список отсортирован и аппарат "работал" большую часть времени, вы можете избежать перебора всех дат, группируя даты по месяцам и пропуская даты между ними. Примерно так (нужно почистить): 

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];  
}
...