Optimize Recursive Fetching of information?

Question

I wrote a small class that demonstrates my problem:

class Root
{
 private Leaf RootLeaf;
 private Dictionary<object, Leaf> AllItems = new Dictionary<object, Leaf>(); //dictionary contains a reference to each item, and the leaf it is assigned to (its parent)
 public Root()
 {
 RootLeaf = new Leaf();
 }
 public List<object> GetAllChildren
 {
 get { return RootLeaf.getAllChildren; }
 }
 public void Add(object o)
 {
 Leaf AddedTo = RootLeaf.Add(o);
 AllItems.Add(o, AddedTo); //Add object reference to AllItems dictionary
 }
 private IEnumerable<object> GetNeighbors(object obj)
 {
 foreach (object o in this.AllItems[obj].getAllChildren)
 {
 if (obj != o)
 yield return o;
 }
 }
 public void Update()
 {
 foreach (KeyValuePair<object, Leaf> i in AllItems)
 {
 foreach (object b in this.GetNeighbors(i.Key))
 {
 //Would do collision checks here
 }
 }
 }
}
class Leaf
{
 private const int MaxChildCount = 1;
 private List<object> Children = new List<object>();
 private Leaf[] ChildLeaves = null;
 private bool _LeavesGenerated = false; //Have the leaves been created? (Low Level, do not touch)
 private bool HasLeaves = false; //Should we use the leaves?
 protected void CreateLeaves()
 {
 if (!_LeavesGenerated)
 {
 //create each of the four leaves
 for (int i = 0; i < 4; i++)
 ChildLeaves[i] = new Leaf();
 _LeavesGenerated = true;
 }
 HasLeaves = true;
 }
 protected void RemoveLeaves()
 {
 HasLeaves = false;
 }
 /// <summary>
 /// Returns children of this leaf, and all of its subleaves
 /// </summary>
 public List<object> getAllChildren
 {
 get
 {
 List<object> outp = Children.ToList();
 if (HasLeaves)
 {
 foreach (Leaf l in ChildLeaves)
 outp.AddRange(l.getAllChildren);
 }
 return outp;
 }
 }
 /// <summary>
 /// Get count of all children in this leaf, and its subleaves
 /// </summary>
 public int getChildCount
 {
 get
 {
 int outp = Children.Count;
 if (HasLeaves)
 {
 foreach (Leaf l in ChildLeaves)
 outp += l.getChildCount;
 }
 return outp;
 }
 }
 static Random rand = new Random();
 /// <summary>
 /// 
 /// </summary>
 /// <param name="o">The object to be added</param>
 /// <returns>The leaf the object was added to</returns>
 public Leaf Add(object o)
 {
 if (Children.Count >= MaxChildCount)
 {
 //Pick random subleaf, I know this isn't correct for a quadtree, but it will simplify this explanation code
 if (!HasLeaves)
 CreateLeaves();
 return ChildLeaves[rand.Next(0, 3)].Add(o);
 }
 else
 {
 Children.Add(o);
 return this;
 }
 }
}

I ran this through the ANTS profiler, and it not surprisingly pulled the Leaf.getAllChildren and Leaf.getChildCount as the two most expensive operations. I'm ok with how everything thing else is laid out. My question is: how could I optimize the two aforementioned properties?

The properties are called when the Root.Update() function is run.

• Jesse C. Slicer: What is your test program that uses these classes that you're using to profile?
• Jess: I can post it if you feel it's relevent, but it's some 300+ lines, and after optimizing most of it, the profiler pointed out the lines that called the above properties (and the call count can't be reduced) as taking up 30% of the execution time. I'll see if I can trim it down to the important bits.
• Jess: Update, I've added what I think you were referring to, was that what you were talking about?
• Jesse C. Slicer: I don't think so? I'm looking for perhaps a Main() method which creates these objects and calls their methods.
• Jess: Oh, they are very simple functions, the first is on form.load and adds new objects, and the second runs on a every 1000/60 millisecs. I can also add that if you wish

Answer 1

All right, I've done a bit of work here (a good most of it stylistic, to be sure). Do note I replaced object with a generic implementation to help avoid boxing of value types. It does also employ LINQ in a couple instances to remove some complexity. When I run it and generate 1,000,000 integer leaves, I find that the bulk of the time is taken in the class constructors and the methods themselves are close enough to 0 time to be considered 0. Hope this helps:

internal sealed class Root<T>
{
 private readonly Leaf<T> rootLeaf = new Leaf<T>();
 // dictionary contains a reference to each item, and the leaf it is assigned to (its parent)
 private readonly IDictionary<T, Leaf<T>> allItems = new Dictionary<T, Leaf<T>>();
 /// <summary>
 /// Gets GetAllChildren.
 /// </summary>
 public IList<T> GetAllChildren
 {
 get
 {
 return this.rootLeaf.GetAllChildren;
 }
 }
 public void Add(T o)
 {
 var addedTo = this.rootLeaf.Add(o);
 this.allItems.Add(o, addedTo); // Add object reference to AllItems dictionary
 }
 public void Update()
 {
 foreach (var i in from i in this.allItems from b in this.GetNeighbors(i.Key) select i)
 {
 // Would do collision checks here
 }
 }
 private IEnumerable<T> GetNeighbors(T obj)
 {
 return this.allItems[obj].GetAllChildren.Where(o => ReferenceEquals(obj, o));
 }
}
internal class Leaf<T>
{
 private const int MaxChildCount = 1;
 private static readonly Random rand = new Random();
 private readonly IList<T> children = new List<T>();
 private List<Leaf<T>> childLeaves;
 private bool hasLeaves; // Should we use the leaves?
 private bool leavesGenerated; // Have the leaves been created? (Low Level, do not touch)
 /// <summary>
 /// Returns children of this leaf, and all of its subleaves
 /// </summary>
 public IList<T> GetAllChildren
 {
 get
 {
 var allChildren = this.children.ToList();
 if (this.hasLeaves)
 {
 this.childLeaves.ToList().ForEach(l => allChildren.AddRange(l.GetAllChildren));
 }
 return allChildren;
 }
 }
 /// <summary>
 /// Get count of all children in this leaf, and its subleaves
 /// </summary>
 public int GetChildCount
 {
 get
 {
 var allChildrenCount = this.children.Count;
 if (this.hasLeaves)
 {
 allChildrenCount += this.childLeaves.Sum(l => l.GetChildCount);
 }
 return allChildrenCount;
 }
 }
 /// <summary>
 /// 
 /// </summary>
 /// <param name="o">The object to be added</param>
 /// <returns>The leaf the object was added to</returns>
 public Leaf<T> Add(T o)
 {
 if (this.children.Count < MaxChildCount)
 {
 this.children.Add(o);
 return this;
 }
 // Pick random subleaf, I know this isn't correct for a quadtree, but it will simplify this explanation code
 if (!this.hasLeaves)
 {
 this.CreateLeaves();
 }
 return this.childLeaves[rand.Next(0, 3)].Add(o);
 }
 protected void CreateLeaves()
 {
 if (!this.leavesGenerated)
 {
 // create each of the four leaves
 this.childLeaves = new List<Leaf<T>> { new Leaf<T>(), new Leaf<T>(), new Leaf<T>(), new Leaf<T>() };
 this.leavesGenerated = true;
 }
 this.hasLeaves = true;
 }
 protected void RemoveLeaves()
 {
 this.hasLeaves = false;
 }
}

• Bobby: Nice work. Only one thing, can outp get a better name?
• Jesse C. Slicer: I don't see why not.
• Jess: One question I can't seem to figure out: How would I select both items in the collision foreach loop? If I wanted to do something like : if (Rect1.Intersects(Rect2)) where Rect1 was the first object, and Rect2 was its neighbor? With the nested foreach loops it was simple, take the outer variable, and the inner variable; I'm not sure how to do it with your LINQ though
• Jess: Also, would it be better to loop through each child every time I need that information, or should I store it in each leaf (like I do in the Root class), and just update it whenever a child changes leaves?

Answer 2

What I saw when quickly looking at it:

Naming convetion: Some of your Properties and variables are lowerCamelCase, some are UpperCamelCase, some of your variables have a leading underscore, some don't. Some objects are called o, some obj.

Here are the basic naming conventions proposed for C#:

• Variables are lowerCamelCase: myVariable
• Properties are UpperCamelCase: MyProperty
• Methods and Functions are UpperCamelCase: MyFunction

Stick to those, and don't confuse them with the Java conventions, they're quite different.

---

private Dictionary<object, Leaf> AllItems = new Dictionary<object, Leaf>(); //dictionary contains a reference... ... ...

We've got some cool documentation features available, make that information easily accessible:

/// <summary>
/// Contains a reference to each item, and the leaf it is assigned to (its parent).
/// </summary>
private Dictionary<object, Leaf> AllItems = new Dictionary<object, Leaf>();

---

Organize your classes better, what does that lone static Random do there between the Add and getChildCount functions?

static Random rand = new Random();

---

You never initialize the ChildLeaves variable as far as I can see.

• Jess: Thanks for the case information, I do need to follow that more closely. As for the underscore, I use it when I feel it is a low level type of function/variable, and it should never be called straight out, though that probably isn't the best way todo it...