logo标签列表

递归方法比迭代方法慢10倍。

c#recursionrhino
3
我会尽力清理代码以展示我的问题。基本上，它是一个八叉树搜索与相交的结合体。相交函数来自SDK（整个项目是Rhino插件）。如果我使用相交调用循环，它比递归搜索快10倍。更奇怪的是，在递归中隔离相交调用的时间较慢，比循环慢8倍。可能有1000种原因导致它表现如此，但我希望我能在代码上犯了一些显而易见的错误，有人可以通过查看代码发现。
这里是缓慢的递归部分：
public void NewRayCast()
{            
    int runs = 500000;                          //how many rays we cast
    Point3d raypos = new Point3d(0, 0, 0);      //raystart
    Ray3d ray = new Ray3d();                

    Random r = new Random();                    //here we create targets to scatter the ray directions
    Vector3d[] targets = new Vector3d[runs];
    for (int i = 0; i < runs; i++)
    {
        targets[i] = new Vector3d(r.NextDouble() * 200 - 100, 500, r.NextDouble() * 200 - 100);
    }

    for (int i = 0; i < runs; i++)
    {
        boxes = new List<int>();            // this collects the octree leaves the rays hits
        rayline.From = ray.Position;
        rayline.To = ray.Position + ray.Direction;                
        LineBoxer(starter);                 // this starts the raycasting - starter is a array with 1 value (the scene bounding box)
    }            
}

public void LineBoxer(int[] check)    // Cast a ray against boxes
{            
    for (int i = 0; i < check.Length; i++)  // check only because the first call is with the scene box (1 index)
    {
        if (octmanB.node[check[i]].closed == false) // if node is a dead end > empty we skip it
        {                                       
            isect = Rhino.Geometry.Intersect.Intersection.LineBox(rayline, octmanB.node[check[i]].bbox, 0, out ival); // intersection function, changing to an arbitrary bounding box doesnt speed it up either                    
            if (isect == true)
            {                        
                if (octmanB.node[check[i]].leaf == false)   // continue with recursion
                {
                    LineBoxer(octmanB.node[check[i]].child);
                }
                else
                {
                    boxes.Add(check[i]);    // here we have a leaf
                }
            }
        }
    }
}

这里是更快的方法：

public void FasterTestRun()
{
    int runs = 500000;                       
    Line line = new Line(new Point3d(1, 1, 1), new Point3d(0, 1000, 0));
    BoundingBox box = new BoundingBox(new Point3d(-50, 50, -50), new Point3d(50, 150, 50));

    bool isect;
    Interval v = new Interval();

    Random r = new Random();
    Point3d[] targets = new Point3d[runs];
    for (int i = 0; i < runs; i++)
    {
        targets[i] = new Point3d(r.NextDouble() * 20 - 10, 1000, r.NextDouble() * 20 - 10);
    }

    for (int i = 0; i < runs; i++)
    {
        line.To = targets[i];                
        isect = Rhino.Geometry.Intersect.Intersection.LineBox(line, box, 0, out v);                
    }            
}

感谢您的信任！
递归方法调用总是比迭代调用更快。这仅仅是因为当离开方法时，所有的方法数据都被推送到堆栈中。内部调用返回时会分配和释放新的内存。使用迭代时不需要执行这些操作。 - Carsten
1
@Aschratt难道他没有说明迭代方法比其他方法快10倍吗？ - Nathan White
我认为@Aschratt打错了字，他的陈述表明递归方法由于堆栈分配/释放而真正变慢。好奇的是时间是在发布版还是调试版中完成的，因为在调试模式下可能会加剧这个问题。 - David Hope
抱歉，我搞混了... 我的意思是递归调用比较慢 :D - Carsten
2
你尝试使用 LineBoxer(ref int[] check) 方法了吗？你也在多次迭代数组，所以要创建一个变量 var checkI = check[i]; 和 var nodeI = octmanB.node[checkI];！ - metadings
显示剩余5条评论
1个回答
5

现在我在家，终于可以回答你的问题了，让我们开始吧...

递归

首先：如果你使用结构化编程语言，递归总是比迭代慢。你不能一概而论，因为在函数式编程语言中，函数调用更快（函数在那里定义得不同）。有关更多信息，请参见Wikipedia。

详细来说，递归调用会将函数（或方法）分配的所有本地变量推送到堆栈上，等待内部调用返回（这包括同一个过程一遍又一遍...），最后从调用堆栈中弹出值并继续使用它们。这不仅是重负载内存，也是垃圾收集器的痛点：你的函数必须等待的时间越长，你的对象就在内存中存活的时间就越长，变老并最终达到gen1或gen2。这意味着它们实际上要花很长时间才能被释放。

我看到的另一个问题是：

public void LineBoxer(int[] check)
{
    // ...
    LineBoxer(octmanB.node[check[i]].child);
    // ...
}

递归传递数组意味着该数组的所有值都在堆栈上停留了很长时间。即使大多数元素已准备好被释放！如果您以迭代方式执行相同的操作，则不会对堆栈施加压力。分配的变量通常是临时变量，并且可以很快得到释放。内存分配是瓶颈所在。这就是为什么我将继续更详细地讨论它的原因（以及因为你在评论中要求）。

理论上提高性能

但是（在评论中），您还要求如何更有效地处理光线跟踪。基本上，使用八叉树是正确的选择。您想要执行的基本操作是简单搜索。这就是问题所在。据我所了解，从您的代码来看，您正在测试每个八叉树叶子节点是否被击中：

public void LineBoxer(int[] check)    // Cast a ray against boxes
{            
    for (int i = 0; i < check.Length; i++)
    {
        // ...
    }
}

那只是搜索与您的射线相交的所有框的简单方法。但这不是引入树的动机。您可以将八叉树想象成在三个维度上扩展的二叉搜索树。二叉搜索树可以搜索一维条目（例如列表或数组）。要在二维构造中搜索信息，可以使用四叉树。现在我们需要添加另一个维度（因为我们现在处于3D状态），所以我们使用八叉树。
到目前为止还不错，但是树如何帮助我们执行“更好”的搜索操作呢？
这是因为分而治之原则。如果我们在较大的信息集中搜索特定内容，我们将该集合分成小块。我们这样做直到找到我们正在寻找的特定内容。
对于我们的八叉树来说，这意味着我们将一个立方体分成 8 个较小的立方体。现在我们测试每个盒子是否与我们的光线相交。在最好的情况下，它恰好与一个盒子相交。那就是要进一步检查的盒子。但如果每个盒子包含 1000 个盒子，我们只需通过一个额外的检查就可以摆脱 7000 次检查！
现在我们一遍又一遍地做这件事，直到我们找到一个或多个叶子节点。递归地执行这个过程不应该比迭代执行慢得多。想象一个有 100,000 个节点的八叉树。第一个立方体可以存储 8 个立方体，这 8 个立方体可以存储 64 个立方体（深度：2！），依此类推...
  • 深度 = 3：512 个立方体
  • 深度 = 4：4,096 个立方体
  • 深度 = 5：32,768 个立方体
  • 深度 = 6：262,144 个立方体
  • 深度 = 7：2,097,152 个立方体
  • ...
我们最多只需要检查 8 x 深度 个元素，如果我们正在搜索一个特定的盒子。因此，我们将算法的性能从 O(n) 提高到了 O(log(n))。1

好的，但如何将其应用于您的问题？

首先：您正在使用 C# - 一种面向对象的语言。所以使用对象！如果您将所有内容封装在对象结构中，则很容易将分治原则应用于您的树形结构。

在您的具体情况下，这意味着：

public class OctreeNode
{
    public bool IsLeaf { get; private set; }
    public OctreeNode[8] Children { get; private set; }

    public OctreeNode()
    {
        this.IsLeaf = true;
        this.Children = null;
    }

    // Don't forget to implement methods to build up the tree and split the node when required.
    // Splitting results in a tree structure. Inside the split-method 
    // you need to allocate the Children-Array and set the IsLeaf-Property to false.

    public bool Intersects(Line rayline, ref ICollection<OctreeNodes> Nodes)
    {
        Interval interval;

        // If the current node does not intersect the ray, then we do not need to
        // investigate further on from here.
        if (!Rhino.Geometry.Intersect.Intersection.LineBox(rayline, this.GetBoundingBox(), 0, out interval))
        {
            return false;
        }

        // If this is a leaf (in which we are interested in) we add it to 
        // the nodes-collection.
        if (this.IsLeaf)
        {
            Nodes.Add(this);
            return true;
        }

        // Not a leaf, but our box intersects with the ray, so we need to investigate further.

        for (int i = 0; i < 8; ++i)
        {
            // Recursive call here, but the result doesn't actually matter.
            this.Children[i].Intersects(rayline, Nodes)
        }

        // The ray intersects with our current node.
        return true;
    }
}

这将为您完成所有的魔法！它仅测试树，直到测试失败的深度，并继续直到您拥有与光线相交的所有叶子。您还可以按“谁获得了最长的交集间隔”对它们进行排序，以在流式传输时提高内部对象的优先级，但由于我现在完全无法掌握这个主题，所以我会继续：

您甚至可以通过应用并行性来进一步加速此算法。使用TPL非常简单，就像这里一样：

Parallel.For<int> (0; 8; i =>
{
    this.Children[i].Intersects(rayline, Nodes)
});

好的，目前为止就这些了。我希望这能帮助你和更多人。:)

注意：我对rhino3d不是很熟悉。也许有内置功能可以更好地帮助您解决问题！

注意2：请原谅我，如果我在某些方面不是100％正确，因为我已经有一段时间没有进行理论考虑了...

1在最好的情况下，我们正在搜索完全平衡树中的一个特定叶子。

你对递归的初步分析是错误的。向堆栈添加/删除值不会为GC创建大量负载。事实上，GC与分配/释放堆栈内存无关；它只关心堆内存的管理。分配/释放堆内存非常快。通过移动一个指针一次即可释放N字节的堆内存，这基本上是您可以执行的单个最便宜的操作。分配堆内存的成本仅取决于将字节写入堆栈所需的时间，这非常快。 - Servy
哇！非常感谢您的好解释！在过去的一个小时左右，我一直在搜索网络，并找到了一些不同的方法 - 线程（二叉）树，其中您可以不使用递归进行操作。我想我需要多读一些资料。再次感谢！ - atair
网页内容由stack overflow 提供, 点击上面的
可以查看英文原文，
原文链接