Объединить элементы в IEnumerable согласно условию

Question

Я искал какой-нибудь быстрый и эффективный способ объединения элементов в массиве.Это мой сценарий.Коллекция отсортирована по.Соседний элемент не обязательно отличается на 1, то есть могут быть промежутки между последним To и следующим From, но они никогда не перекрываются.

var list = new List<Range>();
list.Add(new Range() { From = 0, To = 1, Category = "AB" });
list.Add(new Range() { From = 2, To = 3, Category = "AB" });
list.Add(new Range() { From = 4, To = 5, Category = "AB" });
list.Add(new Range() { From = 6, To = 8, Category = "CD" });
list.Add(new Range() { From = 9, To = 11, Category = "AB" }); // 12 is missing, this is ok
list.Add(new Range() { From = 13, To = 15, Category = "AB" });

Я бы хотел, чтобы вышеуказанная коллекция была объединена таким образом, чтобы первые три элемента (это число могло варьироваться от как минимум 2 элементов до целого числа, удовлетворяющего условию) стали одним элементом.Невозможно объединить элементы с другой категорией.

new Range() { From = 0, To = 5, Category = "AB" };

Так что итоговая коллекция будет иметь всего 4 элемента.

0 - 5    AB
6 - 8    CD
9 - 11   AB // no merging here, 12 is missing
13 - 15  AB

У меня очень большая коллекция с более чем 2.000.000 предметовхотел бы, чтобы это было максимально эффективно.

Answer 1

Вот общее, многократно используемое решение, а не специальное, конкретное решение. (Обновлено на основе комментариев)

IEnumerable<T> Merge<T>(this IEnumerable<T> coll, 
                      Func<T,T,bool> canBeMerged, Func<T,T,T>mergeItems)
{
    using(IEnumerator<T> iter = col.GetEnumerator())
    {
      if (iter.MoveNext())
      {
          T lhs = iter.Current;
          while(iter.MoveNext())
          {
              T rhs = iter.Current;
              if (canBeMerged(lhs, rhs)
                 lhs=mergeItems(lhs, rhs);
              else
              {
                 yield return lhs;
                 lhs= rhs;
              }
          }
          yield return lhs;
      }
    }
}

Вы должны будете предоставить метод, чтобы определить, можно ли объединить элемент, и объединить их. Они действительно должны быть частью вашего класса Range, поэтому он будет называться так:

list.Merge((l,r)=> l.IsFollowedBy(r), (l,r)=> l.CombineWith(r));

Если у вас нет этих методов, вам придется вызывать их следующим образом:

list.Merge((l,r)=> l.Category==r.Category && l.To +1 == r.From,
           (l,r)=> new Range(){From = l.From, To=r.To, Category = l.Category});

Answer 2

Что ж, из постановки задачи я думаю, что очевидно, что вы не можете избежать перебора исходной коллекции из 2 миллионов элементов:

var output = new List<Range>();
var currentFrom = list[0].From;
var currentTo = list[0].To;
var currentCategory = list[0].Category;
for (int i = 1; i < list.Count; i++)
{
    var item = list[i];
    if (item.Category == currentCategory && item.From == currentTo + 1)
        currentTo = item.To;
    else
    {
        output.Add(new Range { From = currentFrom, To = currentTo,
            Category = currentCategory });
        currentFrom = item.From;
        currentTo = item.To;
        currentCategory = item.Category;
    }
}
output.Add(new Range { From = currentFrom, To = currentTo,
    Category = currentCategory });

Мне было бы интересно узнать, есть ли решение, более оптимизированное для производительности.

Редактировать: я предположил, что список ввода отсортирован. Если это не так, я рекомендую сначала отсортировать его, а не пытаться вмешиваться в алгоритм. Сортировка только O ( n log n ), но если вы попытаетесь ее изменить, вы легко получите O ( n ²), что хуже.

list.Sort((a, b) => a.From < b.From ? -1 : a.From > b.From ? 1 : 0);

Кстати, Я написал это решение, потому что вы попросили оптимизировать производительность. С этой целью я не сделал его универсальным, я не использовал делегатов, я не использовал методы расширения Linq, я использовал локальные переменные примитивных типов и старался по возможности избегать доступа к полям объекта.

Answer 3

Вот еще один:

IEnumerable<Range> Merge(IEnumerable<Range> input)
{
    input = input.OrderBy(r => r.Category).ThenBy(r => r.From).ThenBy(r => r.To).ToArray();
    var ignored = new HashSet<Range>();
    foreach (Range r1 in input)
    {
        if (ignored.Contains(r1))
            continue;

        Range tmp = r1;
        foreach (Range r2 in input)
        {
            if (tmp == r2 || ignored.Contains(r2))
                continue;

            Range merged;
            if (TryMerge(tmp, r2, out merged))
            {
                tmp = merged;
                ignored.Add(r1);
                ignored.Add(r2);
            }
        }
        yield return tmp;
    }
}

bool TryMerge(Range r1, Range r2, out Range merged)
{
    merged = null;
    if (r1.Category != r2.Category)
        return false;
    if (r1.To + 1 < r2.From || r2.To + 1 < r1.From)
        return false;
    merged = new Range
    {
        From = Math.Min(r1.From, r2.From),
        To = Math.Max(r1.To, r2.To),
        Category = r1.Category
    };
    return true;
}

Вы можете использовать его напрямую:

var mergedList = Merge(list);

Но это будет очень неэффективно, если у вас много предметов, так как сложность O (n²),Однако, поскольку можно объединять только элементы в одной и той же категории, вы можете сгруппировать их по категориям и объединить каждую группу, а затем сгладить результат:

var mergedList = list.GroupBy(r => r.Category)
                    .Select(g => Merge(g))
                    .SelectMany(g => g);

Answer 4

Если предположить, что список отсортирован и диапазоны не перекрываются, как вы указали в вопросе, это будет выполнено за O (n) раз:

var flattenedRanges = new List<Range>{new Range(list.First())};

foreach (var range in list.Skip(1))
{
    if (flattenedRanges.Last().To + 1 == range.From && flattenedRanges.Last().Category == range.Category)
        flattenedRanges.Last().To = range.To;
    else
        flattenedRanges.Add(new Range(range));
}

Предполагается, что у вас есть конструктор копирования для Range

EDIT: Вот алгоритм на месте:

    for (int i = 1; i < list.Count(); i++)
    {
        if (list[i].From == list[i - 1].To+1  && list[i-1].Category == list[i].Category)
        {
            list[i - 1].To = list[i].To;
            list.RemoveAt(i--);
        }
    }

EDIT:

Добавлена ​​проверка категории и исправлена ​​версия на месте.