c++ - 如何确定浮动应该在哪个 bin 中？C++

Question

我有一个浮点数组Float_t xbins[41]，它定义了 40 个容器，即浮点数范围。例如，如果 .y在 bin 7 中y > xbins[7] && !(y > xbins[8])。

在没有 40 个 if 语句的情况下，如何确定给定浮点数应该属于哪个 bin？

请用 C++ 回答，因为我不会说其他语言。

Answer 1

如果数组已排序，则执行二进制搜索以找到正确的 bin。您需要组合std::sort（如果未排序），然后是std::lower_bound, 来定位。您需要确保operator<正确实施Float_t.

Answer 2

事实证明，这些箱不是均匀间隔的，而是具有整数范围，可能最快的方法是有一个（反向）查找表，该表显然有大约 100 个条目。基本上需要对下限和上限进行两次比较。

如果使用公式导出数组边界，则可以编写一个优于 LUT 方法的逆公式。

对于一般情况，二进制搜索是一种方式——甚至可以通过进行线性插值而不是将范围精确地细分为一半来改进一点。与二进制搜索的 O(logn) 相比，速度（如果数据不是病态的）将是 O(loglogn)。