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

Question

我在 c# 中为我的数据处理应用程序使用四叉树结构，它类似于哈希生命算法。从四叉树获取数据 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)，代码访问每一层，然后返回。对于下一个元素，它访问每一层，然后返回，依此类推。这是非常费力的。

如果您将添加到列表本身的过程递归访问每个象限一次，它将加快速度。

注意：我不是 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);
}
}  

这将附加所有值，尽管不是按原始代码的光栅扫描(逐行)顺序！

如果您正在处理稀疏数据，则可以进一步加快速度。因此，如果在许多情况下节点为空甚至"实心"(全部为零或一个值)，您可以将节点设置为null，然后使用零或实心值。

这个技巧在Conway Life的Hashlife中效果很好，但取决于您的应用程序。有趣的模式有大面积的"死"细胞，这些细胞总是会传播到死细胞，很少需要详细考虑。

我不确定 25-40% 的"重复"是什么意思。如果它们不是某个固定值或分散在树上，那么大的"固体"区域可能很少见，而这个技巧在这里可能无济于事。

此外，如果您实际上只需要获取某个区域(例如矩形)中的值，则需要更聪明地了解如何使用offset计算出每个象限的哪个子区域，但它仍然比每个元素的"蛮力"巡回要有效得多。确保代码在感兴趣区域完全在手头节点之外时意识到并快速返回。

综上所述，如果在四叉树中创建所有值的列表是应用程序中的常见活动，那么四叉树可能不是您需要的答案。简单地将(行，列)映射到值的映射是预先制作的，如果存在一些常见的默认值(例如零)，则再次非常有效。

创建迭代器对象而不是向列表中添加数百万个项目可能会有所帮助;特别是如果列表是暂时的并且很快就会被销毁。

需要有关实际应用程序的更多信息才能了解四叉树是否是此处的答案。到目前为止提供的信息表明事实并非如此。