搜索快速/高效的直方图算法（具有预先指定的箱）

Question

我在 Matlab 之外没有做太多编码，但我需要将我的 Matlab 代码导出到另一种语言，最有可能是 C。我的 Matlab 代码包含一个直方图函数 histc()，它放置我的输入数据（它是双精度） -精度，非整数）到指定的 bin 数组中，以形成直方图。

我确信我可以将几个嵌套循环拼凑在一起来生成直方图函数，但我需要这个函数快速且占用内存少，因为它将被重复且频繁地访问。

为了避免重新发明轮子，有人知道C语言是否有可用的现有直方图函数，或者需要这样的东西的人通常自己创建它吗？

有人知道创建直方图的有效算法吗？伪代码没问题。

提前致谢。

Answer 1

“理想”直方图算法将取决于您期望捕获的范围。一般来说，任何直方图算法都将如下所示：

const int NSAMPLES = whatever;
double samples[NSAMPLES] = { 1.0, 3.93, 1e30, ... }; // your data set
const int NBUCKETS = 10; // or whatever
int counts[NBUCKETS] = { 0 };
for (int i = 0; i != NSAMPLES; ++i) {
    counts[TRANSFER(samples[i])]++;
}

其中 TRANSFER() 是将输入映射到 bin 的函数（第 0 个或第 N 个 bin 映射到适用的“超出范围”）。

TRANSFER() 的确切实现在很大程度上取决于样本的预期分布以及您感兴趣的细节。我见过的一些常见方法：

• [a,b] 范围内的均匀分布（需要线性变换）
• 无符号整数值的对数分布（与一些 位旋转黑客来快速确定最接近的二次幂或类似的）。

如果您事先不知道分布，那么您确实无法拥有有效的机制来有效地对它们进行分类：您要么必须猜测（有偏见或无信息的结果），要么存储所有内容并在最后对其进行排序，分箱到相同大小的桶中（性能较差）。

Answer 2

GSL（GNU 科学库）包含直方图实现。

这是文档： http://www.gnu.org/software/ gsl/manual/html_node/Histograms.html。

这是一个示例使用： http:// www.gnu.org/software/gsl/manual/html_node/Example-programs-for-histograms.html。

Answer 3

我用 C 语言编写了自己的直方图代码，因为它非常简单，我什至没有想过要寻找一个库。通常，您只需要创建一个数组来包含所需的 bin 数量 [num_bins = (int)(max_val - min_val + 1);]，当您遇到每个样本时，您可以除以箱数 [bin_idx = (int)((value - min_val) / bin_width);]（其中 bin_width = (max_val - min_val)/num_bins）来查找位置它属于，然后递增 bin 计数器。这是一次简单、快速、单次传递数据的过程。请检查我上面的算术是否有边缘情况。

您可能遇到的问题是您的输入的域可能未知。如果您的所有数据仅占其中的一小部分，那么在整个 double 范围内拥有 100 个 bin 并不会带来多大好处。解决方案是首先遍历数据以找到范围的最小值/最大值。确实没有快速解决这个问题的方法，大多数库都会预先要求最小/最大。