如何在一系列排序的日期中找到缺失的日期？

Question

在Python中，我怎么才能找到一个已排序的日期列表中所有缺失的日期呢？

Answer 1

>>> from datetime import datetime, timedelta
>>> date_list = [datetime(2010, 2, 23),datetime(2010, 2, 24),datetime(2010, 2, 25),datetime(2010, 2, 26),datetime(2010, 3, 1),datetime(2010, 3, 2)]
>>> 
>>> date_set=set(date_list)         # for faster membership tests than list
>>> one_day = timedelta(days=1)
>>> 
>>> test_date = date_list[0]
>>> missing_dates=[]
>>> while test_date < date_list[-1]:
...     if test_date not in date_set:
...         missing_dates.append(test_date)
...     test_date += one_day
... 
>>> print missing_dates
[datetime.datetime(2010, 2, 27, 0, 0), datetime.datetime(2010, 2, 28, 0, 0)]

这段话的意思是，这种方法也适用于 datetime.date 对象，但提问者说他们的列表里是 datetime.datetime 对象。

Answer 2

先把日期列表排序，然后逐个查看每个日期，同时记住前一个日期。如果前一个日期和当前日期之间的差距超过一天，那就说明中间有缺失的日期。

下面是一种实现方法：

from datetime import date, timedelta
from itertools import tee, izip

def pairwise(iterable):
    "s -> (s0,s1), (s1,s2), (s2, s3), ..."
    a, b = tee(iterable)
    b.next()
    return izip(a, b)

def missing_dates(dates):
    for prev, curr in pairwise(sorted(dates)):
        i = prev
        while i + timedelta(1) < curr:
            i += timedelta(1)
            yield i

dates = [ date(2010, 1, 8),
          date(2010, 1, 2),
          date(2010, 1, 5),
          date(2010, 1, 1),
          date(2010, 1, 7) ]

for missing in missing_dates(dates):
    print missing

输出结果：

2010-01-03
2010-01-04
2010-01-06

这个方法的性能是 O(n*log(n))，其中 n 是输入中日期的数量，适用于未排序的情况。但因为你的列表已经排好序了，所以实际运行的时间是 O(n)。

Answer 3

使用集合

>>> from datetime import date, timedelta
>>> d = [date(2010, 2, 23), date(2010, 2, 24), date(2010, 2, 25),
         date(2010, 2, 26), date(2010, 3, 1), date(2010, 3, 2)]
>>> date_set = set(d[0] + timedelta(x) for x in range((d[-1] - d[0]).days))
>>> missing = sorted(date_set - set(d))
>>> missing
[datetime.date(2010, 2, 27), datetime.date(2010, 2, 28)]
>>>