LINQ Group по непрерывному времени

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, но избежать этого нельзя.Получив заказ, вы можете предотвратить материализацию ваших результатов перед их возвратом;вы просто yield получаете результаты, если диктуют условия.

Если вы знаете, что последовательность упорядочена, вам вообще не нужно вызывать 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() и лямбду, чтобы сгруппировать их вместе. Это, как вы говорите, при условии отсутствия дубликатов или совпадений:

// 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

Приведенный ниже код делает это в синтаксисе понимания запросов.

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 6

Следующее работает, но это действительно злоупотребление 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)

Обратите внимание:
Я бы придерживался итеративного решения, потому что приведенный выше код является нечитаемым , не поддерживаемым , и это заняло у значительно больше времени , чем просто ввод цикла и if. ..

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;