寻找最长的重叠周期

Question

我有一个包含 Id、DateFrom、DateTo 的记录列表。为了这个问题，我们可以使用这个：

    List<(int, DateTime, DateTime)> data = new List<(int, DateTime, DateTime)>
        {
            (1, new DateTime(2012, 5, 16), new DateTime(2018, 1, 25)),
            (2, new DateTime(2009, 1, 1), new DateTime(2011, 4, 27)),
            (3, new DateTime(2014, 1, 1), new DateTime(2016, 4, 27)),
            (4, new DateTime(2015, 1, 1), new DateTime(2015, 1, 3)),
            (2, new DateTime(2013, 5, 10), new DateTime(2017, 4, 27)),
            (5, new DateTime(2013, 5, 16), new DateTime(2018, 1, 24)),
            (2, new DateTime(2017, 4, 28), new DateTime(2018, 1, 24)),
        };

在我的真实案例中，列表可能要大得多。最初我假设某个 Id 只能有一个记录，我能够想出一个很好的解决方案，但现在，正如你所看到的，假设你可以有多个比较整个时间时，应考虑 Id 的周期和所有周期。

任务是找到重叠时间最长的两条记录，并returnids和重叠天数。

在这个示例案例中，这意味着这些应该是记录 1 和 2。

我的实现如下：

    public (int, int, int) GetLongestElapsedPeriodWithDuplications(List<(int, DateTime, DateTime)> periods)
    {
        Dictionary<int, List<(DateTime, DateTime)>> periodsByPeriodId = new Dictionary<int, List<(DateTime, DateTime)>>();

        foreach (var period in periods)
        {
            if (periodsByPeriodId.ContainsKey(period.Item1))
            {
                periodsByPeriodId[period.Item1].Add((period.Item2, period.Item3));
            }
            else
            {
                periodsByPeriodId[period.Item1] = new List<(DateTime, DateTime)>();
                periodsByPeriodId[period.Item1].Add((period.Item2, period.Item3));
            }
        }

        int firstId = -1;
        int secondId = -1;
        int periodInDays = 0;

        foreach (var period in periodsByPeriodId)
        {
            var Id = period.Key;

            foreach (var currPeriod in periodsByPeriodId)
            {
                int currentPeriodInDays = 0;
                if (Id != currPeriod.Key)
                {
                    for (var i = 0; i < period.Value.Count; i++)
                    {
                        for (var j = 0; j < currPeriod.Value.Count; j++)
                        {
                            var firstPeriodDateFrom = period.Value[i].Item1;
                            var firstPeriodDateTo = period.Value[i].Item2;

                            var secondPeriodDateFrom = currPeriod.Value[j].Item1;
                            var secondPeriodDateTo = currPeriod.Value[j].Item2;

                            if (secondPeriodDateFrom < firstPeriodDateTo && secondPeriodDateTo > firstPeriodDateFrom)
                            {
                                DateTime commonStartingDate = secondPeriodDateFrom > firstPeriodDateFrom ? secondPeriodDateFrom : firstPeriodDateFrom;
                                DateTime commonEndDate = secondPeriodDateTo > firstPeriodDateTo ? firstPeriodDateTo : secondPeriodDateTo;

                                currentPeriodInDays += (int)(commonEndDate - commonStartingDate).TotalDays;
                            }
                        }
                    }
                    if (currentPeriodInDays > periodInDays)
                    {
                        periodInDays = currentPeriodInDays;
                        firstId = Id;
                        secondId = currPeriod.Key;
                    }
                }
            }
        }
        return (firstId, secondId, periodInDays);
    }

如您所见，该方法非常庞大，在我看来，在执行速度方面远未得到优化。我知道那些嵌套循环会大大增加复杂性，但是处理 Id 多个周期的这一额外要求确实让我没有想法。我如何优化这个逻辑，以便在输入更大的情况下执行得比现在更快？

Answer 1

这里的基本问题是如何识别一组唯一的时间段。自己给每个人自己唯一的 ID。

当您写下最终答案时，请在输出中包含其他详细信息，以便用户可以了解哪些（原始）ID 和原始时间段产生了最终答案。

请记住 - 问题仍然与原始 post (https://codereview.stackexchange.com/questions/186014/finding-the-longest-overlapping-period/186031?noredirect=1#comment354707_186031) 中的问题相同，您仍然可以使用相同的信息。不要过于关注原始列表中提供的 "ID"s - 您仍在遍历时间段列表。

Answer 2

与您的原始解决方案一样 - 您需要将每个间隔与任何其他间隔进行比较，除了具有相同 ID 的间隔，所以我将这样编码：

支持类，只是为了简化实际算法：

class Period {
    public DateTime Start { get; }
    public DateTime End { get; }

    public Period(DateTime start, DateTime end) {
        this.Start = start;
        this.End = end;
    }

    public int Overlap(Period other) {
        DateTime a = this.Start > other.Start ? this.Start : other.Start;
        DateTime b = this.End < other.End ? this.End : other.End;
        return (a < b) ? b.Subtract(a).Days : 0;
    }
}

class IdData {
    public IdData() {
        this.Periods = new List<Period>();
        this.Overlaps = new Dictionary<int, int>();
    }
    public List<Period> Periods { get; }
    public Dictionary<int, int> Overlaps { get; }
}

寻找最大重叠的方法：

    static int GetLongestElapsedPeriod(List<(int, DateTime, DateTime)> periods) {
        int maxOverlap = 0;

        Dictionary<int, IdData> ids = new Dictionary<int, IdData>();
        foreach (var period in periods) {
            int id = period.Item1;
            Period idPeriod = new Period(period.Item2, period.Item3);

            // preserve interval for ID
            var idData = ids.GetValueOrDefault(id, new IdData());
            idData.Periods.Add(idPeriod);
            ids[id] = idData;

            foreach (var idObj in ids) {
                if (idObj.Key != id) {
                    // here we calculate of new interval with all previously met
                    int o = idObj.Value.Overlaps.GetValueOrDefault(id, 0);
                    foreach (var otherPeriods in idObj.Value.Periods)
                        o += idPeriod.Overlap(otherPeriods);
                    idObj.Value.Overlaps[id] = o;

                    // check whether newly calculate overlapping is the maximal one, preserve Ids if needed too
                    if (o > maxOverlap)
                        maxOverlap = o;
                }
            }
        }

        return maxOverlap;
    }

Answer 3

使用扩展方法：

public static T MaxBy<T, TKey>(this IEnumerable<T> src, Func<T, TKey> key, Comparer<TKey> keyComparer = null) {
    keyComparer = keyComparer ?? Comparer<TKey>.Default;
    return src.Aggregate((a, b) => keyComparer.Compare(key(a), key(b)) > 0 ? a : b);
}

还有一些辅助函数

DateTime Max(DateTime a, DateTime b) => (a > b) ? a : b;
DateTime Min(DateTime a, DateTime b) => (a < b) ? a : b;

int OverlappingDays((DateTime DateFrom, DateTime DateTo) span1, (DateTime DateFrom, DateTime DateTo) span2) {
    var maxFrom = Max(span1.DateFrom, span2.DateFrom);
    var minTo = Min(span1.DateTo, span2.DateTo);
    return Math.Max((minTo - maxFrom).Days, 0);
}

您可以将具有匹配 Ids

的跨度组合在一起

var dg = data.GroupBy(d => d.Id);

生成所有 Ids

对

var pdgs = from d1 in dg
           from d2 in dg.Where(d => d.Key > d1.Key)
           select new[] { d1, d2 };

然后计算每对 Id 之间的重叠天数并找到最大值：

var MaxOverlappingPair = pdgs.Select(pdg => new {
    Id1 = pdg[0].Key,
    Id2 = pdg[1].Key,
    OverlapInDays = pdg[0].SelectMany(d1 => pdg[1].Select(d2 => OverlappingDays((d1.DateFrom, d1.DateTo), (d2.DateFrom, d2.DateTo)))).Sum()
}).MaxBy(TwoOverlap => TwoOverlap.OverlapInDays);

既然提到了效率，我应该说直接实现其中一些操作而不是使用 LINQ 效率更高，但是您使用的是元组和内存结构，所以我认为这不会有太大区别。

我运行使用包含 1249 个唯一 ID 的 24000 个跨度列表进行一些性能测试。 LINQ 代码用了大约 16 秒。通过内联一些 LINQ 并用元组替换匿名对象，它下降到大约 3.1 秒。通过添加一个快捷方式，跳过任何累计天数短于当前最大重叠天数的 ID，并进行一些优化，我将其缩短到不到 1 秒。

var baseDate = new DateTime(1970, 1, 1);

int OverlappingDays(int DaysFrom1, int DaysTo1, int DaysFrom2, int DaysTo2) {
    var maxFrom = DaysFrom1 > DaysFrom2 ? DaysFrom1 : DaysFrom2;
    var minTo = DaysTo1 < DaysTo2 ? DaysTo1 : DaysTo2;
    return (minTo > maxFrom) ? minTo - maxFrom : 0;
}

var dgs = data.Select(d => {
    var DaysFrom = (d.DateFrom - baseDate).Days;
    var DaysTo = (d.DateTo - baseDate).Days;
    return (d.Id, DaysFrom, DaysTo, Dist: DaysTo - DaysFrom);
})
              .GroupBy(d => d.Id)
              .Select(dg => (Id: dg.Key, Group: dg, Dist: dg.Sum(d => d.Dist)))
              .ToList();

var MaxOverlappingPair = (Id1: 0, Id2: 0, OverlapInDays: 0);

for (int j1 = 0; j1 < dgs.Count; ++j1) {
    var dg1 = dgs[j1];
    if (dg1.Dist > MaxOverlappingPair.OverlapInDays)
        for (int j2 = j1 + 1; j2 < dgs.Count; ++j2) {
            var dg2 = dgs[j2];
            if (dg2.Dist > MaxOverlappingPair.OverlapInDays) {
                var testOverlapInDays = 0;
                foreach (var d1 in dg1.Group)
                    foreach (var d2 in dg2.Group)
                        testOverlapInDays += OverlappingDays(d1.DaysFrom, d1.DaysTo, d2.DaysFrom, d2.DaysTo);

                if (testOverlapInDays > MaxOverlappingPair.OverlapInDays)
                    MaxOverlappingPair = (dg1.Id, dg2.Id, testOverlapInDays);
            }
        }
}

已应用优化：

将每个跨度 DateTimes 转换为 arbitrary baseDate 的天数，以通过进行一次日期转换来优化重叠天数计算。
计算每个跨度的总天数并跳过任何不能超过当前重叠的跨度对
将 SelectMany/Select 替换为嵌套 foreach 以计算重叠天数。
使用 ValueTuples 而不是匿名对象，匿名对象（稍微）更快地解决这个问题。
用直接生成每个可能对的嵌套 for 循环替换对生成 LINQ
将单个 from/to 参数而不是对象传递给 OverlappingDays 函数

注意：我尝试了一种更智能的重叠天数计算，但是当每个 ID 的跨度数较小时，开销比直接进行计算花费的时间更长。

Answer 4

您可以使用TimePeriodLibrary.NET:

PM> Install-Package TimePeriodLibrary.NET

TimePeriodCollection timePeriods = new TimePeriodCollection(
    data.Select(q => new TimeRange(q.Item2, q.Item3)));

var longestOverlap = timePeriods
    .OverlapPeriods(new TimeRange(timePeriods.Start, timePeriods.End))
    .OrderByDescending(q => q.Duration)
    .FirstOrDefault();

Answer 5

解决方案已经很少

但是

如果您想提高效率，则不必将每个 objects/value 与其他所有值或对象进行比较。您可以使用 Interval Search Tree 来解决这个问题，它可以在 RlogN 中解决，其中 R 是间隔之间的交点数。

我建议您观看 Robert Sedgwick 的这本 video 并且该书在线提供。

寻找最长的重叠周期

Finding the longest overlapping period

c#

algorithm

datetime

intervals