Is this Recursion + Linq example inefficient?

Question

I have a hierarchy of of groups, and I want to get a collection of all the lowest level groups (or leaves if we'll look at this as a tree).

I wrote the following code. Is it inefficient?

public static class FeatureWeightGroupExtensions
{
    public static IEnumerable<IFeatureWeightGroup> GetLeafGroups(this IFeatureWeightGroup featureWeightGroup)
    {
        return GetLeafGroupsRecursive(featureWeightGroup).ToList();
    }

    private static IEnumerable<IFeatureWeightGroup> GetLeafGroupsRecursive(IFeatureWeightGroup featureWeightGroup)
    {
        if (!featureWeightGroup.ChildGroups.Any())
            return Enumerable.Repeat(featureWeightGroup, 1);

        return featureWeightGroup.ChildGroups.Aggregate(Enumerable.Empty<IFeatureWeightGroup>(),
                                                        (allGroups, group) =>
                                                        allGroups.Concat(GetLeafGroupsRecursive(group)));
    }
}

Wow, I kept reading it as feather weight until I realised it says feature :-D — Timwi
– Timwi, Commented Feb 24, 2011 at 15:35

Timwi · Accepted Answer · 2011-02-27 01:45:24Z

5

return featureWeightGroup.ChildGroups.Aggregate(Enumerable.Empty<IFeatureWeightGroup>(),
                                                    (allGroups, group) =>
                                                    allGroups.Concat(GetLeafGroupsRecursive(group)));

It looks like it can be replaced with:

return featureWeightGroup.ChildGroups
           .SelectMany(g => GetLeafGroupsRecursive(group));

Which probably will not be much better from performance point of view, but looks cleaner.

edited Feb 27, 2011 at 1:45

Timwi

1,1246 silver badges14 bronze badges

answered Feb 24, 2011 at 13:14

Snowbear

3,6931 gold badge20 silver badges23 bronze badges

3

\$\begingroup\$ Actually it would be much better performance. The Aggregate version would instantiate many Concat iterators, which would constantly forward MoveNext() calls to each other, while your improvement instantiates only one SelectMany iterator. \$\endgroup\$

Timwi
– Timwi

2011-02-24 15:36:45 +00:00
Commented Feb 24, 2011 at 15:36

Add a comment |

Timwi · Accepted Answer · 2011-02-24 15:42:37Z

5

As already pointed out by Snowbear and my comment on his answer, you can improve the performance and readability by using SelectMany instead of Concat.

However, I notice that you are using ToList() at the end anyway. This pulls into question the benefit of using LINQ and all those SelectMany iterators in the first place. Using LINQ sacrifices performance at the benefit of lazy evaluation, but you are not using the lazy-evaluation aspect. Therefore, if performance is what you are after, then don’t use LINQ that much:

public static class FeatureWeightGroupExtensions
{
    public static IEnumerable<IFeatureWeightGroup> GetLeafGroups(this IFeatureWeightGroup featureWeightGroup)
    {
        var list = new List<IFeatureWeightGroup>();
        populateList(list, featureWeightGroup);
        return list;
    }

    private static void populateList(List<IFeatureWeightGroup> list, IFeatureWeightGroup featureWeightGroup)
    {
        if (!featureWeightGroup.ChildGroups.Any())
            list.Add(featureWeightGroup);
        else
            foreach (var childGroup in featureWeightGroup.ChildGroups)
                populateList(list, childGroup);
    }
}

This is the most performance-optimised way I can think of, while at the same time also being significantly easier to read than the original or the SelectMany alternative.

answered Feb 24, 2011 at 15:42

Timwi

1,1246 silver badges14 bronze badges

\$\begingroup\$ +1 for the answer. -0.5 for lack of curly braces in your if and foreach statements (which still rounds up to +1). IMO, curly braces are never optional. \$\endgroup\$

Saeed
– Saeed

2011-02-24 22:51:28 +00:00
Commented Feb 24, 2011 at 22:51
2

\$\begingroup\$ @Saeed: It’s totally fine for you to have that opinion, but try not to let that turn into intolerance of other people’s opinions. \$\endgroup\$

Timwi
– Timwi

2011-02-25 20:08:43 +00:00
Commented Feb 25, 2011 at 20:08
\$\begingroup\$ last I checked, this is a code review forum where style comments are encouraged. I was merely pointing out that I don't agree with that style point in your answer, so my vote should not be seen as condoning it. Not sure how that qualifies as intolerance. \$\endgroup\$

Saeed
– Saeed

2011-02-25 21:42:59 +00:00
Commented Feb 25, 2011 at 21:42
\$\begingroup\$ @Saeed: I’m just saying. No harm done. :) Thanks for the upvote, anyway! \$\endgroup\$

Timwi
– Timwi

2011-02-26 02:11:06 +00:00
Commented Feb 26, 2011 at 2:11

Add a comment |

Stack Exchange Network

Is this Recursion + Linq example inefficient?

2 Answers 2

You must log in to answer this question.

Hot Network Questions

Is this Recursion + Linq example inefficient?

2 Answers 2

You must log in to answer this question.

Related

Hot Network Questions