将IList<DateTime>中连续的日期合并为范围

Question

1. 我有一系列带有“from”和“to”日期的对象。

2. 使用以下内容：

IList<DateTime> dates =
    this.DateRanges
        .SelectMany(r => new [] { r.From, r.To })
        .Distinct()
        .OrderBy(d => d)
        .ToList();

我可以获取所有日期，而且不会有任何重复的日期。范围可能完全重叠、部分重叠（上部或下部重叠）、触及或根本不重叠。

现在我需要将此列表转换为另一个列表，以便每个连续的日期对形成一个新生成的DateTime实例，该实例位于日期对中间。

D1      D2      D3              D4  D5
    G1      G2          G3        G4

如何将一组有序的日期转换为成对的日期，产生的日期对如下所示？我想使用 LINQ 来实现这个目标，而不是使用 for 循环。使用 LINQ 可能会导致更有效的代码，因为它支持延迟表达树执行。

D_n 是来自列表中不同的日期，而 G_m 日期是我想在这些日期之间生成的日期。

以下是一个真实世界例子：

D1             D2     D3     D4   D5     D6          D11    D12
|--------------|      |------|    |------|           |------|
       D7                         D8
       |--------------------------|
D9                                              D10
|-----------------------------------------------|

获取不同日期的第一步骤将会得到以下日期：

D1     D7      D2     D3     D4   D5     D6     D10  D11    D12

D9和D8会被删除，因为它们是重复的。

下一步是形成一对（我不知道如何使用LINQ完成此操作）：

D1-D7, D7-D2, D2-D3, D3-D4, D4-D5, D5-D6, D6-D10, (D10-D11), D11-D12

最后一步是使用以下公式为每对计算一个日期：

D_new = D_from + (D_to - D_from)/2

空范围问题

最好省略D₁₀-D₁₁范围，如果省略会导致代码过于复杂，则可以保留该范围并在之后进行单独检查排除。但是，如果在初始时可以排除它，那就应该这样做。因此，如果您提供了如何形成不包括空范围的一对配对的信息，也可以添加该信息。

- Robert Koritnik

---

挑剔一下：我会使用 ....ToList(); dates.Sort(); 而不是 ....OrderBy(d => d).ToList()。 - sehe

@Robert（带更正）你将如何处理断开的日期集？你的例子中有完全重叠的日期集。在D1和D10之间没有一个单独的日期没有被“覆盖”。尝试在D10右侧添加一个D11-D12，其中D11 > D10。 - xanatos

@xanatos：非常好的观点。我稍微修改了我的帖子。 - Robert Koritnik

@KirkBroadhurst，我显然没有表述好我的意思，因为那不是我想要的。我想从连续的项目中形成一对...计算中间值太简单了，不是吗？ - Robert Koritnik

@RobertKoritnik，你看到这里提出的一些问题了吗？;) 很抱歉我做了假设，我很乐意接受纠正。 - Kirk Broadhurst

Answer 1

您可以使用Zip()函数：

var middleDates = dates.Zip(dates.Skip(1), 
                            (a, b) => (a.AddTicks((b - a).Ticks / 2)))
                       .ToList();

- BrokenGlass

---

这非常聪明，正好符合我的需求。而且当不调用 ToList() 时，我可以延迟循环范围直到 Skip。这非常聪明。您能否也看一下不重叠范围的第一部分，因为最好排除空范围（在 D10 和 D11 之间）？ - Robert Koritnik

@RobertKoritnik：是的-您可以编写自定义扩展方法（或常规迭代代码），仅枚举一次-在这种情况下，Zip将始终枚举两次-我稍后可以尝试一下。此外，“空”日期范围确切指什么？ - BrokenGlass

糟糕，Zip仅适用于.NET 4+... 我需要在3.5中找到一些东西，所以我发现了有用的内容... - Robert Koritnik

@Robert 如果你真的需要 Zip，你可以查看 Mono 的源代码 :-) - xanatos

@xanatos 我直接在 .Net 中查看了它（使用 Reflector 等工具...）。但最终我使用了自己的解决方案，一次性完成所有操作。请查看 最终解决方案 的答案，并提出改进意见（如果有的话）。 - Robert Koritnik

@Robert，重要的一点是我向你指出了Mono而不是告诉你去反射.NET。你不能简单地从.NET复制代码，仅仅看它就会“污染”你的思维。查看Mono的源代码并复制其代码不会对你的代码产生太大影响（因为许可证非常宽松），也不会对你的思维产生太大影响。 - xanatos

Answer 2

最终解决方案

基于 @DavidB 的想法和 @AakashM 原始答案中的有趣想法，我提出了自己的解决方案，从一组日期中提取范围（同时省略空范围）并计算范围的中间日期。

如果您对此解决方案有任何改进建议或评论，欢迎在下面评论区留言。无论如何，这是我现在正在使用的最终代码（内联注释解释其功能）：

// counts range overlaps
int counter = 0;

// saves previous date to calculate midrange date
DateTime left = DateTime.Now;

// get mid range dates
IList<DateTime> dates = this.DateRanges

    // select range starts and ends
    .SelectMany(r => new[] {
        new {
            Date = r.From,
            Counter = 1
        },
        new {
            Date = r.To,
            Counter = -1
        }
    })

    // order dates because they come out mixed
    .OrderBy(o => o.Date)

    // convert dates to ranges; when non-empty & non-zero wide get mid date
    .Select(o => {

        // calculate middle date if range isn't empty and not zero wide
        DateTime? result = null;
        if ((counter != 0) && (left != o.Date))
        {
            result = o.Date.AddTicks(new DateTime((o.Date.Ticks - left.Ticks) / 2).Ticks);
        }

        // prepare for next date range
        left = o.Date;
        counter += o.Counter;

        // return middle date when applicable otherwise null
        return result;
    })

    // exclude empty and zero width ranges
    .Where(d => d.HasValue)

    // collect non nullable dates
    .Select(d => d.Value)
    .ToList();

- Robert Koritnik

---

@DavidB：谢谢。我已经用它轻松地排除了空范围，所以我一次性完成了所有操作。 - Robert Koritnik

Answer 3

下一步是形成一对（我不知道如何使用LINQ来完成这个）：

        List<DateTime> edges = bucketOfDates
            .Distinct()
            .OrderBy(date => date)
            .ToList();

        DateTime rangeStart = edges.First(); //ps - don't forget to handle empty
        List<DateRange> ranges = edges
            .Skip(1)
            .Select(rangeEnd =>
            {
              DateRange dr = new DateRange(rangeStart, rangeEnd);
              rangeStart = rangeEnd;
              return dr;
            })
            .ToList();

- Amy B

---

+1 这是一种很好的方式，可以将 LINQ 结合一些常规的 foreach 循环代码。但它非常简单，这很棒。感谢您的分享。也许我会采用不同的方法，将一些步骤组合在一起，使代码执行更快。 - Robert Koritnik

我添加了自己的答案，并使用了你的想法将一组日期合并成范围来解决问题。 - Robert Koritnik

Answer 4

好的，我的之前的想法行不通。但这个可以。而且它是基于输入数量的 O(n)。

为了解决 D10-D11 问题，我们需要让进程意识到在任何给定日期有多少原始区间处于“生效”状态。然后，我们可以按顺序迭代过渡点，并在我们处于两个过渡点之间并且当前状态为ON时发出中点。以下是完整代码。

数据类：

// The input type
class DateRange
{
    public DateTime From { get; set; }
    public DateTime To { get; set; }
}

// Captures details of a transition point
// along with how many ranges start and end at this point
class TransitionWithCounts
{
    public DateTime DateTime { get; set; }
    public int Starts { get; set; }
    public int Finishes { get; set; }
}

处理代码：

class Program
{
    static void Main(string[] args)
    {
        // Inputs as per question
        var d1 = new DateTime(2011, 1, 1);
        var d2 = new DateTime(2011, 3, 1);
        var d3 = new DateTime(2011, 4, 1);
        var d4 = new DateTime(2011, 5, 1);
        var d5 = new DateTime(2011, 6, 1);
        var d6 = new DateTime(2011, 7, 1);
        var d11 = new DateTime(2011, 9, 1);
        var d12 = new DateTime(2011, 10, 1);
        var d7 = new DateTime(2011, 2, 1);
        var d8 = d5;
        var d9 = d1;
        var d10 = new DateTime(2011, 8, 1);

        var input = new[]
        {
            new DateRange { From = d1, To = d2 },
            new DateRange { From = d3, To = d4 },
            new DateRange { From = d5, To = d6 },
            new DateRange { From = d11, To = d12 },
            new DateRange { From = d7, To = d8 },
            new DateRange { From = d9, To = d10 },
        };

第一步是捕获输入的起始和结束作为转换点。每个原始范围都变成了两个转换点，每个点的计数为1。

        // Transform into transition points
        var inputWithBeforeAfter = input.SelectMany(
            dateRange => new[]
                {
                    new TransitionWithCounts { DateTime = dateRange.From, Starts = 1 },
                    new TransitionWithCounts { DateTime = dateRange.To, Finishes = 1 }
                });

现在我们按日期分组，总结原始范围在该日期开始和结束的数量。

        // De-dupe by date, counting up how many starts and ends happen at each date
        var deduped = (from bdta in inputWithBeforeAfter
                      group bdta by bdta.DateTime
                      into g
                      orderby g.Key
                      select new TransitionWithCounts
                                 {
                                     DateTime = g.Key,
                                     Starts = g.Sum(bdta => bdta.Starts),
                                     Finishes = g.Sum(bdta => bdta.Finishes)
                                 }
                      );

为了处理这个问题，我们可以使用Aggregate（可能），但是对于我来说，手动迭代的阅读和编写速度更快：

        // Iterate manually since we want to keep a current count
        // and emit stuff
        var output = new List<DateTime>();
        var state = 0;
        TransitionWithCounts prev = null;

        foreach (var current in deduped)
        {
            // Coming to a new transition point
            // If we are ON, we need to emit a new midpoint
            if (state > 0)
            {
                // Emit new midpoint between prev and current
                output.Add(prev.DateTime.AddTicks((current.DateTime - prev.DateTime).Ticks / 2));
            }

            // Update state
            state -= current.Finishes;
            state += current.Starts;

            prev = current;
        }

我们可以在需要的时候断言 state == 0。

        // And we're done
        foreach (var dateTime in output)
        {
            Console.WriteLine(dateTime);
        }

        // 16/01/2011 12:00:00
        // 15/02/2011 00:00:00
        // 16/03/2011 12:00:00
        // 16/04/2011 00:00:00
        // 16/05/2011 12:00:00
        // 16/06/2011 00:00:00
        // 16/07/2011 12:00:00
        // 16/09/2011 00:00:00

        // Note: nothing around 15/08 as that is between D10 and D11,
        // the only midpoint where we are OFF

        Console.ReadKey();

- AakashM

---

这实际上与我的最终解决方案相似，但代码更少，基于我从阅读您的第一个答案中得到的左右布尔值的想法编写。让我把我的解决方案放在一个答案中。 - Robert Koritnik

实际上，我的最终解决方案使用了 @DavidB 的区间生成和计数器的想法，这与您的 Starts 和 Finishes 类似，但代码更简单。我没有像你那样对日期进行分组，因为没有必要，我只需要确保在非空且非零宽度的范围中计算中点。就是这样。我仍然给您 +1 的积极评价，感谢您在回答中付出的努力以及可行的解决方案。 - Robert Koritnik