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

Question

我在c＃中使用四叉树结构作为我的数据处理应用程序，它类似于hashlife算法。从四叉树获取数据N×N（例如，2000×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点。你的方式会在每次访问时一次又一次地算术运算。

因此对于element（-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，然后使用零或实心值。

这个技巧在康威生活的Hashlife中运作良好，但取决于你的应用程序。有趣的模式有大面积的“死”细胞，它们总是传播到死亡，很少需要详细考虑。

我不确定25-40％意味着什么是“重复”。如果它们不是一些固定值或分散在树上，那么大的“实心”区域可能很少见，而这种技巧在这里可能没有帮助。

此外，如果你实际上只需要获取某些区域（例如矩形）中的值，那么你需要更清楚地了解如何使用offset计算出你需要的每个象限的哪个子区域，但它仍然会比“野蛮”力量游览每一个元素。确保代码在感兴趣的区域完全位于手中的节点之外并快速返回时实现。

所有这些都说如果创建四叉树中所有值的列表是应用程序中的常见活动，则四叉树可能不是您需要的答案。如果存在一些共同的默认值（例如零），则预先制作简单地将（行，列）映射到值的映射并且再次非常有效。

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

有关实际应用的更多信息，需要了解四叉树是否是答案。到目前为止提供的信息表明它不是。