搜索快速/高效的直方图算法(带有预先指定的箱)

Question

我没有在Matlab之外做太多编码,但我需要将我的Matlab代码导出到另一种语言,很可能是C.我的Matlab代码包括一个直方图函数histc(),它放置我的输入数据(这是双-precision,而不是整数)到指定的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]中的均匀分布(需要线性变换)
• 无符号整数值的对数分布(最好与某些位杂乱的黑客相结合,以快速确定最接近的2的幂或类似值).

如果你不知道预先分配,那么你真的不能有一个有效的机制来有效地对它们进行分类:你要么必须猜测(有偏见或无意义的结果),要么存储所有内容并在最后对其进行排序,装入相同大小的桶(性能不佳).

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)(val_max - val_min + 1);],当你遇到每个样本时,你可以除以bin [ bin_idx = (int)((value - val_min) / bin_width);](where bin_width = (max-min)/num_bins)的数量来找到它所属的位置然后递增bin计数器.这是一种简单,快速,单一的数据传递方式.检查上面的算术是否有边缘情况.

您可能遇到的问题是您的输入域可能不知道.double如果您的所有数据都只在其中的一小部分内,那么在整个范围内拥有100个分区并不会太好.解决方案是首先对数据进行传递,以找到范围的最小值/最大值.实际上没有快速解决这个问题,大多数图书馆都要求最低/最高.