Поиск быстрого/эффективного алгоритма гистограммы (с заранее заданными ячейками)

Я не делаю много кодирования за пределами Matlab, но мне нужно экспортировать мой код Matlab на другой язык, скорее всего C. Мой код Matlab включает функцию гистограммы, histc(), которая помещает мои входные данные ( которая является двойной точностью, а не целой) в заданный массив ящиков, чтобы сформировать гистограмму.

Я уверен, что могу скомпоновать пару вложенных циклов для генерации функции гистограммы, но мне нужно, чтобы эта функция была быстрой и запоминающей, поскольку к ней будут обращаться неоднократно и часто.

Чтобы избежать повторного изобретательства колеса, кто-нибудь знает, есть ли у C-языка какие-либо существующие функции гистограммы, доступные для использования, или люди, которые нуждаются в такой вещи, вообще создают ее сами?

Кто-нибудь знает эффективный алгоритм для создания гистограммы? Псевдокод в порядке.

Спасибо заранее.

Ответ 1

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.

Ответ 2

"Идеальный" алгоритм гистограммы будет зависеть от диапазона, который вы ожидаете захватить. Как правило, любой алгоритм гистограммы будет выглядеть следующим образом:

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() - некоторая функция, которая отображает ваши входы в бункер (отображение 0-го или N-го битов в "вне диапазона" применимо).

Точная реализация TRANSFER() сильно зависит от ожидаемого распределения вашего образца и того, где вас интересует подробно. Некоторые общие подходы, которые я видел:

равномерное распределение в диапазоне [a, b] (требуется линейное преобразование)
логарифмическое распределение беззнаковых целочисленных значений (лучше всего в сочетании с некоторыми битными трюками для быстрого определения ближайшей силы-двух или аналогичных).

Если вы не знаете дистрибутив, то у вас действительно нет эффективного механизма для их эффективного использования: вам придется либо угадать (предвзятые или неинформативные результаты), либо сохранить все и отсортировать его по конец, биннинг в ведра одинакового размера (низкая производительность).

Ответ 3

Я написал свой собственный код гистограммы на C, так как он достаточно прост, что я даже не думал искать библиотеку. Обычно вам просто нужно создать массив, чтобы содержать количество бункеров, которые вы хотите [ num_bins = (int)(val_max - val_min + 1);], и по мере того как вы сталкиваетесь с каждым образцом, вы можете разделить на количество ящиков [bin_idx = (int)((value - val_min) / bin_width);] (где bin_width = (max-min)/num_bins), чтобы найти где он принадлежит, а затем увеличивать счетчик бинов. Это простой, быстрый, простой проход данных. Проверьте мою арифметику выше для краевых случаев.

Проблема, с которой вы можете столкнуться, заключается в том, что домен вашего ввода может быть неизвестен. Наличие 100 бункеров во всем диапазоне double не будет очень хорошим, если все ваши данные находятся в пределах лишь небольшой доли этого. Решение состоит в том, чтобы сделать первый проход по данным, чтобы найти min/max вашего диапазона. Там действительно нет быстрого исправления, и большинство библиотек будут запрашивать минимальный/максимальный фронт.