существует ли известный алгоритм + структура данных для поддержания динамической гистограммы?
Представьте, что у меня есть поток данных (x_1, w_1), (x_2, w_2),... где x_t - двойники, представляющие некоторую измеренную переменную, а w_t - связанный вес.
Я мог бы просто сделать очевидный (псевдо-питонный код):
x0,xN = 0, 10
numbins = 100
hist = [(x0 + i * delta , 0) for i in xrange(numbins)]
def updateHistogram(x, w):
k = lookup(x, hist) #find the adequated bin where to put x
hist[k][1] += 1
Но у меня есть некоторые проблемы с этим, когда у меня есть непрерывный поток данных. У меня нет полного набора данных в руках, и я должен проверить гистограмму между сбором данных. И я не ожидаю:
- идеальный размер бункера для того, чтобы не дойти до большого количества пустых бункеров,
- диапазон данных
Итак, я хочу динамически определять бункеры. Я мог бы сделать глупость:
for x in data_stream:
data.append(x)
hist = make_histogram(data)
но я думаю, что это будет очень быстро...
Если все весовые коэффициенты равны одной из вещей, которые, как я думал, хранят данные в отсортированном массиве и вставляют новые данные таким образом, чтобы отсортировать массив. Таким образом, я мог бы:
data = sortedarray();
for x in data_stream:
data.insert(x)
bins = [ data[int(i * data.size()/numbins)] for i in xrange(numbins)]
и подсчет внутри каждого бина будет равен data.size()/numbins для всех бинов.
Я не могу придумать способ включения весов в это, хотя... есть ли у кого-нибудь предложение? (знание о библиотеках С++, которые это делают, также приветствуется).
EDIT: (для запрошенного разъяснения)
x_t - числа с плавающей запятой. Чтобы вычислить гистограмму, я должен разделить непрерывный диапазон, где x принадлежит в нескольких ячейках. Поэтому у меня будет последовательность чисел bin [0], bin [1] и т.д., Поэтому я должен определить, для чего я делаю bin [i] < x < бен [г + 1].
Вот как вы обычно делаете гистограмму, когда у вас есть все данные заранее. Затем вы должны знать пределы max (x) и min (x), и было бы легко определить соответствующие ячейки. Например, вы могли бы разделить их на равные промежутки между min (x) и max (x).
Если вы заранее не знаете диапазон, вы не можете определить ячейки. Вы можете получить x, который не попадает ни в один бит. Или вы можете много пустых бункеров, потому что вы выбрали слишком большой диапазон для создания бункеров.