高效的日期范围重叠计算？

Question

我有两个日期范围，每个范围都有一个开始日期和一个结束日期（当然，这些都是datetime.date类型的实例）。这两个范围可能会重叠，也可能不会。我需要计算重叠的天数。当然，我可以先把两个范围内的所有日期放到两个集合里，然后找出它们的交集，但这样可能效率不高……除了用很长的if-elif语句来处理所有情况，还有没有更好的方法呢？

Answer 1

我实现了一个叫做 TimeRange 的类，下面是它的代码。

get_overlapped_range 这个方法首先通过一个简单的条件来排除所有不重叠的选项，然后再考虑所有可能的选项来计算重叠的范围。

要计算天数，你需要拿到从 get_overlapped_range 返回的 TimeRange 值，然后把这个时间段的持续时间除以 60*60*24。

class TimeRange(object):
    def __init__(self, start, end):
        self.start = start
        self.end = end
        self.duration = self.end - self.start

    def is_overlapped(self, time_range):
        if max(self.start, time_range.start) < min(self.end, time_range.end):
            return True
        else:
            return False

    def get_overlapped_range(self, time_range):
        if not self.is_overlapped(time_range):
            return

        if time_range.start >= self.start:
            if self.end >= time_range.end:
                return TimeRange(time_range.start, time_range.end)
            else:
                return TimeRange(time_range.start, self.end)
        elif time_range.start < self.start:
            if time_range.end >= self.end:
                return TimeRange(self.start, self.end)
            else:
                return TimeRange(self.start, time_range.end)

    def __repr__(self):
        return '{0} ------> {1}'.format(*[time.strftime('%Y-%m-%d %H:%M:%S', time.localtime(d))
                                          for d in [self.start, self.end]])

Answer 2

函数调用的开销比算术运算要大。

最快的做法是用2次减法和1次min()函数：

min(r1.end - r2.start, r2.end - r1.start).days + 1

而下一个最好的方法需要1次减法、1次min()函数和1次max()函数：

(min(r1.end, r2.end) - max(r1.start, r2.start)).days + 1

当然，使用这两种表达式时，你仍然需要检查是否有正的重叠。

Answer 3

• 找出两个开始日期中较晚的一个，以及两个结束日期中较早的一个。
• 通过相减来计算时间差。
• 如果这个时间差是正数，那就是重叠的天数。

下面是一个计算的例子：

>>> from datetime import datetime
>>> from collections import namedtuple
>>> Range = namedtuple('Range', ['start', 'end'])

>>> r1 = Range(start=datetime(2012, 1, 15), end=datetime(2012, 5, 10))
>>> r2 = Range(start=datetime(2012, 3, 20), end=datetime(2012, 9, 15))
>>> latest_start = max(r1.start, r2.start)
>>> earliest_end = min(r1.end, r2.end)
>>> delta = (earliest_end - latest_start).days + 1
>>> overlap = max(0, delta)
>>> overlap
52