CODEWITHSUNDEEP
c#recursiondictionary
Dmitrii Erokhin
Dmitrii Erokhin

Reputation: 1347

Why is dictionary lookup slower than recursive search?

I was trying to optimize a search for a node in a TreeNodeCollection. The original method uses recursive approach:

public UGTreeNode FindNode(BaseId nodeId, TreeNodeCollection nodes)
{
    foreach (UGTreeNode n in nodes)
    {
        if (n.node_info.Description.base_id.Id == nodeId.Id &&
            n.node_info.Description.base_id.RootId == nodeId.RootId &&
            n.node_info.Description.base_id.SubId == nodeId.SubId)
            return n;
        UGTreeNode n1 = FindNode(nodeId, n.Nodes);
        if (n1 != null)
            return n1;
    }
    return null;
}

I tried storing all nodes in a Dictionary and use Dictionary.TryGetValue to search for a node:

public UGTreeNode FindNode(BaseId nodeId, TreeNodeCollection nodes)
{
    UGTreeNode res;
    _nodesCache.TryGetValue(nodeId.Id, out res);
    return res;
}

But it turns out that the second approach is way slower than the first (appoximately 10 times slower). What are the possible reasons for this?

Upvotes: 2

Views: 164

Answers (1)

Stefan Steinegger
Stefan Steinegger

Reputation: 64658

The recursion may be faster when you always search for one of the first items in the tree. It also depends on the Equals implementation of the BaseId or the comparer you use in the dictionary. In the recursive method, you have reference comparison. The dictionary uses the GetHashCode and Equals.

How did you measure the performance?

Upvotes: 1

Related Questions