Performance of reverse-mapping collection

Question

I have a collection of objects where every object has a unique string Id, and any other object can contain entirely arbitrary (many-to-one) "Links" to another object. I also want to be able to generate a "usage map" which is the reverse index -- given any one object, which other objects are linked either directly to it or to a child of it? (Here a "child" is defined as any object with a matching prefix Id, as the Id is a dotted-path notation.)

So Baz.Boz might be one object that links to Foo.Bar -- the usage map should then reflect that both Foo and Foo.Bar (but not Foo.Bob) are used by Baz.Boz.

This is the code used to calculate the usage map:

// builds Id => links that link to Id or one of Id's children (by prefix)
public IDictionary<string, IList<Link>> CalculateUsageMap()
{
    var all = All();
    var links = all.Values
        .SelectMany(o => o.Links ?? Enumerable.Empty<Link>())
        .ToList();
    return all.Keys.ToDictionary(i => i, i => links.Where(k => IsLinkedTo(k, i)).ToList());
    // this last line is very slow
}

private static bool IsLinkedTo(Link link, string candidateId)
{
    return !string.IsNullOrEmpty(link.TargetId)
        && !string.IsNullOrEmpty(candidateId)
        && link.TargetId.StartsWith(candidateId, StringComparison.Ordinal);
}

This is the supporting structure behind it:

public interface ILinkable
{
    string Id { get; }
    IEnumerable<ILinkable> Children { get; }
    IEnumerable<Link> Links { get; }
}

public class Link
{
    public string Name { get; }
    public ILinkable Source { get; } // our immediate owner
    public string TargetId { get; }
    // plus constructors etc that's irrelevant at present
}

public ILinkable Root { get; }

public IDictionary<string, ILinkable> All()
{
    var tree = new Dictionary<string, ILinkable>();
    AddWithDescendants(tree, Root);
    return tree;
}

private static void AddWithDescendants(IDictionary<string, ILinkable> tree, ILinkable obj)
{
    tree.Add(obj.Id, obj);

    foreach (var child in obj.Children ?? Enumerable.Empty<ILinkable>())
    {
        AddWithDescendants(tree, child);
    }
}

This works, but in a tree with ~14k objects and ~3k links (producing ~20k usages) this takes ~5s to generate, which is longer than I'd like. (I've checked and All() and calculating links takes basically no time; it's all being spent inside ToDictionary.)

Is there some way to improve performance of this line? My first thought was using something like GroupJoin, but since we're "joining" on prefix-equality rather than actual equality that doesn't really work. I would prefer to keep this in pure code, not involving a database.

(I did attempt to write a custom equality comparer for GroupJoin but this ended up being both slower and producing the wrong results, with only ~7k of usage output. And it's dubious anyway since this is an asymmetric match, while equality comparers assume symmetry.)

Answer 1

The time complexity of this code

return all.Keys.ToDictionary(i => i, i => links.Where(k => IsLinkedTo(k, i)).ToList());

is quadratic O(N*M), where N is all.Keys.Count and M is links.Count. So not surprisingly it is slow.

Since what you are trying to achieve is essentially finding all ILinkable.Id being prefix of Link.TargetId, you need an efficient data structure optimized for such operation. Such data structure exists and is called Prefix tree. Following is a quick implementation for your case:

class ItemMap : IReadOnlyCollection<KeyValuePair<string, IReadOnlyList<Link>>>
{
    class Node
    {
        public Node(char key) => Key = key;
        public char Key { get; }
        public NodeMap Children;
        public ILinkable Item;
        public List<Link> Links;
        public IReadOnlyList<Link> ItemLinks => Links ?? (Item != null ? NoLinks : null);
        public static IReadOnlyList<Link> NoLinks => Array.Empty<Link>(); 
    }

    struct NodeMap
    {
        Dictionary<char, Node> items;
        public IEnumerable<Node> Items => items?.Values;
        public bool TryGetItem(char key, out Node item, bool create = false)
        {
            item = null;
            if ((items == null || !items.TryGetValue(key, out item)) && create)
                (items ?? (items = new Dictionary<char, Node>())).Add(key, item = new Node(key));
            return item != null;
        }
    }

    NodeMap RootNodes;

    IEnumerable<Node> Nodes
        => RootNodes.Items?.Expand(e => e.Children.Items) ?? Enumerable.Empty<Node>();

    IEnumerable<Node> ItemNodes
        => Nodes.Where(n => n.Item != null);

    IEnumerable<KeyValuePair<string, IReadOnlyList<Link>>> Items
        => ItemNodes.Select(n => new KeyValuePair<string, IReadOnlyList<Link>>(n.Item.Id, n.ItemLinks));

    public ItemMap(ILinkable tree)
    {
        if (tree == null) return;
        var items = new[] { tree }.Expand(e => e.Children);
        foreach (var item in items)
            AddItem(item);
        var links = Nodes.Where(n => n.Item?.Links != null).SelectMany(n => n.Item.Links);
        foreach (var link in links)
            AddLink(link);
    }

    void AddItem(ILinkable item)
    {
        var node = GetNode(item.Id, create: true);
        if (node == null) return;
        if (node.Item != null) throw new Exception($"Duplicate key: {item.Id}");
        node.Item = item;
        Count++;
    }

    void AddLink(Link link)
    {
        var key = link.TargetId;
        if (string.IsNullOrEmpty(key)) return;
        ref var nodes = ref RootNodes;
        for (int i = 0; i < key.Length; i++)
        {
            if (!nodes.TryGetItem(key[i], out var node)) break;
            // Add to each item in the prefix path
            if (node.Item != null && node.Item != link.Source)
                (node.Links ?? (node.Links = new List<Link>())).Add(link);
            nodes = ref node.Children;
        }
    }

    Node GetNode(string key, bool create = false)
    {
        if (string.IsNullOrEmpty(key)) return null;
        Node node = null;
        ref var nodes = ref RootNodes;
        for (int i = 0; i < key.Length; i++)
        {
            if (!nodes.TryGetItem(key[i], out node, create)) break;
            nodes = ref node.Children;
        }
        return node;
    }

    public int Count { get; private set; }

    public IEnumerator<KeyValuePair<string, IReadOnlyList<Link>>> GetEnumerator() => Items.GetEnumerator();

    IEnumerator IEnumerable.GetEnumerator() => GetEnumerator();
}

(Note: Instead of recursive tree traversals, in many places I use the generic DRY Expand method from my answer to How to flatten tree via LINQ?))

All the hard work happens in the class constructor. The first pass adds all items to the prefix tree. Then the second pass associates the links with each item. The first operation is O(N), second is O(M), so the overall is O(M+N), i.e. linear and much faster than the original.

Now you can easily build the desired dictionary (I've changed the interfaces to their ReadOnly variants):

public IReadOnlyDictionary<string, IReadOnlyList<Link>> CalculateUsageMap()
    => new ItemMap(Root).ToDictionary(e => e.Key, e => e.Value);

But note that this is not even needed, because the prefix tree can be used effectively as dictionary. Implementing the read only dictionary interface is quite easy - change the class declaration to

class ItemMap : IReadOnlyDictionary<string, IReadOnlyList<Link>> 

and add the following few lines inside

public IEnumerable<string> Keys => Items.Select(e => e.Key);

public IEnumerable<IReadOnlyList<Link>> Values => Items.Select(e => e.Value);

public IReadOnlyList<Link> this[string key]
    => TryGetValue(key, out var value) ? value : throw new KeyNotFoundException();

public bool ContainsKey(string key) => TryGetValue(key, out _);

public bool TryGetValue(string key, out IReadOnlyList<Link> value)
    => (value = GetNode(key)?.ItemLinks) != null;

Now you can remove the ToDictionary call:

public IReadOnlyDictionary<string, IReadOnlyList<Link>> CalculateUsageMap()
    => new ItemMap(Root);

---

The above prefix tree implementation use Dictionary<char, Node> for child node list storage/traversal. This might use much more memory. Since the whole implementation is encapsulated in NodeMap, you can experiment with different data structures and measure the performance and memory usage.

For instance, the following is another implementation which uses null, single Node or sorted List<Node> as storage, and binary search for locating the Node by key in the sorted list:

struct NodeMap
{
    object items; // null, Node or sorted List<Node>
    public IEnumerable<Node> Items => items is Node node ? new[] { node } : items as IEnumerable<Node>;
    public bool TryGetItem(char key, out Node item, bool create = false)
    {
        item = null;
        if (items == null)
        {
            if (create) items = item = new Node(key);
        }
        else if (items is Node node)
        {
            if (node.Key == key) item = node;
            else if (create) items = node.Key < key ? new List<Node>(2) { node, (item = new Node(key)) } : new List<Node>(2) { (item = new Node(key)), node };
        }
        else
        {
            var nodeList = (List<Node>)items;
            int lo = 0, hi = nodeList.Count - 1;
            while (lo <= hi)
            {
                int mid = lo + ((hi - lo) >> 1);
                node = nodeList[mid];
                if (node.Key == key) { item = node; break; }
                if (node.Key < key) lo = mid + 1; else hi = mid - 1;
            }
            if (item == null && create) nodeList.Insert(lo, item = new Node(key));
        }
        return item != null;
    }
}

Answer 2

Just for reference, here is the version of NodeMap from Ivan's answer which uses the built-in List<T>.BinarySearch instead:

struct NodeMap
{
    object items; // null, Node or sorted List<Node>
    private static readonly IComparer<Node> NodeComparer
        = Comparer<char>.Default.SelectComparer((Node n) => n.Key);
    public IEnumerable<Node> Items => items is Node node
        ? new[] { node } : items as IEnumerable<Node>;
    public bool TryGetItem(char key, out Node item, bool create = false)
    {
        item = null;
        if (items == null)
        {
            if (create) items = item = new Node(key);
        }
        else if (items is Node node)
        {
            if (node.Key == key) item = node;
            else if (create) items = node.Key < key
               ? new List<Node>(2) { node, (item = new Node(key)) }
               : new List<Node>(2) { (item = new Node(key)), node };
        }
        else
        {
            var nodeList = (List<Node>)items;
            var newNode = new Node(key);
            var index = nodeList.BinarySearch(newNode, NodeComparer);
            if (index >= 0) item = nodeList[index];
            else if (create) nodeList.Insert(~index, (item = newNode));
        }
        return item != null;
    }
}

Note that here I'm using a helper class to generate an IComparer<Node> from a lambda; equivalently you can make Node implement IComparable<T> (although that might be very slightly slower, apparently?).

Also interesting is that I also tried an alternative version which always created the List<Node> instead of supporting leaf Nodes (eliminating the middle branch), but that doubled the time from ~0.10s to ~0.20s. Which would still be good enough, but might as well go with the fastest option.

---

One more variation: since my ids are dotted-path segments that are atomic (ie. I only care about path-segment prefixes, not path-substring prefixes), I tried using string keys split at the segment level instead; replacing NodeMap like so:

struct NodeMap
{
    object items; // null, Node or sorted List<Node>
    private static readonly IComparer<Node> NodeComparer
        = StringComparer.Ordinal.SelectComparer((Node n) => n.Key);
    public IEnumerable<Node> Items => items is Node node
        ? new[] { node } : items as IEnumerable<Node>;
    public bool TryGetItem(string key, out Node item, bool create = false)
    {
        item = null;
        if (items == null)
        {
            if (create) items = item = new Node(key);
        }
        else if (items is Node node)
        {
            if (node.Key == key) item = node;
            else if (create) items = StringComparer.Ordinal.Compare(node.Key, key) < 0
                ? new List<Node>(2) { node, (item = new Node(key)) }
                : new List<Node>(2) { (item = new Node(key)), node };
        }
        else
        {
            var nodeList = (List<Node>)items;
            var newNode = new Node(key);
            var index = nodeList.BinarySearch(newNode, NodeComparer);
            if (index >= 0) item = nodeList[index];
            else if (create) nodeList.Insert(~index, (item = newNode));
        }
        return item != null;
    }
}

And then in AddLink/GetNode changed the key loop to:

foreach (var segment in key.Split('.'))

This has now improved performance again (back to ~0.05s, similar to Ivan's original dictionary-based version). And while I haven't verified all the entries, it's producing the same number of results as the "known good" version so it should still be correct.