检查 List<T> 中是否存在日期的最快方法

Question

我有一份机器工作日期的清单，但它没有包括机器停机的日期。我需要创建一个工作和未工作日期的列表。我不确定最好的方法是什么。我已经开始通过递增整个日期范围内的所有天数，并检查日期是否在列表中来迭代地遍历整个列表。我正在寻找一种更有效的查找日期的方法。

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

- fishhead

Answer 1

将日期排序，同时迭代结果列表并递增计数器。每当计数器与当前列表元素不匹配时，您就会发现列表中缺少一个日期。

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

（假设列表中没有重复的日期。）

- dtb

---

这不是一个好的解决方案，因为它需要15行代码才能实现1或2行就能完成的任务。看看Marcelo Cantos提出的基于集合的解决方案。虽然except方法可能在你的.net版本中不可用，但你可以以可重用的方式自己编写它。 - usr

@usr：你看过标签了吗？这是在.NET 2.0中实际可行的唯一解决方案。 - Aaronaught

Answer 2

使用LINQ的Enumerable.Except扩展方法，建立一个有效日期列表，并从中减去您的机器天收集。就像这样：

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

get_candidate_dates() 方法甚至可以是一个迭代器，实时生成范围内的所有日期，而不是预先存储所有日期的列表。

Enumerable 的方法通常比较智能，在性能方面通常会表现良好，但如果你想要最快的算法，那么它将取决于你计划如何消费结果。

- Marcelo Cantos

---

LINQ是这个问题的选择吗？ - slugster

也许不是（我刚刚注意到 .Net 2 标签），但是 Enumerable 可以从 .Net 2.0 中访问，虽然语法比较繁琐。您只需要添加对 System.Core 程序集的引用即可。 - Marcelo Cantos

Answer 3

抱歉，但我不太喜欢你们的解决方案。

我认为你们应该使用HashTable来存储日期。你只需要遍历一次工作日即可创建它。

然后，你可以遍历所有日期，并对每个日期在HashTable中查询是否存在，使用：

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

简单、优雅、快速。

我认为你的解决方案使用了指数级时间，而这个解决方案是线性或对数级的（实际上这是一件好事）。

- Daniel Dolz

---

常数时间和内存，但内存常数非常巨大，这是非常糟糕的事情。 - Ben Voigt

@Ben：不一定，这取决于性能是否更为关键。更好的性能通常是以某些其他资源（例如内存）为代价的。 - Kevin Brock

有趣，我从未想过那个方向。 - fishhead

巨大？保守地使用约1MB的内存，便可存储45年的日期。 在处理简单数据类型时，内存通常不再是问题。这在15年前是不同的，还记得那些只有640K内存的日子吗？ - Daniel Dolz

问题是在设置哈希数据结构所需的时间与搜索次数之间如何平衡。仅列出状态在“服务中”和“维护中”之间更改的日期的排序稠密结构将使用二分搜索非常快速。 - Ben Voigt

我认为对于大型集合，哈希搜索比二分搜索更高效。 - Daniel Dolz

Answer 4

假设列表已排序并且机器大部分时间都在“工作”，您可以通过按月份分组日期并跳过中间的日期来避免迭代所有日期。类似这样（您需要清理）：

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

- Zach Smith

Answer 5

我怀疑你是否想要一个工作日和非工作日列表。

根据你的问题标题，似乎你想知道系统在特定日期是否正常运行。另外，计算正常运行时间的百分比也是合理的。这两个问题都不需要构建一个包含所有时间点的列表。

对服务时间进行排序。对于第一个问题，使用二分搜索找到你关心的日期，并检查前一个条目是系统维护还是恢复运行。对于正常运行时间的百分比，将（维护中断、服务恢复）成对地进行运算，通过减法计算出维护时间的持续时间，并将它们相加。然后使用减法计算出总时间段的长度。

如果你的问题实际上并不意味着你正在跟踪维护间隔（或者等效的使用间隔），那么你可以忽略这个答案。

- Ben Voigt