c# - 递归方法比交互式方法慢10倍

Question

This question is unlikely to help any future visitors; it is only relevant to a small geographic area, a specific moment in time, or an extraordinarily narrow situation that is not generally applicable to the worldwide audience of the internet. For help making this question more broadly applicable, visit the help center。
                            
                        
                    
                
                                6年前关闭。
            
                    
我已尽力清除代码以显示问题。
基本上是八叉树搜索+相交。
相交函数来自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);                
    }            
}

谢谢！

最佳答案

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

递归

首先：如果使用结构化编程语言，则递归总是比迭代慢。您不能一概而论，因为使用函数式编程语言进行的函数调用速度更快（此处的函数定义不同）。有关更多信息，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++)
    {
        // ...
    }
}

只需搜索所有与射线相交的盒子即可。但这不是引进树木的动机。您可以想象一个像 binary search tree的八叉树被扩展到3个维度。二叉搜索树可以搜索一维条目（例如列表或数组）。要以二维结构搜索信息，可以使用 quadtrees。现在我们需要添加另一个尺寸（因为我们现在处于3D模式），因此我们使用 octrees。

到目前为止，一切都很好，但是树如何帮助我们“更好”地执行搜索操作？

这是因为 divide and conquer priciple。如果我们要在较大的信息集中搜索特定的内容，则会将信息集分成几小段。我们会一直这样做，直到找到所需的特定东西。

对于八叉树，这意味着我们将一个多维数据集划分为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在最佳情况下，我们要在完全平衡的树中搜索一片特定的叶子。

关于c# - 递归方法比交互式方法慢10倍，我们在Stack Overflow上找到一个类似的问题： https://stackoverflow.com/questions/15139871/

上一篇：c# - 受密码保护的 SQLite 数据库

下一篇：C# 简单列表显示的问题

相关文章：

javascript - 如何从 javascript 中获取 Rhino 的版本？

c# - 如何以编程方式设置附加属性？

c# - Excel VSTO 加载项部署错误

c# - WhereIn 动态属性

c++ - main 的递归

python - 尝试编写递归函数来迭代嵌套字典时出现 RecursionError

c# - Win 7 DllImport C# 奇怪的错误，对内存位置的访问无效？

java - 递归生成ASCII二叉树

java - 是否可以在 Java 6 中为 RhinoScriptEngine 设置优化级别？

javascript - Rhino:能够暂停、保存状态和恢复 javascript

Answer 1

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

递归

首先：如果使用结构化编程语言，则递归总是比迭代慢。您不能一概而论，因为使用函数式编程语言进行的函数调用速度更快（此处的函数定义不同）。有关更多信息，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++)
    {
        // ...
    }
}

只需搜索所有与射线相交的盒子即可。但这不是引进树木的动机。您可以想象一个像 binary search tree的八叉树被扩展到3个维度。二叉搜索树可以搜索一维条目（例如列表或数组）。要以二维结构搜索信息，可以使用 quadtrees。现在我们需要添加另一个尺寸（因为我们现在处于3D模式），因此我们使用 octrees。

到目前为止，一切都很好，但是树如何帮助我们“更好”地执行搜索操作？

这是因为 divide and conquer priciple。如果我们要在较大的信息集中搜索特定的内容，则会将信息集分成几小段。我们会一直这样做，直到找到所需的特定东西。

对于八叉树，这意味着我们将一个多维数据集划分为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在最佳情况下，我们要在完全平衡的树中搜索一片特定的叶子。