c++ - 在没有循环的情况下查找稀疏矩阵值

Question

我有一个 C++ 程序需要格式为以下的输入文件:

X    Y    Z
1    1    .642
1.1  1    .482
1.2  1    .394
1.3  1    .420
1.4  1    .948

文本文件很长 - 大约 20,000 行左右。我现在需要将其读入我的 C++ 程序，以便对任何 (X,Y) 对进行 Z 查找。如果 (X,Y) 对与我的输入文件中的任何一对都不完全相同，我需要使用最接近的 X 和最接近的 Y 值。如果我有一个完整的矩阵而不是只有非零值，X 和 Y 坐标将均匀分布。

我的问题是确定最快的方法。我想避免实际搜索最接近的 X 的 vector ，然后搜索最接近的 Y 的 vector 。有没有一种方法可以在不循环和搜索的情况下完成此操作？是否可以使用某种哈希表来查找值？

我是一名脚本专家和一名 C++ 新手，所以如果这看起来微不足道，我深表歉意。所以作为引用，我需要快速的方法:

lookup(1.1,1)
    >>> .482

lookup(1.112, 1)
    >>> .482 // value corresponding to closest x and closest y

lookup(0,0)
    >>> .642 // value corresponding to closest x and closest y

如果我有完整的矩阵，这是可能的，例如:

    1.1  1.2  1.3  1.4  1.5
1.1
1.3
1.5      (Z values)
1.7
1.9

为了找到与 (1.5, 1.2) 相关的 Z 值，我可以简单地返回在索引 [1.5/(x_spacing), 1.2/(y_spacing)] 处找到的 Z 值。

当然，我还需要用这个间距减去我的查找值，如果不存在确切的 (X,Y) 对，则进行舍入。然而，最重要的是，它允许我在不进行任何搜索的情况下获得适当的 Z 值。我想完成同样的事情，除了不占用巨大的完整矩阵所需的所有空间。这就是文本文件仅包含对应于非零 Z 值的对的原因。

如果您能提供任何帮助，我们将不胜感激。

Answer 1

我建议将其存储在结构化树中。例如四叉树。它将是稀疏存储以节省空间并且搜索最近点也很容易。

C++ 中的四叉树教程是 here .