C++ - 仰视没有循环
我有一个C++程序,其在格式期待一个输入文件稀疏矩阵值:C++ - 仰视没有循环
X Y Z
1 1 .642
1.1 1 .482
1.2 1 .394
1.3 1 .420
1.4 1 .948
该文本文件是很长 - 大约2万线左右。我现在需要将它读入我的C++程序中,以便为任何(X,Y)对执行Z查找。如果(X,Y)对与我的输入文件中的对不完全相同,我需要使用最接近的X和最接近的Y值。如果我有一个完整的矩阵而不是非零值,那么X和Y坐标将会均匀分布。
我的问题是确定最快的方法来做到这一点。我想避免实际搜索最接近X的向量,然后搜索最接近Y的向量。有没有办法在没有循环和搜索的情况下完成此操作?某种哈希表可用于查找值吗?
我是一个脚本人和一个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
为了找到属于Z值(1.5 ,1.2)我可以简单地返回在索引[1.5 /(x_spacing),1.2 /(y_spacing)]处找到的Z值。
授予我也需要通过此间距减去我的查找值,如果确切(X,Y)对不存在,则舍入。但底线是,它允许我在不进行任何搜索的情况下得到适当的Z值。我想要完成同样的事情,除非不占用巨型全矩阵需要的所有空间。这就是文本文件只包含对应于非零Z值的对的原因。
任何帮助,你可以提供将不胜感激。
我建议将它存储在结构化树中。例如,四叉树。这将是节省空间的稀疏存储空间,搜索最近点也很容易。
C++中的四叉树教程是here。
我考虑使用树。我想我真正要问的是,如果有一种方法(类似于哈希表)取任何X,Y对并直接得到Z.这将是可能的一个完整的表。例如,我可以取任何x值,除以X坐标之间的差值(假设等距),并给出正确的索引。我想要完成同样的事情,而不必实际存储整个完整的矩阵。 – user1764386 2013-03-13 00:19:33
好吧,哈希表可以工作,但如果你想要的x不存在,那么搜索一个接近的位置将非常困难。 – 2013-03-13 01:02:42
有没有其他方法可能会给我〜O(1)的复杂性?是否还有其他信息可以从第一个程序(生成文件)中提供给文件,所以这可能是可能的? – user1764386 2013-03-13 03:47:54
所以你的意思是问有没有办法以稀疏的方式解析文件?也许只能根据查找来读取它的一部分? – AxelOmega 2013-03-13 00:54:52
我想读取整个文本文件,并以这种方式存储它,当我查找一个值时,我可以在不搜索正确的X和Y键的情况下执行此操作。 – user1764386 2013-03-13 01:03:59
因此,只需使用答案中建议的四叉树即可。 – AxelOmega 2013-03-13 01:21:16