c++ - 搜索快速/高效的直方图算法(使用预先指定的 bin)

Question

我在 Matlab 之外没有做太多编码，但我需要将我的 Matlab 代码导出到另一种语言，很可能是 C。我的 Matlab 代码包含一个直方图函数 histc()，它放置我的输入数据 (它是 double 的，而不是整数)到指定的 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] 范围内的均匀分布(需要线性变换)
• 无符号整数值的对数分布(最好与一些 bit twiddling hacks 结合使用，以快速确定最接近的二次幂或类似值)。

如果您事先不知道分布情况，那么您真的无法有一个有效的机制来有效地对它们进行分类:您要么必须猜测(有偏见或无信息的结果)，要么存储所有内容并将其排序最后，分成大小相等的桶(性能不佳)。