Merge elements in IEnumarable according to a conditon

Question

Hello Everyone,

I was looking for some fast and efficient method do merge items in array. This is my scenario. The collection is sorted by From. Adjacent element not necessarily differ by 1, that is there can be gaps between the last To and the next From, but they never overlap.

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" });

I would like the above collection to be merged in such way that the first three (this number can vary, from at least 2 elements to as many as the condition is satisfied) elements become one element. Cannot merge elements with different category.

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

So that the resulting collection would have 4 elements total.

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

I have a very large collection with over 2.000.000 items and I would like to this as efficiently as possible. Any ideas?

Thank you.

Answer 1

Well, from the statement of the problem I think it is obvious that you cannot avoid iterating through the original collection of 2 million items:

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 });

I’d be interested to see if there is a solution more optimised for performance.

Edit: I assumed that the input list is sorted. If it is not, I recommend sorting it first instead of trying to fiddle this into the algorithm. Sorting is only O(n log n), but if you tried to fiddle it in, you easily get O(n²), which is worse.

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

As an aside, I wrote this solution because you asked for one that is performance-optimised. To this end, I didn’t make it generic, I didn’t use delegates, I didn’t use Linq extension methods, and I used local variables of primitive types and tried to avoid accessing object fields as much as possible.

Answer 2

Here's a generic, reusable solution rather than an ad hoc, specific solution. (Updated based on comments)

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;
      }
    }
}

You will have to provide method to determine if the item can be merged, and to merge them. These really should be part of your Range class, so it would be called like them:

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

If you don't have these method, then you would have to call it like:

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 3

Assuming that the list is sorted -and- the ranges are non overlapping, as you have stated in the question, this will run in O(n) time:

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));
}

This is assuming you have a copy-constructor for Range

EDIT: Here's an in-place algorithm:

    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:

Added the category check, and fixed the inplace version.

Answer 4

Here's another one :

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;
}

You could use it directly:

var mergedList = Merge(list);

But that would be very inefficient it you have many items as the complexity is O(n²). However, since only items in the same category can be merged, you can group them by category and merge each group, then flatten the result:

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