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.

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;
    }
}

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.