LINQ GroupBy 连续时间

Question

假设我有一个如下所示的简单结构：

public class Range
{
    public DateTime Start { get; set; }
    public DateTime End { get; set; }

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

我创建了一个像这样的集合：

var dr1 = new Range(new DateTime(2011, 11, 1, 12, 0, 0), 
    new DateTime(2011, 11, 1, 13, 0, 0));
var dr2 = new Range(new DateTime(2011, 11, 1, 13, 0, 0), 
    new DateTime(2011, 11, 1, 14, 0, 0));
var dr3 = new Range(new DateTime(2011, 11, 1, 14, 0, 0), 
    new DateTime(2011, 11, 1, 15, 0, 0));
var dr4 = new Range(new DateTime(2011, 11, 1, 16, 0, 0), 
    new DateTime(2011, 11, 1, 17, 0, 0));

var ranges = new List<Range>() { dr1, dr2, dr3, dr4 };

我想要做的是将连续的范围进行分组 - 即，如果前一个范围的结束值与下一个范围相同，则它们是连续的下一个开始。

我们可以假设范围值不存在冲突/重复或重叠。

在发布的示例中，我最终会得到两个组：

2011-11-1 12:00:00 - 2011-11-1 15:00:00

2011-11-1 16:00:00 - 2011-11-1 17:00:00

为此提出一个迭代解决方案相当容易。但是我可以使用一些 LINQ 魔法来以漂亮的单行代码实现这一点吗？

Answer 1

您最好的选择是使用 yield 和扩展方法：

static IEnumerable<Range> GroupContinuous(this IEnumerable<Range> ranges)
{
    // Validate parameters.

    // Can order by start date, no overlaps, no collisions
    ranges = ranges.OrderBy(r => r.Start);

    // Get the enumerator.
    using (IEnumerator<Range> enumerator = ranges.GetEnumerator();
    {
        // Move to the first item, if nothing, break.
        if (!enumerator.MoveNext()) yield break;

        // Set the previous range.
        Range previous = enumerator.Current;

        // Cycle while there are more items.
        while (enumerator.MoveNext())
        {
            // Get the current item.
            Range current = enumerator.Current;

            // If the start date is equal to the end date
            // then merge with the previous and continue.
            if (current.Start == previous.End)
            {
                // Merge.
                previous = new Range(previous.Start, current.End);

                // Continue.
                continue;
            }

            // Yield the previous item.
            yield return previous;

            // The previous item is the current item.
            previous = current;
        }

        // Yield the previous item.
        yield return previous;
    }
}

授予，对 OrderBy 的调用正在进行引起充分ranges 序列的迭代，但这是无法避免的。一旦您订购了它，您就可以避免在返回结果之前必须实现结果；如果条件允许，您只需产生结果即可。

但是，如果您知道序列是有序的，那么您根本不必调用 OrderBy，并且可以在遍历列表并中断时yield 项不同的折叠 Range 实例。

最终，如果序列是无序的，那么您有两个选择：

• 对列表进行排序，然后进行处理（请记住，OrderBy 也会延迟，但必须使用一次完整迭代来对序列进行排序），当您有一个要处理的项目时，使用 yield 返回该项目
• 立即处理整个序列并作为整个物化序列返回

Answer 2

casperOne 扩展方法的通用版本，如下使用：

var items = new[]
    {
        // Range 1
        new { A = 0, B = 1 },
        new { A = 1, B = 2 },
        new { A = 2, B = 3 },
        new { A = 3, B = 4 },
        // Range 2
        new { A = 5, B = 6 },
        new { A = 6, B = 7 },
        new { A = 7, B = 8 },
        new { A = 8, B = 9 },
    };

var ranges = items.ContinousRange(
    x => x.A,
    x => x.B,
    (lower, upper) => new { A = lower, B = upper });

foreach(var range in ranges)
{
    Console.WriteLine("{0} - {1}", range.A, range.B);
}

扩展方法的实现

    /// <summary>
    /// Calculates continues ranges based on individual elements lower and upper selections. Cannot compensate for overlapping.
    /// </summary>
    /// <typeparam name="T">The type containing a range</typeparam>
    /// <typeparam name="T1">The type of range values</typeparam>
    /// <param name="source">The ranges to be combined</param>
    /// <param name="lowerSelector">The range's lower bound</param>
    /// <param name="upperSelector">The range's upper bound</param>
    /// <param name="factory">A factory to create a new range</param>
    /// <returns>An enumeration of continuous ranges</returns>
    public static IEnumerable<T> ContinousRange<T, T1>(this IEnumerable<T> source, Func<T, T1> lowerSelector, Func<T, T1> upperSelector, Func<T1, T1, T> factory)
    {
        //Validate parameters

        // Can order by start date, no overlaps, no collisions
        source = source.OrderBy(lowerSelector);

        // Get enumerator
        using(var enumerator = source.GetEnumerator())
        {
            // Move to the first item, if nothing, break.
            if (!enumerator.MoveNext()) yield break;

            // Set the previous range.
            var previous = enumerator.Current;

            // Cycle while there are more items
            while(enumerator.MoveNext())
            {
                // Get the current item.
                var current = enumerator.Current;

                // If the start date is equal to the end date
                // then merge with the previoud and continue
                if (lowerSelector(current).Equals(upperSelector(previous)))
                {
                    // Merge
                    previous = factory(lowerSelector(previous), upperSelector(current));

                    // Continue
                    continue;
                }

                // Yield the previous item.
                yield return previous;

                // The previous item is the current item.
                previous = current;
            }

            // Yield the previous item.
            yield return previous;
        }
    }

Answer 3

您可以使用 Aggregate() 方法和 lambda 将它们组合在一起。正如您所说，假设没有重复或重叠：

// build your set of continuous ranges for results
List<Range> continuousRanges = new List<Range>();

ranges.Aggregate(continuousRanges, (con, next) => {
{
    // pull last item (or default if none) - O(1) for List<T>
    var last = continuousRanges.FirstOrDefault(r => r.End == next.Start);

    if (last != null)
        last.End = next.End;
    else
        con.Add(next);

    return con;
});   

现在，如果您知道范围是有序的，则可以始终将下一个与我们处理的最后一个进行比较，如下所示：

// build your set of continuous ranges for results
List<Range> continuousRanges = new List<Range>();

ranges.Aggregate(continuousRanges, (con, next) => {
{
    // pull last item (or default if none) - O(1) for List<T>
    var last = continuousRanges.LastOrDefault();

    if (last != null && last.End == next.Start)
        last.End = next.End;
    else
        con.Add(next);

    return con;
});   

Answer 4

这是另一个 LINQ 解决方案。它使用一个查询找到每个连续范围的开头，使用另一个查询找到每个连续范围的结尾，然后遍历这些对来构造新的范围。

var starts = ranges.Where((r, i) => i == 0 || r.Start != ranges[i - 1].End);
var ends = ranges.Where((r, i) => i == ranges.Count - 1 || r.End != ranges[i + 1].Start);
var result = starts.Zip(ends, (s, e) => new Range(s.Start, e.End));

它可以重写为一行代码，但单独的版本更清晰且更易于维护：

var result = ranges.Where((r, i) => i == 0 || r.Start != ranges[i - 1].End).Zip(ranges.Where((r, i) => i == ranges.Count - 1 || r.End != ranges[i + 1].Start), (s, e) => new Range(s.Start, e.End));

Answer 5

以下内容有效，但实际上是对 LINQ 的滥用：

// Dummy at the end to get the last continues range
ranges.Add(new Range(default(DateTime), default(DateTime)));
// The previous element in the list
Range previous = ranges.FirstOrDefault();
// The start element of the current continuous range
Range start = previous;
ranges.Skip(1).Select(x => {var result = new {current = x, previous = previous};
                            previous = x; return result;})
              .Where(x => x.previous.End != x.current.Start)
              .Select(x => { var result = new Range(start.Start, x.previous.End);
                             start = x.current; return result; });

该代码执行以下操作：

首先选择：

1. 将当前值和当前前一个值保存在新匿名类型的实例中
2. 将前一个值设置为下一次迭代的当前值

其中：仅选择那些标记新连续范围开始的元素

第二次选择：

1. 使用保存的开始值的开始日期和上一项的结束值创建一个 Range 对象。
2. 将起始值设置为当前项目，因为它标志着新的连续范围的开始。
3. 返回在(1)中创建的范围

请注意：
我会坚持使用迭代解决方案，因为上面的代码不可读，不可维护，并且它比仅仅输入一个循环花费了我更多的时间一个如果...

Answer 6

下面的代码以查询理解语法执行此操作。

public static List<Range> Group(List<Range> dates){
    if(dates.Any()){
        var previous = dates.FirstOrDefault();
        previous = new Range(previous.Start,previous.Start);
        var last = dates.Last();
        var result = (from dt in dates
                     let isDone = dt.Start != previous.End
                     let prev = isDone || last == dt ? 
                                                previous :  
                                               (previous = new Range(previous.Start,dt.End))
                     where isDone || last == dt
                     let t = (previous = dt)
                     select prev).ToList();
        if(result.Last().End != last.End)
           result.Add(last);
        return result;
    }
    return Enumerable.Empty<Range>().ToList();
}

我认为我实际上不会在生产代码中执行此操作，因为我觉得它违反了最小惊喜规则。 linq 语句通常没有副作用，而这是有效的，因为它有副作用。然而我认为值得发帖来表明它确实可以使用 O(n) 中的查询理解语法来解决

Answer 7

        var ranges = new List<Range>() { dr1, dr2, dr3, dr4 };
        var starts = ranges.Select(p => p.Start);
        var ends = ranges.Select(p => p.End);
        var discreet = starts.Union(ends).Except(starts.Intersect(ends)).OrderBy(p => p).ToList();
        List<Range> result = new List<Range>();
        for (int i = 0; i < discreet.Count; i = i + 2)
        {
            result.Add(new Range(discreet[i], discreet[i + 1]));
        }
        return result;