7
\$\begingroup\$

I've created a method that groups Item entities below based on their Value property. The idea is to produce groups that also includes possible "edge duplicates", i.e.

[{ Value: 9 }, { Value: 10 }, { Value: 11 }]

With rangeSize set to 10 yields two groups:

[ [{ Value: 9 }, { Value: 10 }], [{ Value: 10 }, { Value: 11 }] ]
public IEnumerable<IEnumerable<DTO.Item>> GroupByValueRange(int rangeSize)
{
    var items = _itemRepository.GetAll().ToList();
    var steps = Math.Ceiling(items.Max(p => p.Value) / rangeSize);
    var groups = new List<IEnumerable<DTO.Item>>();

    for (var i = 1; i <= steps; i++)
    {
        var max = i * rangeSize;
        var min = (i - 1) * rangeSize;
        var currentGroup = items.Where(p => p.Value >= min && p.Value <= max);
        groups.Add(currentGroup.Select(p => _mapper.Map<DTO.Item>(p)));
    }

    return groups;
}

So the idea is to create groups with values like 0-10, 10-20, 20-30 etc...

\$\endgroup\$
3
\$\begingroup\$

Can there be empty groups?

If you pass in a rangeSize of 5, your current code will have an empty group. Is this desired?

Iterating over entire collection for each group

In addition to Peter Csala's recommendations, there is a possible performance issue here: you are iterating over the entire source for each group. The delegate passed to Where must be evaluated against all the items, to determine the contents of each group.

for (var i = 1; i <= steps; i++)
{
    ...
    var currentGroup = items.Where(p => p.Value >= min && p.Value <= max);
    groups.Add(currentGroup.Select(p => _mapper.Map<DTO.Item>(p)));
}

If you have few items, or only a small number of groups, this might not be an issue.

The following might be more efficient. Create a sequence of mapped-item / group-index pairs:

public IEnumerable<(DTO.Item mappedItem, int groupIndex)> GroupIndexes(int rangeSize) {
    foreach (var item in _itemRepository.GetAll()) {
        var groupIndex = Math.Floor(item.Value / rangeSize);
        var mapped = _mapper.Map<DTO.Item>(item);
        yield return (mapped, groupIndex);
        if (item.Value > 0 && item.Value % rangeSize == 0) {
            yield return (mapped, groupIndex - 1);
        }
    }
}

which you could then use to group:

var grouped = GroupIndexes(10).GroupBy(x => x.groupIndex, x => x.mappedItem);
| improve this answer | |
\$\endgroup\$
3
+150
\$\begingroup\$

I would generalize it as an extension method:

public static IEnumerable<IEnumerable<U>> GroupByValueRange<T, U>(
    this IEnumerable<T> items,
    int rangeSize,
    Func<T, double> getValue,
    Func<T, U> map)
{
    items = items.ToList();

    double steps = Math.Ceiling(items.Max(getValue) / rangeSize);

    for (int i = 1; i <= steps; i++)
    {
        int max = i * rangeSize;
        int min = (i - 1) * rangeSize;

        yield return items
            .Where(p => getValue(p) >= min && getValue(p) <= max)
            .Select(map);
    }
}

Your code to call it would look like:

var grouped = _itemRepository.GetAll().GroupByValueRange(10, p => p.Value, p => _mapper.Map<RepoistoryItem, DTO.Item>(p));

(I made up RepositoryItem for this)

| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

There is a room for improvement:

  1. var items = _itemRepository.GetAll().ToList();: Try to separate methods based on their responsibilities. Data retrieval and data processing should be not be in the same method.
  2. List is treated as IEnumerable: List's Enumerator is a struct but because you are accessing via the interface an implicit hidden boxing is happening unnecessarily. Further details
  3. List<IEnumerable<T>> and IEnumerable<IEnumerable<T>>: IEnumerable is a forward only iterator. This enables you construct the elements one-by-one (using yield return) so you don't have to compute all values upfront (into the groups) and then return it as an iterator of iterators.
  4. Depending on the size of the source an ascending ordering and the use of the ArraySegment can cause significant performance improvement.
| improve this answer | |
\$\endgroup\$
2
\$\begingroup\$

As others pointed out you are iterating over the source a lot. Once ToList and every loop in the step. Your grouping method is tied to repository and GetAll method. It would be better to pass that into the method instead of having how to access data as part of the grouping. I would also recommend removing the mapping from this method as well and use the standard Select afterwards. Every method should just have one responsibility and right now your method gets data, groups data and projects the data. This would make it hard to unit test and maintain down the road.

Typically when dealing with IEnumerable we want to try to avoid multiple iterations. We can do this here but does make the code more complicated. It's always a fine line between complex code and maintenance.

Can see in this method signature it takes in the source, rangeSize and how we determine the grouping value.

public static class IEnumerableExtensions
{
    public static ILookup<(int start, int end), TSource> GroupByRange<TSource>(this IEnumerable<TSource> source, int rangeSize, Func<TSource, decimal> valueFunc)
    {

You could just update your method to be that signature and fix it but you would still have the issue of multiple iterations, but at least it would be testable and responsible for one thing only.

Like I said before we want to just iterate over the source once it does get more complex but we can go step by step into it and only you will know if it's worth it.

Starters I'm return an ILookup as that will act like across between a dictionary and grouping and it's readonly. I'm also using the ValueTuple and if using a version of .net that doesn't have that I would recommend creating a struct that would hold the range.

public static ILookup<(int start, int end), TSource> GroupByRange<TSource>(this IEnumerable<TSource> source, int rangeSize, Func<TSource, decimal> valueFunc)
{
    var grouping = new Dictionary<(int start, int end), List<TSource>>();
    var maxValue = 0m;
    foreach (var item in source)
    {
        var value = valueFunc(item);
        CheckIfNeedToResize(value, maxValue, rangeSize, grouping, valueFunc);
        foreach (var group in grouping.Where(grp => grp.Key.start <= value && grp.Key.end >= value))
        {
            group.Value.Add(item);
        }
    }

    // not in love with iterating over the dictionary to convert to lookup
    //   if don't want to do this could return IReadOnlyDictionary
    //    also because of SelectMany this will exclude key ranges that don't have values
    //   if we do return readonly dictionary it will include "empty" key ranges
    //   if return readonly dictionary should make it value IEnumerable or and array as well
    return grouping.SelectMany(x => x.Value.Select(v => new { x.Key, Value = v }))
        .ToLookup(x => x.Key, x => x.Value);
}

As you can see this part of the code isn't that complicated. For the return value if you need the "empty" result sets then I would return a ReadOnlyDictionary instead of LookUp. Again only you know if that's a requirement or not.

Now for the complicated code. We can storing the maxValue so we can see if we need to add more slots when we hit the next value. We are going to calculate the slots as we move through the collection instead of up front.

private static void CheckIfNeedToResize<TSource>(decimal currentValue, decimal maxValue, int rangeSize, IDictionary<(int, int), List<TSource>> grouping, Func<TSource, decimal> valueFunc)
{
    if (currentValue > maxValue)
    {
        maxValue = currentValue;
        // check if we need to add ranges
        var groupCount = grouping.Count;
        var steps = Math.Ceiling(currentValue / rangeSize);
        if (steps > int.MaxValue)
        {
            throw new IndexOutOfRangeException();
        }
        if (steps > groupCount)
        {
            // add in extra "rows" into dictionary
            foreach (var key in Enumerable.Range(groupCount, (int)steps - groupCount)
                .Select(x => (x * rangeSize, (x + 1) * rangeSize)))
            {
                grouping.Add(key, new List<TSource>());
            }

            // have an edge case if previous end group had the ending range values in it we need
            //  to add it into the next range that we added
            if (groupCount > 0)
            {
                var endRange = groupCount * rangeSize;
                var lastList = grouping[((groupCount - 1) * rangeSize, endRange)];
                var items = lastList.Where(x => valueFunc(x) == endRange);
                grouping[(endRange, (groupCount + 1) * rangeSize)].AddRange(items);
            }
        }
    }
}

This could be merged up in the main method but because there is a lot going on I moved it to its own. That is personal choice but I feel its easier to read and understand this way. We first check if the current value greater than the max value if so we calculate if we need to add another slot or multiple slots. For each slot we calculate we need to add it to the dictionary and initialize the list of values. There is an edge case where we need to iterate of the last value list to see if we need to add any to the new slot. While if each slot did contain one value each time in theory we would end up iterating over the source twice, I would guess in practice this wouldn't be as much as twice the collection but still that's worst case of n*3.

Now for testing I just used a console app but you could see how easy it would be to convert to unit test.

static void Main(string[] args)
{
    var testData = new[] { new { Value = 14 }, new { Value = 30 }, new { Value = 11 }};
    var lookup = testData.GroupByRange(5, x => x.Value);
    foreach (var items in lookup)
    {
        Console.WriteLine($"Start: {items.Key.start} End: {items.Key.end}");
        foreach (var data in items)
        {
            Console.Write($"     Value {data.Value} ");
        }
        Console.WriteLine();
    }

    Console.WriteLine("---------------");

    testData = new[] { new { Value = 9 }, new { Value = 10 }, new { Value = 11 } };
    lookup = testData.GroupByRange(10, x => x.Value);
    foreach (var items in lookup)
    {
        Console.WriteLine($"Start: {items.Key.start} End: {items.Key.end}");
        foreach (var data in items)
        {
            Console.Write($"     Value {data.Value} ");
        }
        Console.WriteLine();
    }


    Console.WriteLine("done" );
    
    Console.ReadLine();
}

The first one I wanted to show how it will skip "empty" ranges and the second one was just showing the same results you posted with yours.

Again this doesn't do the projection and I would just do _itemRepository.GetAll().GroupByRange(10, x => x.Value).Select(_mapper.Map<DTO.Item>) as I don't think adding a projection parameter gains much. With this way now you have a method that is unit testable and can be reused.

| improve this answer | |
\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.