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

Question

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

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

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

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

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

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

Answer 2

GSL (GNU Scientific Library) содержит реализацию гистограммы.

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

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