这个问题是对这里回答的问题的一个小扩展。我正在重新实现这篇论文第2.1节中提到的直方图近似版本，在开始这个过程之前，我想把所有事情都安排好。之前，我使用了boost::multi_index，但性能不是很好，我希望避免使用std::set时桶数的对数级插入/查找复杂度。由于我使用的直方图数量（随机森林中随机树的每个叶节点的每个类别的每个特征一个），计算复杂度必须尽可能接近常数。
实现直方图的标准技术涉及将输入的实数值映射到一个桶号。为了实现这一点，一种方法是：
- 初始化一个大小为N的标准C数组，其中N = 桶的数量；以及
- 将输入值（实数）乘以某个因子，然后对结果进行向下取整以获得其在C数组中的索引。
这对于具有均匀桶大小的直方图效果很好，并且非常高效。然而，上述链接的论文的第2.1节提供了一种没有均匀桶大小的直方图算法。
另一个问题是，简单地将输入的实数值乘以一个因子并使用结果作为索引在处理负数时会失败。为了解决这个问题，我考虑在数组中某个位置识别一个’0’桶。这个桶将以0.0为中心；可以使用刚刚解释的相同乘法和向下取整方法计算其上方/下方的桶，只是稍微修改一下，将向下取整的乘积根据需要加2或减2。
这就引出了合并的问题：论文中的算法合并两个最接近的桶，测量标准是从中心到中心。在实践中，这会创建一个’锯齿状’的直方图近似，因为一些桶会有极大的计数，而其他桶则不会。当然，这是由于非均匀大小的桶造成的，并且不会导致任何精度损失。然而，如果我们尝试将非均匀大小的桶标准化以使其均匀，就会发生精度损失。这是由于假设m/2个样本落在桶中心的左右两侧，其中m = 桶计数。我们可以将每个桶建模为高斯分布，但这仍然会导致精度损失（尽管很小）。
所以这就是我目前卡住的地方，导致了这个主要问题：实现一个接受流数据并将每个样本存储在均匀大小的桶中的直方图的最佳方法是什么？
回答：
保持四个变量。
int N; // 为了简单起见，假设N是偶数int count[N];double lower_bound;double bin_size;当一个新的样本x到达时，计算double i = floor(x - lower_bound) / bin_size。如果i >= 0 && i < N，则增加count[i]。如果i >= N，则重复将bin_size翻倍，直到x - lower_bound < N * bin_size。每次翻倍时，调整计数（通过利用多次翻倍的稀疏性来优化这一点）。
for (int j = 0; j < N / 2; j++) count[j] = count[2 * j] + count[2 * j + 1];for (int j = N / 2; j < N; j++) count[j] = 0;i < 0的情况更棘手，因为我们需要同时减少lower_bound和增加bin_size（同样，优化稀疏性或在一步中调整计数）。
while (lower_bound > x) { lower_bound -= N * bin_size; bin_size += bin_size; for (int j = N - 1; j > N / 2 - 1; j--) count[j] = count[2 * j - N] + count[2 * j - N + 1]; for (int j = 0; j < N / 2; j++) count[j] = 0;}特殊情况是昂贵的，但只会在数据范围内相对于初始桶大小的对数次数内发生。
如果你在浮点数中实现这一点，请注意浮点数不是实数，像lower_bound -= N * bin_size这样的语句可能会出现问题（在这种情况下，如果N * bin_size远小于lower_bound）。我建议bin_size始终是基数（通常是二）的幂。
