5
\$\begingroup\$

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.

\$\endgroup\$
  • \$\begingroup\$ Wouldn't it be more useful to return a tree structure, and then have properties like Count on each Node? \$\endgroup\$ – dfhwze Aug 29 at 7:44
  • \$\begingroup\$ Using a flat structure greatly simplifies other parts of the application, especially when working with databases. Creating a tree structure would be a way but I wouldn't have any use for. I think it would be 'too much' if I created one just to count the nodes afterwards. \$\endgroup\$ – Shawn Aug 29 at 7:54
  • \$\begingroup\$ Understandable... I just figured a method to convert this flat structure to tree might be very reusable :) \$\endgroup\$ – dfhwze Aug 29 at 7:55
  • \$\begingroup\$ Is it a static read only list, or is it dynamic (delete/add)? And what is the expected average size of it? \$\endgroup\$ – Henrik Hansen Aug 29 at 17:18
6
\$\begingroup\$

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.
\$\endgroup\$
  • 1
    \$\begingroup\$ Thanks for pointing out the possible infinite loop. Data-wise it shouldn't be possible, but I'v added a guard. The only reason I've separated those methods because I didn't want the actual algorithm to do 'too much' and mainly because I've been doing it with other methods as well. Using nameof is a good idea. Thanks! \$\endgroup\$ – Shawn Aug 29 at 12:31
  • \$\begingroup\$ Good point on the cycle detection, but then maybe keys is useful after all. It's certainly the most straightforward way of detecting a cycle. \$\endgroup\$ – Peter Taylor Aug 29 at 13:43
5
\$\begingroup\$
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.

\$\endgroup\$
  • \$\begingroup\$ Thanks for your answer! I already added the validation for the other arguments but forgot to update my post. I used the ReadOnlyDictionary out of habit because I usually explicitly declare read-only types as such, but I followed your suggestion to use .ToLookup instead. The HashSet is useless as you mentioned, I removed it. I also changed the stack to be of the type T. Thanks for your notes, they really helped! \$\endgroup\$ – Shawn Aug 29 at 12:17

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.