java - n-body Simulation 预期性能 barnes hut

Question

我首先使用蛮力进行了 2D n 体模拟，但随后遵循 http://arborjs.org/docs/barnes-hut我已经实现了 Barnes-Hut 近似算法。然而，这并没有给我我想要的效果。

例如:

巴恩斯小屋 -> 2000 具尸体；平均帧时间32 毫秒和 5000； 164 毫秒

蛮力 -> 2000 具尸体；平均帧时间31 毫秒和 5000； 195 毫秒

这些值是关闭渲染的。

我是否正确地假设我没有正确实现算法，因此没有获得性能的显着提高？

Theta 当前设置为 s/d < 0.5。将此值更改为例如1 确实提高了性能，但很明显为什么这不是首选。

单线程

我的代码大致如下:

while(!close)
    {
        long newTime = System.currentTimeMillis();
        long frameTime = newTime-currentTime;
        System.out.println(frameTime);
        currentTime = newTime;

        update the bodies
    }

在更新主体的函数中:

first insert all bodies into the quadtree with all its subnodes
for all bodies
    {
        compute the physics using Barnes-Hut which yields a net force per planet (doPhysics(body))
        calculate instantaneous acceleration from net force
        update the instantaneous velocity
    }

barneshut 函数:

doPhysics(body)
{
    if(node is external (contains 1 body) and that body is not itself)
    {
        calculate the force between those two bodies

    }else if(node is internal and s/d < 0.5)
    {
        create a pseudobody at the COM with the nodes total mass
        calculate the force between the body and pseudobody

    }else (if is it internal but s/d >= 0.5)
    {
        (this is where recursion comes in)
        doPhysics on same body but on the NorthEast subnode
        doPhysics on same body but on the NorthWest subnode
        doPhysics on same body but on the SouthEast subnode
        doPhysics on same body but on the SouthWest subnode
    }
}

实际计算力:

calculateforce(body, otherbody)
{
    if(body is not at exactly the same position (avoid division by 0))
    {
        calculate force using newtons law of gravitation in vector form

        add the force to the bodies' net force in this frame
    }
}

Answer 1

您的代码仍然不完整(请阅读 SSCCE s )，深入调试不完整的代码不是该站点的目的。然而，这就是我接下来要确定什么是错误的(如果有的话)的方法:

• 只您担心的函数(我们称之为 barnes_hutt_update())；而不是整个更新循环。将其与等效的非 B-H 代码进行比较，而不是与没有 B-H 的整个更新循环进行比较。这将导致更有意义的比较。
• 您似乎将 s/d 0.5 硬编码到您的算法中。将其作为参数，当它设置得更高时，您应该能够注意到加速；如果设置为 0，则性能与原始的非 B-H 实现非常相似。B-H 中的加速来自评估较少的节点(因为远距离节点集中在一起)；你知道你要跳过多少个节点吗？ 没有跳过的节点，就没有加速。另一方面，跳过节点会在计算中引入小错误 - 你量化这些错误了吗？
• 在线查看 B-H 的其他实现。 D3 的 force layout在内部使用它，并且非常可读。有多个现有的四叉树实现。如果您已经构建了自己的，它们可能不是最佳的(甚至是错误的)。除非您尝试边做边学，否则最好使用经过测试的库而不是自己动手。
• 减速可能是由于使用了四叉树，而不是力加法本身。与 B-H 力近似本身相比，了解构建和更新四叉树所花费的时间会很有用——因为在这种情况下，四叉树是纯粹的开销。 B-H 需要四叉树，但朴素的非 B-H 实现不需要。对于少量节点，naive 会更快(但随着添加的节点越来越多，速度会变得非常快)。 当您添加越来越多的主体时，性能如何扩展？
• 您是否正在创建和丢弃大量对象？您可以通过使用 memory pool 使您的算法避免相关的开销(是的，大量新闻 + 垃圾收集会导致显着的减速) .