2
\$\begingroup\$

Alright, well the title doesn't really explain anything, so I'll show a pared down version of my code:

class Handler {
    Dictionary<object, Leaf> AllItems = new Dictionary<object, Leaf>(); //This list

    Leaf RootLeaf = new Leaf();
    public void Add (object obj)
    {
        Leaf AddedTo = RootLeaf.Add(obj); //Adds to a leaf, then returns the leaf it was added to
        AllItems.Add(obj, AddedTo); //adds references to the obj and the leaf it's in.
    }
}

class Leaf {
    private Leaf _Parent;
    public Leaf SubLeaf;
    public List<object> Children = new List<object>();

    public Leaf (Leaf parent)
    {
        this._Parent = parent;
    }

    public void Add (object obj)
    {
        if (Children.Count > 5)
        {
            SubLeaf = new Leaf();
            return SubLeaf.Add(obj); //recursively return the reference to the end leaf
        }
        Children.Add(obj);
        return this; //start the recursive return
    }

    public Leaf Parent { get { return this._Parent; } }
}

Note: The above isn't real code, just an example of what I plan to do.

So the idea of the above is to organize all the items into leaves, but I need a quick way to loop through every object, and its leaf. Would doing the above (storing a reference of every object & its parent in a list in the Handler class) cause a drop in performance? Or would there be a better way to do this?

I hope this was clear enough, if not, please ask any questions.

\$\endgroup\$
2
  • \$\begingroup\$ Are you really going to allow any object to be a key to the Dictionary<object, Leaf>? \$\endgroup\$
    – neontapir
    Nov 21 '11 at 18:28
  • \$\begingroup\$ It is actually a interface that others inherit from, but for the basic example, an object would suffice just as well \$\endgroup\$
    – Ben
    Nov 21 '11 at 22:45
3
\$\begingroup\$

Well, it's not a tree, it's a linked list, and it won't work properly for more than seven items. After that you will overwrite the SubLeaf variable in the first node, and previously added items will be removed from the list, and AllItems will contain lost items with disowned nodes.

To make the list work you have to check if the node has a next node before creating a new one.

public class Node {

  private Node _next;
  private List<object> _items;

  public Node Previous { get; private set; }

  public Leaf (Leaf previous) {
    _previous = previous;
    _next = null;
    _items = new List<object>(6);
  }

  public void Add(object obj) {
    if (_items.Count == 6) {
      if (_next == null) {
        _next = new Leaf(this);
      }
      return _next.Add(obj);
    }
    _items.Add(obj);
    return this;
  }

}

Note: Consider using an array in the node instead of a list. Creating a list that uses lists seems redundant...

Also, keeping a reference to the last node in the handler would help when you want to add nodes, so that you don't have to loop through all nodes each time.

Putting the objects and their nodes in a list is not needed for looping through them, as you already have all the nodes and the objects. Adding the list would roughly tripple the memory usage and the time to add an item. You would only need another list if you need two completely different ways of accessing the items, for example both predictable enumerating and hash lookup.

To enumerate the list as pairs of objects and nodes, you can put an enumerator in the Node class which gets all objects and their nodes from the current node and forward, so you just use it on the first node to get all objects:

public IEnumerable<KeyValuePair<object,Node>> GetAll() {
  Node node = this;
  while (node != null() {
    foreach (object obj in node._items) {
      yield return new KeyValuePair<object,Node>(obj, node);
    }
    node = node._next;
  }
}
\$\endgroup\$
7
  • \$\begingroup\$ I'm sorry, I mis-wrote the example code above (and you are correct). My question was more along the lines of "Does using a list (in this case called AllItems) in the Handler class that stores references to all of the items I have hurt performance?". \$\endgroup\$
    – Ben
    Nov 21 '11 at 9:12
  • \$\begingroup\$ I added some notes on performanc above. \$\endgroup\$
    – Guffa
    Nov 21 '11 at 11:35
  • \$\begingroup\$ Thanks for the feedback, so holding a List of every item added to sub nodes (and their sub nodes, etc) would greatly damage performance, though would it hurt it to the point that looping through every node and retrieving every item would be a better alternative? And this is an implementation for a video game, so performance is (in this case) more important then memory, though memory could still be a problem with many items. \$\endgroup\$
    – Ben
    Nov 21 '11 at 18:51
  • \$\begingroup\$ And FYI, the IEnumerable is a gorgeous piece of code, but what if there are multiple sub-nodes per node? Sorry for dragging this on, but hopefully you can help me iron out the performance issues in this bit of code. \$\endgroup\$
    – Ben
    Nov 21 '11 at 18:53
  • \$\begingroup\$ @mazzzzz: Looping the nodes would be rougly as fast as looping the items in a dictionary, and at no memory cost. You should define what you really need to do with your collection, so that you can pick one that does that fast. \$\endgroup\$
    – Guffa
    Nov 21 '11 at 20:01

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.