Generic Extension Method To Count Descendants

Question

I've created a extension method to count every available descendant starting from a single, given key.

The data is a flat list, there's is no hierarchical structure. (Well, not entirely true. There is an hierarchy in the data-model, but not in the list itself)

self-reference      parent-reference   some other members
10045     =>        0                   ..
10046     =>        10045               ..
10044     =>        10063               ..
10061     =>        10044               ..
10063     =>        10046               ..
10064     =>        10046               ..
10021     =>        10061               ..
10028     =>        10000               ..
10030     =>        10000               ..
10031     =>        10000               ..
10000     =>        10000               ..

As an example, counting the descendant of the entry with the self-reference number 10046 would result in 6.

Let's take 10021 as an possible related entry to entry 10046, for example.

10021 refers to 10061, 10061 refers to 10044, 10044 refers to 10063, 10063 refers to 10046 => related!

---

My extension method is actually split up in two different methods.

public static int CountDescendants<TSource, T>(
    this IEnumerable<TSource> source, 
    T startKey, 
    Func<TSource, T> selfReference,
    Func<TSource, T> parentReference)
{
    if(source == null) {
        throw new ArgumentNullException("source");
    }

    return Count(source, startKey, selfReference, parentReference);
}

startKey defines our filter, the key we're looking for. In the example above I've used

10046

selfReference defines a unique key a dataset can be identified with.

parentReference defines a unique key which refers to another dataset.

The actual algorithm looks like this.

private static int Count<TSource, T>(
            IEnumerable<TSource> source, 
            T key, 
            Func<TSource, T> selfReference, 
            Func<TSource, T> parentReference)
{
    // hash-map + .Where is faster than using IEnumerable + .Where
    ReadOnlyDictionary<T, T> consolidatedSource = 
        new ReadOnlyDictionary<T, T>(source.ToDictionary(selfReference, parentReference));
    int count = 0;

    // to keep track of every reference which is somehow related to "key"
    HashSet<T> keys = new HashSet<T> {
        key
    };

    // using a stack instead of recurison
    Stack<KeyValuePair<T, T>> stack = new Stack<KeyValuePair<T, T>>();

    // get all first level entries with the given key
    foreach(KeyValuePair<T,T> item in consolidatedSource.Where(x => x.Value.Equals(key))) {
        stack.Push(item);
    }

    // using .Any over .Count because we don't care how many items we have but rather that the stack is not empty
    while (stack.Any()) {
        KeyValuePair<T, T> current = stack.Pop();

        if (keys.Contains(current.Value)) {
            count++;
            keys.Add(current.Key);

            // get all first level entries with the new key
            foreach (KeyValuePair<T, T> item in consolidatedSource.Where(x => x.Value.Equals(current.Key) && !x.Key.Equals(current.Key))){
                stack.Push(item);
            }
        }
    }

    return count;
}

The method can be called like this

this.AllProfiles.CountDescendants(CurrentProfile.Ref, x => x.Ref, x => x.ParentRef);

Is stuff like using a Dictionary to speed up things micro-optimization which I shouldn't worry about? Personally, wherever I can impact performance, I try to get the best out of it. Or at least not make it any worse.

Also, I'm not entirely sure if there are any constraints I can apply to the generic types. I don't think there's one that actually fits and is needed.

Answer 1

Peter already pointed out the main problem with your code: you're doing linear searches when looking for child-nodes, which will blow up to \$O(n^2)\$ for worst-case inputs (very deep trees). Indeed, a lookup table that maps a parent ID to child IDs is much more efficient, and ensures that your method remains \$O(n)\$ for all sorts of input.

Another problem is that your method does not guard against cyclic inputs - it'll run indefinitely. You may want to throw an exception instead, or otherwise prevent the start item from being added to the stack again. It's also a good idea to document this behavior.

Other notes:

• There's no need to perform input validation in a separate method here: Count does not use yield, so the input validation will be performed immediately. Note that a modern alternative is to move the yielding part to a local function instead of to a separate method.
• When throwing argument-related exceptions, it's better to use nameof(parameterName) instead of "parameterName". This lets the compiler protect you against typos, and works well with code refactoring tools.
• I would rename T to TKey, selfReference to keySelector and parentReference to parentKeySelector. I think that better describes their purpose, and it's consistent with other Linq methods.
• Use var to cut down on type name repetition: var variableName = new LongTypeName(...); is equivalent to LongTypeName variableName = new LongTypeName(...);.
• As Peter already mentioned, there's no need for that keys set: you're only adding items with a known parent ID to the stack, so there's no point in verifying whether their parent ID is known.

Answer 2

public static int CountDescendants<TSource, T>(
    this IEnumerable<TSource> source, 
    T startKey, 
    Func<TSource, T> selfReference,
    Func<TSource, T> parentReference)
{
    if(source == null) {
        throw new ArgumentNullException("source");
    }

    return Count(source, startKey, selfReference, parentReference);
}

Thumbs up for doing the validation in a non-coroutine method, although I wonder why source is the only argument which needs validation.

---

    // hash-map + .Where is faster than using IEnumerable + .Where
    ReadOnlyDictionary<T, T> consolidatedSource = 
        new ReadOnlyDictionary<T, T>(source.ToDictionary(selfReference, parentReference));

Firstly, why ReadOnlyDictionary? This isn't exposed outside this method, and within the method you should able to trust yourself not to do anything nasty with it.

Secondly, I think the comment is indicative of a misunderstanding. Hash-map + .TryGetValue is faster than IEnumerable + .Where, but a linear search through a hash-map is no faster than a linear search through a list.

What you probably want to use here is source.ToLookup(parentReference). That will give an asymptotic performance improvement.

---

    Stack<KeyValuePair<T, T>> stack = new Stack<KeyValuePair<T, T>>();

If you have C# 7 then it would probably be nicer to use Stack<(T foo, T bar)> with suitable names. The ability to have names at all is part of the point here.

Although, FWIW, I'm not convinced that you need anything more than Stack<T>, and I don't think keys is necessary at all.