c# - 数万个粒子的更快嵌套循环

问题描述

我正在 Unity 环境中进行一些视觉艺术研究。我正在尝试实现与此处解释的差分线增长非常相似的东西，但我主要担心的是，在算法的某个地方，每个节点都应该检查每个其他节点，看看它有多接近，并从所有这些中构造一个排斥力数组附近的粒子。

这是我的代码片段：

   public void Differentiate()
    {
        int c = nodes.Count;                                 
        Vector3[] repulsionForces = new Vector3[c];

        for (int i = 0; i < c ; i++)
        {

            // Construct nearbies
            List<DifferentialNode> nearby = new List<DifferentialNode>();
            foreach(DifferentialNode n in nodes)
            {
                float d = Vector3.Distance(n.position, nodes[i].position);
                if (d < 5)
                {
                    nearby.Add(n);
                }
            }
            // Get Forces
            Vector3 repulsionForce = nodes[i].RepulsionForce(nearby);

            // Limit Forces
            repulsionForce = Vector3.ClampMagnitude(repulsionForce, maxForce);

            // Apply Multipliers
            repulsionForce *= Repulsion;

            // Put Forces into Array
            repulsionForces[i] = repulsionForce;
        }

        for (int i = 0; i < c; i++)
        {
            nodes[i].applyForce(repulsionForces[i]);
            nodes[i].update();
            nodes[i].velocity = new Vector3(0, 0, 0);
        }

这是我在 DifferentialLineNode 类中的 RepulsionForce() 函数

public Vector3 RepulsionForce(List<DifferentialNode> nearby)
{
    Vector3 repulsionForce = new Vector3();

    foreach (DifferentialNode n in nearby)
    {
        // calculate distance between both
        float d = Vector3.Distance(n.position, this.position);
        // calculate difference and divide by exp(d) to get less influence when far
        Vector3 diff = ( this.position - n.position ) / (Mathf.Exp(d)); 
        repulsionForce += diff;
    }
    repulsionForce /= (float)nearby.Count;
    repulsionForce.Normalize();

    return repulsionForce;
}

一旦我开始游戏，一切都会降到 1fps 以下，我认为嵌套循环是它的来源，因为它具有 n^n 的复杂性。我一直在研究 Octree / KdTree 实现，但找不到任何解释代码。还有其他路线吗？超过一个？可以任意组合吗？非常感谢

标签： c#unity3dnested-loopskdtree

解决方案

每个点计算距离内的点是O(n^2)，所以如果粒子数量很大，性能下降并不奇怪。但这可以很容易地改进。可以使用的搜索结构有几个选项：

3D 网格。这应该很容易实现，只需创建一个 3D 列表数组。选择一个合适的 bin 大小，以便您有固定数量的 bin 进行迭代。这样做的主要缺点是内存使用，如果在您的模拟中有没有粒子的大空隙，这将更加重要。
稀疏八叉树。如果点的间距不均匀，则与网格相比的主要优势将是更好的内存使用。如果您需要搜索任意距离，它也会更好地扩展。缺点将是更复杂的实现。
Kd树。这是一个非常好的数据结构，因为它使用的内存很少，可以用连续的内存实现，并且可以很好地扩展。一个缺点是难以处理位置的变化。实现也比网格更复杂。

对于网格或八叉树，可以在 bin 之间移动点。对于 kd 树，重建树可能会更好。任何选项都应将搜索时间从 O(N^2) 减少到 O(n log n)。

鉴于您的问题的上下文，我建议从一个简单的 3D 网格开始。如果这还不够，我会考虑使用 kd 树。我会避免组合数据结构，除非有特定的理由这样做。八叉树和 kdtree 应该可以很好地扩展。

我建议尝试一些分析工具来检查实际需要时间。我还建议设置一些受控环境以在已知数据集上运行算法并测量时间。Benchmark.Net是黄金标准，但在测量较大的变化时，一个简单的秒表应该是相当不错的。

还应该有一些微优化的机会。避免在紧密循环中创建列表，如果需要，创建一个可重复使用的列表。避免重复操作。避免昂贵的操作。比其他集合更喜欢数组和列表，因为运行时对这些有特殊的优化。首选for而不是foreach因为前者可以避免创建迭代器对象。

c# - 数万个粒子的更快嵌套循环

问题描述

解决方案

推荐阅读