从四叉树获取 N x N 维数据在 C# 中非常慢

Question

我在 c# 中为我的数据处理应用程序使用 四叉树 结构，它类似于 hashlife 算法。从四叉树获取 N x N（例如 2000 x 2000）维数据非常非常慢。
我如何优化它以从四叉树中提取大数据。

编辑：这是我用来以递归方式提取数据的代码

public int Getvalue(long x, long y)
{
    if (level == 0)
    {
        return value;
    }
    long offset = 1 << (level - 2);
    if (x < 0)
    {
        if (y < 0)
        {
            return NW.Getvalue(x + offset, y + offset);
        }
        else
        {
            return SW.Getvalue(x + offset, y - offset);
        }
    }
    else
    {
        if (y < 0)
        {
            return NE.Getvalue(x - offset, y + offset);
        }
        else
        {
            return SE.Getvalue(x - offset, y - offset);
        }
    }
}

外码

    int limit = 500;
    List<int> ExData = new List<int>();
    for (int row = -limit; row < limit; row++)
    {
        for (int col = -limit; col < limit; col++)
        {
            ExData.Add(Root.Getvalue(row, col));
            //sometimes two dimension array
        }
    }

Answer 1

如果您要访问每个元素（即 0 级叶节点），四叉树或任何其他结构都无济于事。无论代码在给定的单元格中获取值，详尽的游览将访问 4,000,000 个点。你的方法在每次访问时沿着树向下一遍又一遍地进行算术运算。

因此对于元素 (-limit,-limit)，代码访问每一层然后 returns。对于下一个元素，它会访问每一层，然后是 returns 等等。那是很费力的。

如果你让添加到列表的过程本身递归访问每个象限一次，它会加快。

注意：我不是 C# 程序员，所以请更正此处的任何错误：

public void AppendValues(List<int> ExData) {
    if(level==0){ 
        ExData.Add(value);
    } else{
        NW.AppendValues(ExData);
        NE.AppendValues(ExData);
        SW.AppendValues(ExData);
        SE.AppendValues(ExData);
    }
}

虽然不是按照原始代码的光栅扫描（逐行）顺序附加所有值！

如果处理稀疏数据，可以进一步提高速度。因此，如果在许多情况下节点为空甚至 'solid'（全部为零或一个值），您可以将节点设置为 null，然后使用零或实体值。

该技巧在 Conway Life 的 Hashlife 中很有效，但取决于您的应用程序。有趣的模式有大面积的 'dead' 细胞，它们总是会传播到死亡，很少需要详细考虑。

我不确定 'duplicates' 中的 25-40% 是什么意思。如果它们不是某个固定值或散布在树中，大的 'solid' 区域可能很少见，并且该技巧在这里可能无济于事。

此外，如果您实际上只需要获取某些区域（例如矩形）中的值，您需要更聪明地了解如何使用 offset 计算每个象限的哪个子区域但它仍然比 'brute' 强制遍历每个元素更有效率。确保代码在感兴趣区域完全位于手头节点之外时实现，并且 return 迅速。

综上所述，如果创建四叉树中所有值的列表在您的应用程序中很常见 activity，那么四叉树可能不是您需要的答案。简单地将 (row,col) 映射到值的映射是预制的，如果有一些常见的默认值（例如零），它也非常有效。

创建一个迭代器对象可能比将数百万个项目添加到列表中更有帮助；特别是如果列表是短暂的并且很快就会被销毁。

需要有关实际应用程序的更多信息才能了解四叉树是否是此处的答案。目前提供的信息表明它不是。

从四叉树获取 N x N 维数据在 C# 中非常慢

Getting N x N dimension data from quad tree is very slow in c#

c#

optimization

quadtree

data-processing

multidimensional-array