C#•2y ago

❔ LINQ: Group and extract all consecutive elements from List that match predicate

Example:

List<int> ints = new() {6,3,1,1,1,1,1,2,7,8,1,1,1,1,3,2,5,1,1,9,8,1,1,1,1,4,7,8,1}
var output = ints.GroupConsecutive().Where((g) => g.Key == 1); // Not a real function

foreach (var o in output) 
{
  Console.WriteLine(o.Count);
}

List<int> ints = new() {6,3,1,1,1,1,1,2,7,8,1,1,1,1,3,2,5,1,1,9,8,1,1,1,1,4,7,8,1}
var output = ints.GroupConsecutive().Where((g) => g.Key == 1); // Not a real function

foreach (var o in output) 
{
  Console.WriteLine(o.Count);
}

Expected output:

Is there such functionality in LINQ?

32 Replies

TheHelpfulHelperOP•2y ago

Any suggestions for a performant implementation?

ero•2y ago

Just a for loop, right? Or i guess if you need it to work on any ienumerable, a foreach one

Angius•2y ago

Or a foreach, will work with any IEnumerable

TheHelpfulHelperOP•2y ago

I think I'd prefer a solution using LINQ expressions

ero•2y ago

Hm?

Angius•2y ago

TheHelpfulHelperOP•2y ago

Unless a "manual" loop is unavoidable

Angius•2y ago

Write your own, using a loop

TheHelpfulHelperOP•2y ago

I was thinking about using GroupBy and somehow combining the value with its index, then working with that

ero•2y ago

You mentioned performant That will be awful

TheHelpfulHelperOP•2y ago

Yeah I suppose a manual foreach is the best then Weird/Sad that there isnt a GroupConsecutive method :/ I adjusted my example to better reflect a general solution Yeah having multiple KVP is not good, since they all contain the same Key Would IGrouping be more appropiate? Or maybe a KeyValuePair<T, IReadOnlyList<T>> Yeah

ero•2y ago

Wait huh? You want the values? How does that make sense? You already select the value in the call

TheHelpfulHelperOP•2y ago

Look at my example. My supposed "GroupConsecutive" method will give you a List which itself contains Groupings of all the consecutive elements in the given List. Essentially it (as the name implies) groups all the elements which are consecutively equal in the list. So 1,2,3,4 would give you 4 groupings, but 1,2,2,3 would only give you 3, while 1,2,2,3,2 would give you 4 again

ero•2y ago

TheHelpfulHelperOP•2y ago

I suppose for simple integers it does not make a lot of sense but I could also imagine needing a ConsecutiveGroupBy method, where the key is chosen from an object Then the grouping would only have that key as the key of the grouping, but the actual elements could be objects Uhh that doesnt compile for me

ero•2y ago

Wouldn't it be <TValue, int>

TheHelpfulHelperOP•2y ago

Huh seems to be a weird bug with copy and paste...if I manually write the exact same thing out it works.

Henkypenky•2y ago

https://stackoverflow.com/questions/20469416/linq-to-find-series-of-consecutive-numbers modify it for consecutive and equal

rotor_•2y ago

I'd have called this a folding problem Presumably you don't actually want to group the values. You just want to see how many of each sequence there are So why store anything more than the keys and counts? So you'd use LINQ Aggregate with a result value that holds a list of tuples representing the key and the count. For each iteration you'd compare the current key with the most recent key in the result value. If the keys are different, push a new tuple onto the result with the new key and a count of zero

static List<T> WhoopsAddReturnsVoid<T>(this List<T> list, T val) {
    list.Add(val);
    return list;
}

var ints = new List<int>{6,3,1,1,1,1,1,2,7,8,1,1,1,1,3,2,5,1,1,9,8,1,1,1,1,4,7,8,1};

var keysAndCounts = ints.Aggregate( 
      (new List<(int, int)>(), (-1,-1)), 
      (carry, current) =>       
          carry switch {                          
              (var result, (-1, -1)) =>
                  (result, (current, 1)),
              (var result, var (key, count)) => 
                  current == key 
                      ? (result, (key, count + 1)) 
                      : (result.WhoopsAddReturnsVoid((key, count)), (current, 1)) 
          }, 
      carry => carry.Item1.WhoopsAddReturnsVoid(carry.Item2));

var all1Counts = keysAndCounts
    .Where(pair => pair.Item1 == 1)
    .Select(pair => pair.Item2);

foreach (var val in all1Counts) {
    Console.WriteLine(val);
}

static List<T> WhoopsAddReturnsVoid<T>(this List<T> list, T val) {
    list.Add(val);
    return list;
}

var ints = new List<int>{6,3,1,1,1,1,1,2,7,8,1,1,1,1,3,2,5,1,1,9,8,1,1,1,1,4,7,8,1};

var keysAndCounts = ints.Aggregate( 
      (new List<(int, int)>(), (-1,-1)), 
      (carry, current) =>       
          carry switch {                          
              (var result, (-1, -1)) =>
                  (result, (current, 1)),
              (var result, var (key, count)) => 
                  current == key 
                      ? (result, (key, count + 1)) 
                      : (result.WhoopsAddReturnsVoid((key, count)), (current, 1)) 
          }, 
      carry => carry.Item1.WhoopsAddReturnsVoid(carry.Item2));

var all1Counts = keysAndCounts
    .Where(pair => pair.Item1 == 1)
    .Select(pair => pair.Item2);

foreach (var val in all1Counts) {
    Console.WriteLine(val);
}

@TheHelpfulHelper try this

ero•2y ago

yeah but who would want to use that that's incredibly unreadable also what's with those -1s?

rotor_•2y ago

It's because C# isn't bundled with a maybe type And everybody knows that readability is subjective The reason I like this solution is that it's performant and that any mistake you make will lead to a compiler error. I agree it should be pulled into its own declaration rather than as a big inline blob though

ero•2y ago

no but, why -1? does this not mess up if the first item in the enumerable is -1? does this even work with other types? this is just not a solution, at all and don't talk about this being performant, this is using linq

rotor_•2y ago

Hey @TheHelpfulHelper I cleaned up my first solution and made it generic for you

  public static List<T> With<T>(this List<T> list, T val) 
  {                                                                                                         
      list.Add(val);                                                                                        
      return list;                                                                                          
  }                                                                                                         
   
  static IEnumerable<(T, int)> CountContiguous<T>(this IEnumerable<T> seq) where T : IEquatable<T> 
  { 
      var NULL_TUPLE = (default(T), -1); 
      var aggregateFn = ((List<(T, int)>, (T, int)) carry, T current) => 
          carry switch 
          { 
              (var result, (_, -1)) => 
                  (result, (current, 1)), 
              (var result, var (key, count)) => 
                  (key?.Equals(current) ?? current is null) 
                      ? (result, (key, count + 1)) 
                      : (result.With((key, count)), (current, 1)) 
          }; 
      return seq.Aggregate(
          (new List<(T, int)>(), NULL_TUPLE),
          aggregateFn,
          pair => pair.Item1.With(pair.Item2)
      );
  }
   
  void MainFn() 
  { 
      var ints = new List<int> { 6, 3, 1, 1, 1, 1, 1, 2, 7, 8, 1, 1, 1, 1, 3, 2, 5, 1, 1, 9, 8, 1, 1, 1, 1, 4, 7, 8, 1 }; 
   
      var allCountsOf1 = ints.CountContiguous().Where(pair => pair.Item1 == 1); 
   
      foreach (var (key, count) in allCountsOf1) 
      { 
          Console.WriteLine(count);      
      } 
  }

  public static List<T> With<T>(this List<T> list, T val) 
  {                                                                                                         
      list.Add(val);                                                                                        
      return list;                                                                                          
  }                                                                                                         
   
  static IEnumerable<(T, int)> CountContiguous<T>(this IEnumerable<T> seq) where T : IEquatable<T> 
  { 
      var NULL_TUPLE = (default(T), -1); 
      var aggregateFn = ((List<(T, int)>, (T, int)) carry, T current) => 
          carry switch 
          { 
              (var result, (_, -1)) => 
                  (result, (current, 1)), 
              (var result, var (key, count)) => 
                  (key?.Equals(current) ?? current is null) 
                      ? (result, (key, count + 1)) 
                      : (result.With((key, count)), (current, 1)) 
          }; 
      return seq.Aggregate(
          (new List<(T, int)>(), NULL_TUPLE),
          aggregateFn,
          pair => pair.Item1.With(pair.Item2)
      );
  }
   
  void MainFn() 
  { 
      var ints = new List<int> { 6, 3, 1, 1, 1, 1, 1, 2, 7, 8, 1, 1, 1, 1, 3, 2, 5, 1, 1, 9, 8, 1, 1, 1, 1, 4, 7, 8, 1 }; 
   
      var allCountsOf1 = ints.CountContiguous().Where(pair => pair.Item1 == 1); 
   
      foreach (var (key, count) in allCountsOf1) 
      { 
          Console.WriteLine(count);      
      } 
  }

I hope this helps you Testing it produces the answers you were hoping to see

ero•2y ago

you have like a billion nullability warnings there lol

rotor_•2y ago

Oh my mistake. Could you point some out, please?

ero•2y ago

you just need to put T? almost everywhere because T could technically be a reference type where default(T) would be null

static IEnumerable<(T?, int)> CountContiguous<T>(this IEnumerable<T> seq) where T : IEquatable<T>
{
    var NULL_TUPLE = (default(T), -1);

    var aggregateFn = ((List<(T?, int)>, (T?, int)) carry, T? current) =>
        carry switch
        {
            (var result, (_, -1)) =>
                (result, (current, 1)),
            (var result, var (key, count)) =>
                (key?.Equals(current) ?? current is null)
                    ? (result, (key, count + 1))
                    : (result.AddAndReturnSelf((key, count)), (current, 1))
        };

    return seq.Aggregate(
        (new List<(T?, int)>(), NULL_TUPLE),
        aggregateFn,
        pair => pair.Item1.AddAndReturnSelf(pair.Item2));
}

static IEnumerable<(T?, int)> CountContiguous<T>(this IEnumerable<T> seq) where T : IEquatable<T>
{
    var NULL_TUPLE = (default(T), -1);

    var aggregateFn = ((List<(T?, int)>, (T?, int)) carry, T? current) =>
        carry switch
        {
            (var result, (_, -1)) =>
                (result, (current, 1)),
            (var result, var (key, count)) =>
                (key?.Equals(current) ?? current is null)
                    ? (result, (key, count + 1))
                    : (result.AddAndReturnSelf((key, count)), (current, 1))
        };

    return seq.Aggregate(
        (new List<(T?, int)>(), NULL_TUPLE),
        aggregateFn,
        pair => pair.Item1.AddAndReturnSelf(pair.Item2));
}

rotor_•2y ago

Ah yes I'd accounted for nulls in the code but had forgotten to annotate the type Well spotted

ero•2y ago

|                Method |    Size |            Mean |         Error |        StdDev |  Allocated |
|---------------------- |-------- |----------------:|--------------:|--------------:|-----------:|
|   CountContiguous_Ero |      10 |        258.4 ns |       3.39 ns |       3.17 ns |      304 B |
|   CountContiguous_Ero |      50 |        833.1 ns |       2.69 ns |       2.38 ns |      360 B |
|   CountContiguous_Ero |     100 |      1,612.5 ns |      20.54 ns |      19.21 ns |      448 B |
|   CountContiguous_Ero |   10000 |    147,899.4 ns |   1,157.82 ns |     966.83 ns |    16872 B |
|   CountContiguous_Ero | 1000000 | 14,658,540.5 ns | 117,910.87 ns |  98,460.92 ns |  1049266 B |
|                       |         |                 |               |               |            |
| CountContiguous_Rotor |      10 |        299.6 ns |       2.55 ns |       2.13 ns |      392 B |
| CountContiguous_Rotor |      50 |      1,574.9 ns |       7.93 ns |       7.03 ns |     1456 B |
| CountContiguous_Rotor |     100 |      3,165.3 ns |      27.86 ns |      26.06 ns |     2744 B |
| CountContiguous_Rotor |   10000 |    350,129.8 ns |   6,956.69 ns |   5,809.15 ns |   279294 B |
| CountContiguous_Rotor | 1000000 | 33,320,041.5 ns | 136,918.83 ns | 114,333.42 ns | 17827455 B |

|                Method |    Size |            Mean |         Error |        StdDev |  Allocated |
|---------------------- |-------- |----------------:|--------------:|--------------:|-----------:|
|   CountContiguous_Ero |      10 |        258.4 ns |       3.39 ns |       3.17 ns |      304 B |
|   CountContiguous_Ero |      50 |        833.1 ns |       2.69 ns |       2.38 ns |      360 B |
|   CountContiguous_Ero |     100 |      1,612.5 ns |      20.54 ns |      19.21 ns |      448 B |
|   CountContiguous_Ero |   10000 |    147,899.4 ns |   1,157.82 ns |     966.83 ns |    16872 B |
|   CountContiguous_Ero | 1000000 | 14,658,540.5 ns | 117,910.87 ns |  98,460.92 ns |  1049266 B |
|                       |         |                 |               |               |            |
| CountContiguous_Rotor |      10 |        299.6 ns |       2.55 ns |       2.13 ns |      392 B |
| CountContiguous_Rotor |      50 |      1,574.9 ns |       7.93 ns |       7.03 ns |     1456 B |
| CountContiguous_Rotor |     100 |      3,165.3 ns |      27.86 ns |      26.06 ns |     2744 B |
| CountContiguous_Rotor |   10000 |    350,129.8 ns |   6,956.69 ns |   5,809.15 ns |   279294 B |
| CountContiguous_Rotor | 1000000 | 33,320,041.5 ns | 136,918.83 ns | 114,333.42 ns | 17827455 B |

public static IEnumerable<(TSource Value, int Count)> CountContiguous<TSource>(
    this IEnumerable<TSource> source,
    IEqualityComparer<TSource>? comparer = null)
{
    comparer ??= EqualityComparer<TSource>.Default;
    int count = 1;

    using IEnumerator<TSource> e = source.GetEnumerator();
    if (!e.MoveNext())
    {
        string msg = "Sequence contains no elements.";
        throw new InvalidOperationException(msg);
    }

    TSource previous = e.Current;
    TSource current;

    while (e.MoveNext())
    {
        current = e.Current;

        if (comparer.Equals(previous, current))
        {
            count++;
        }
        else
        {
            yield return (previous, count);

            count = 1;
        }

        previous = current;
    }

    yield return (previous, count);
}

public static IEnumerable<(TSource Value, int Count)> CountContiguous<TSource>(
    this IEnumerable<TSource> source,
    IEqualityComparer<TSource>? comparer = null)
{
    comparer ??= EqualityComparer<TSource>.Default;
    int count = 1;

    using IEnumerator<TSource> e = source.GetEnumerator();
    if (!e.MoveNext())
    {
        string msg = "Sequence contains no elements.";
        throw new InvalidOperationException(msg);
    }

    TSource previous = e.Current;
    TSource current;

    while (e.MoveNext())
    {
        current = e.Current;

        if (comparer.Equals(previous, current))
        {
            count++;
        }
        else
        {
            yield return (previous, count);

            count = 1;
        }

        previous = current;
    }

    yield return (previous, count);
}

and for a CountContiguousBy, just do;

public static IEnumerable<(TResult Value, int Count)> CountContiguous_Ero<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector,
    IEqualityComparer<TSource>? comparer = null)
{
    // ...

            yield return (selector(previous), count);

    // ...
}

public static IEnumerable<(TResult Value, int Count)> CountContiguous_Ero<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector,
    IEqualityComparer<TSource>? comparer = null)
{
    // ...

            yield return (selector(previous), count);

    // ...
}

actually you wanna do the select beforehand and do the equality comparison on the result of that so like this;

public static IEnumerable<(TResult Value, int Count)> CountContiguousBy<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector,
    IEqualityComparer<TResult>? comparer = null)
{
    comparer ??= EqualityComparer<TResult>.Default;
    int count = 1;

    using IEnumerator<TSource> e = source.GetEnumerator();
    if (!e.MoveNext())
    {
        string msg = "Sequence contains no elements.";
        throw new InvalidOperationException(msg);
    }

    TResult previous = selector(e.Current);
    TResult current;

    while (e.MoveNext())
    {
        current = selector(e.Current);

        if (comparer.Equals(previous, current))
        {
            count++;
        }
        else
        {
            yield return (previous, count);

            count = 1;
        }

        previous = current;
    }

    yield return (previous, count);
}

public static IEnumerable<(TResult Value, int Count)> CountContiguousBy<TSource, TResult>(
    this IEnumerable<TSource> source,
    Func<TSource, TResult> selector,
    IEqualityComparer<TResult>? comparer = null)
{
    comparer ??= EqualityComparer<TResult>.Default;
    int count = 1;

    using IEnumerator<TSource> e = source.GetEnumerator();
    if (!e.MoveNext())
    {
        string msg = "Sequence contains no elements.";
        throw new InvalidOperationException(msg);
    }

    TResult previous = selector(e.Current);
    TResult current;

    while (e.MoveNext())
    {
        current = selector(e.Current);

        if (comparer.Equals(previous, current))
        {
            count++;
        }
        else
        {
            yield return (previous, count);

            count = 1;
        }

        previous = current;
    }

    yield return (previous, count);
}

also here's the benchmark code;

[MemoryDiagnoser(false)]
[Orderer(SummaryOrderPolicy.Method)]
public class Benchmarks
{
    private const int MaxRandom = 7;

    private int[] _values;

    [Params(10, 50, 100, 10_000, 1_000_000)]
    public int Size { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        _values = new int[Size];

        for (int i = 0; i < Size; i++)
        {
            _values[i] = Random.Shared.Next(0, MaxRandom);
        }
    }

    [Benchmark]
    public List<int> CountContiguous_Rotor()
    {
        return _values.CountContiguous_Rotor()
            .Where(g => g.Value == 1)
            .Select(g => g.Count)
            .ToList();
    }

    [Benchmark]
    public List<int> CountContiguous_Ero()
    {
        return _values.CountContiguous_Ero()
            .Where(g => g.Value == 1)
            .Select(g => g.Count)
            .ToList();
    }
}

[MemoryDiagnoser(false)]
[Orderer(SummaryOrderPolicy.Method)]
public class Benchmarks
{
    private const int MaxRandom = 7;

    private int[] _values;

    [Params(10, 50, 100, 10_000, 1_000_000)]
    public int Size { get; set; }

    [GlobalSetup]
    public void Setup()
    {
        _values = new int[Size];

        for (int i = 0; i < Size; i++)
        {
            _values[i] = Random.Shared.Next(0, MaxRandom);
        }
    }

    [Benchmark]
    public List<int> CountContiguous_Rotor()
    {
        return _values.CountContiguous_Rotor()
            .Where(g => g.Value == 1)
            .Select(g => g.Count)
            .ToList();
    }

    [Benchmark]
    public List<int> CountContiguous_Ero()
    {
        return _values.CountContiguous_Ero()
            .Where(g => g.Value == 1)
            .Select(g => g.Count)
            .ToList();
    }
}

rotor_•2y ago

It'd be nice if the OP showed up to appreciate how much work we're putting in for them lol I would argue that we've just produced two valid solutions written using different paradigms, although I'd prefer yours if it was in a library.

ero•2y ago

You could speed mine up even more for ILists, i reckon Use the indexer instead but at that point it becomes a bit ridiculous i guess

rotor_•2y ago

I'd generally advocate using the smallest tool necessary for the job haha Otherwise you end up with things like Spring Boot

Accord•2y ago

Was this issue resolved? If so, run /close - otherwise I will mark this as stale and this post will be archived until there is new activity.

Gaming

Programming

❔ LINQ: Group and extract all consecutive elements from List that match predicate