c++ - 平方/立方根查找表

Question

我想知道哪个是为 range 中浮点值的平方根和立方根创建两个查找表的最佳方法[0.0, 1.0)。

我已经对代码进行了概要分析，发现这是一个相当强的性能瓶颈（因为我需要为每个值计算它们的几十万个值）。然后我想起了查找表，并认为它们会帮助我提高性能。

由于我的值在一个很小的范围内，我正在考虑用步骤来分割范围，比如说，0.0025（希望它足够了）但我不确定哪种方法应该是最有效的检索它们的方法。

我可以轻松地填充查找表，但我需要一种方法来有效地获取给定浮点数的正确值（在任何步骤中都没有离散化）。对此问题有任何建议或众所周知的方法吗？

我正在使用移动平台，只是为了指定。

提前致谢

score 4 · Accepted Answer

你有 (1.0-0.0)/0.0025 = 400 步

只需创建一个 400x1 矩阵并通过将您想要正方形/立方体的浮点数乘以 400 来访问它。

例如，如果您想查找 0.0075 的平方。将 0.0075 乘以 400 并得到 3，这是您在矩阵中的索引

score 1 · Accepted Answer

1

double table_sqrt(double v)
{
    return table[(unsigned int)(v / 0.0025)];
}

于 2012-04-18T18:27:30.540 回答

score 0 · Accepted Answer

您可以将值乘以您想要的任何精度，然后使用哈希表，因为结果将是整数值。

例如，与其使用浮点键值0.002，不如给自己一个小数点后三位或四位的精度，使您的键值0.002等于200或2000。2000然后，您可以快速查找存储在槽的哈希表键中的平方根和三次根的结果浮点值。

如果您还想从插槽之间的非离散范围中获取值，则可以使用数组或树而不是哈希表，以便您可以通过在根之间插值来生成“中间”值存储在两个相邻的键值槽中。

score 0 · Accepted Answer

如果您只需要分成 10 个不同的条带，请找到与条带之间的阈值相对应的输入，并使用展开的二进制搜索来测试这 9 个值。或者在阈值测试完成之前是否需要额外的计算，以便查找的值不是最终结果。

4 回答 4