5
\$\begingroup\$

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)));
    }
}                      
\$\endgroup\$
1
  • 1
    \$\begingroup\$ Wow, I kept reading it as feather weight until I realised it says feature :-D \$\endgroup\$
    – Timwi
    Feb 24 '11 at 15:35
5
\$\begingroup\$
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.

\$\endgroup\$
1
  • 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
    Feb 24 '11 at 15:36
5
\$\begingroup\$

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.

\$\endgroup\$
4
  • \$\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
    Feb 24 '11 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
    Feb 25 '11 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
    Feb 25 '11 at 21:42
  • \$\begingroup\$ @Saeed: I’m just saying. No harm done. :) Thanks for the upvote, anyway! \$\endgroup\$
    – Timwi
    Feb 26 '11 at 2:11

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.