patterncsharpMinor

Optimize Recursive Fetching of information?

Submitted by: @import:stackexchange-codereview·Mar 10, 2026·

Viewed 0 times

fetchingrecursiveoptimizeinformation

Problem

I wrote a small class that demonstrates my problem:

```
class Root
{
private Leaf RootLeaf;
private Dictionary AllItems = new Dictionary(); //dictionary contains a reference to each item, and the leaf it is assigned to (its parent)
public Root()
{
RootLeaf = new Leaf();
}

public List 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 GetNeighbors(object obj)
{
foreach (object o in this.AllItems[obj].getAllChildren)
{
if (obj != o)
yield return o;
}
}

public void Update()
{
foreach (KeyValuePair 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 Children = new List();

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
/// Returns children of this leaf, and all of its subleaves
///
public List getAllChildren
{
get
{
List outp = Children.ToList();
if (HasLeaves)
{
foreach (Leaf l in ChildLeaves)
outp.AddRange(l.getAllChildren);
}
return outp;
}
}
///
/// Get count of all children in this leaf, and its subleaves
///
public int getChildCount
{
get
{
int outp = Ch

Solution

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
{
    private readonly Leaf rootLeaf = new Leaf();

    // dictionary contains a reference to each item, and the leaf it is assigned to (its parent)
    private readonly IDictionary> allItems = new Dictionary>();

    /// 
    /// Gets GetAllChildren.
    /// 
    public IList 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 GetNeighbors(T obj)
    {
        return this.allItems[obj].GetAllChildren.Where(o => ReferenceEquals(obj, o));
    }
}

internal class Leaf
{
    private const int MaxChildCount = 1;

    private static readonly Random rand = new Random();

    private readonly IList children = new List();

    private List> childLeaves;

    private bool hasLeaves; // Should we use the leaves?

    private bool leavesGenerated; // Have the leaves been created? (Low Level, do not touch)

    /// 
    /// Returns children of this leaf, and all of its subleaves
    /// 
    public IList GetAllChildren
    {
        get
        {
            var allChildren = this.children.ToList();

            if (this.hasLeaves)
            {
                this.childLeaves.ToList().ForEach(l => allChildren.AddRange(l.GetAllChildren));
            }

            return allChildren;
        }
    }

    /// 
    /// Get count of all children in this leaf, and its subleaves
    /// 
    public int GetChildCount
    {
        get
        {
            var allChildrenCount = this.children.Count;

            if (this.hasLeaves)
            {
                allChildrenCount += this.childLeaves.Sum(l => l.GetChildCount);
            }

            return allChildrenCount;
        }
    }

    /// 
    /// 
    /// 
    /// The object to be added
    /// The leaf the object was added to
    public Leaf Add(T o)
    {
        if (this.children.Count > { new Leaf(), new Leaf(), new Leaf(), new Leaf() };

            this.leavesGenerated = true;
        }

        this.hasLeaves = true;
    }

    protected void RemoveLeaves()
    {
        this.hasLeaves = false;
    }
}

Code Snippets

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 Lea

Context

StackExchange Code Review Q#6217, answer score: 2

Revisions (0)

No revisions yet.