“插值”的数据结构查表

发布于 2024-12-21 03:38:50 字数 183 浏览 1 评论 0原文

我有一个代表一变量函数的二维点的集合。给定一个随机输入值，我必须选择最接近的值。示例：

曲线： (1,5) (2,8) (5,9)

输入：3 输出：8

我主要关心的是速度，空间并不那么重要。哪种数据结构最好？

编辑：该表是静态的，在运行时不会改变

原文

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

一曲琵琶半遮面シ 2024-12-28 03:38:50

这取决于表是静态的还是动态的。

如果是静态数据，简单的排序数组和二分搜索就可以完成工作：搜索键，如果没有找到，检查上面和下面的索引，看看哪个更接近搜索键，并返回其关联值。

如果数据是动态的，我会使用 B+Tree 变体（尽管任何平衡的树结构都应该有效）。本质上是相同的算法，但是您将检查兄弟节点，而不是仅检查相邻的数组单元格。

回复收藏 0 原文

北音执念 2024-12-28 03:38:50

你说该表是静态的，在运行时不会改变。
然后，如果您需要出色的性能，并且表不是太大，那么很难击败硬编码的二分搜索。
对于您提供的表，它看起来像这样：

result = (x < 3.5
            ? (x < 1.5
                ? 5
                : 8
              )
            : 9
         );

您可能需要编写一个小程序来将表作为输入，并生成代码作为输出，以便您可以将其包含在主程序中。

如果您不介意使用宏，则可能会使其编写起来更容易一些，如下所示：

#define M(a,middle,b) (x < (middle) ? (a) : (b))

result = M( M(5, 1.5, 8), 3.5, 9);

解决这个问题的唯一方法是使用硬编码的哈希搜索（使用 switch 语句）。

如果表可以在运行之间更改，那么每当程序启动时，它都会生成代码、编译并将其链接到 dll、加载 dll 并使用它运行，这可能是有意义的。
这可能需要大约一秒钟的时间，然后你就可以达到高速了。

You say the table is static, and won't change during runtime.
Then if you need blazing performance, and if the table is not too large, it's hard to beat a hard-coded binary search.
For the table you gave, it looks like this:

result = (x < 3.5
            ? (x < 1.5
                ? 5
                : 8
              )
            : 9
         );

You may have to write a little program to take the table as input, and generate the code as output, so you can include it in your main program.

If you don't mind using a macro, you might make it a little easier to write, like this:

#define M(a,middle,b) (x < (middle) ? (a) : (b))

result = M( M(5, 1.5, 8), 3.5, 9);

The only way to beat that is with a hard-coded hash search (using a switch statement).

If the table can change between runs, it might make sense to, whenever the program starts, it generates the code, compiles and links it into a dll, loads the dll, and runs with that.
That can take all of about a second, and then you have the high speed.

回复收藏 0 原文

~没有更多了~