1

有没有比对非线性 bin 分布进行二分搜索更有效的方法来计算直方图？

我实际上只对将键（值）与 bin（传递函数？）匹配的算法位感兴趣，即对于一堆浮点值，我只想知道每个值的适当 bin 索引。

我知道，对于线性 bin 分布，您可以通过将值除以 bin 宽度来获得 O(1)，而对于非线性 bin，二进制搜索可以获得 O(logN)。我当前的实现对不等的 bin 宽度使用二进制搜索。

本着提高效率的精神，我很好奇是否可以使用散列函数将值映射到其适当的 bin 并在宽度不等的 bin 时实现 O(1) 时间复杂度？

4

4 回答 4

3

在一些简单的情况下，您可以获得 O(1)。

假设您的值是 8 位，从 0 到 255。

如果将它们分成 8 个大小为 2、2、4、8、16、32、64、128 的 bin，则 bin 值范围将为：0-1、2-3、4-7、8-15、16 -31、32-63、64-127、128-255。

在二进制中，这些范围如下所示：

0000000x (bin 0)
0000001x
000001xx
00001xxx
0001xxxx
001xxxxx
01xxxxxx
1xxxxxxx (bin 7)

因此，如果您可以快速（在 O(1) 中）计算值中有多少个最高有效零位，则可以从中获取 bin 编号。

在这种特殊情况下，您可以预先计算一个包含 256 个元素的查找表，其中包含 bin 编号，并且为某个值找到合适的 bin 只是一次查找表。

实际上，对于 8 位值，您可以使用任意大小的 bin，因为查找表很小。

如果您要使用大小为 2 次方的 bin，您也可以将此查找表重用于 16 位值。你需要两次查找。您可以将其扩展到更长的值。

于 2013-03-29T16:47:48.477 回答
2
于 2013-03-29T21:29:05.140 回答
2

Interpolation search is your friend. It's kind of an optimistic, predictive binary search where it guesses where the bin should be based on a linear assumption about the distribution of inputs, rather than just splitting the search space in half at each step. It will be O(1) if the linear assumption is true, but still works (though more slowly) when the assumption is not. To the degree that its predictions are accurate, the search is fast.

于 2013-03-29T21:35:57.733 回答
1

取决于散列的实现和您正在使用的数据类型。对于较小的数据集，如果散列的查找开销平均较大，则更简单的算法（如二进制搜索）可能会优于常量查找。散列的通常实现由链表数组和将字符串映射到链表数组中的索引的散列函数组成。有一个东西叫做负载因子，它是哈希映射中元素的数量/链表数组的长度。因此，对于负载因子 < 1，您将在最佳情况下实现持续查找，因为没有链表将包含一个以上的元素（最佳情况）。

只有一种方法可以找出哪个更好 - 实现哈希映射并亲自查看。你应该能够得到接近不断查找的东西:)

于 2013-03-29T16:29:56.363 回答