Оптимизация рекурсивного извлечения информации?


Я написал небольшой класс, который показывает моя проблема:

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

Я побежал через Profiler муравьев, и это не удивительно вытащил лист.getAllChildren и листьев.getChildCount как два самых дорогих операций. Я ок с тем, как все остальное выложено. Мой вопрос: как я могу оптимизировать два вышеупомянутых свойства?

Свойства вызываются, когда корень.Обновление() функция выполняется.



413
5
задан 23 ноября 2011 в 02:11 Источник Поделиться
Комментарии
2 ответа

Ладно, я сделал немного работы здесь (хорошо большинство из них стилистические, будьте уверены). Обратите внимание, Я заменил объект с обычную реализацию, чтобы помочь избежать бокса типов значений. Он также использовать LINQ в пару инстанций, чтобы удалить некоторые сложности. Когда я запустить его и произвести 1,000,000 число листьев, я считаю, что основная масса времени уходит в конструкторах класса и сами методы достаточно близки к 0 времени следует считать 0. Надеюсь, что это помогает:

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

2
ответ дан 23 ноября 2011 в 03:11 Источник Поделиться

То, что я увидел, когда быстро взглянув на него:

Соглашение об именовании: некоторые из ваших свойств и переменных lowerCamelCase, некоторые UpperCamelCase, некоторые переменные имеют подчеркивания, некоторые нет. Некоторые объекты называются о, какой параметр obj.

Вот основные правила именования предложил для C#:


  • Переменные lowerCamelCase: переменная

  • Свойства UpperCamelCase: свойства myproperty

  • Методы и функции UpperCamelCase: myfunction в консоли

Придерживайтесь их, и не путайте их с конвенциями Ява, они совсем другие.


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

У нас есть некоторые интересные функции, документацию, сделать эту информацию легко доступной:

/// <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>();


Организуйте свои занятия лучше, что это одинокий статических случайных там делать между добавить и getChildCount функции?

static Random rand = new Random();


Вы никогда не инициализировать ChildLeaves переменной, насколько я вижу.

1
ответ дан 23 ноября 2011 в 11:11 Источник Поделиться