Как сохранить динамическую гистограмму?

есть ли известный алгоритм + структура данных для поддержания динамическая гистограмма?

Представьте, что у меня есть поток данных (x_1, w_1), (x_2, w_2), ... где x_t - это двойные числа, которые представляют некоторую измеряемую переменную, а w_t - это связанный вес.

Я мог бы просто сделать очевидное (псевдо-код Python):

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 для всех бункеров.

Я не могу придумать, как включить сюда веса ... есть ли у кого-нибудь предложения? (также приветствуются знания о библиотеках C ++, которые делают это.)

РЕДАКТИРОВАТЬ: (для запрошенного пояснения)

x_t - числа с плавающей запятой. Чтобы вычислить гистограмму, я должен разделить непрерывный диапазон, которому принадлежат x, на несколько интервалов. Итак, у меня будет последовательность чисел bin [0], bin [1] и т. Д., Поэтому я должен определить, что i делает bin [i]

Вот как вы обычно составляете гистограмму , когда у вас есть все данные заранее . Тогда вы будете знать пределы max (x) и min (x), и будет легко определить подходящие интервалы. Например, вы можете расположить их на равном расстоянии между min (x) и max (x).

Если вы не знаете диапазон заранее, вы не можете определить ячейки. Вы можете получить x, который не попадает ни в одну корзину. Или у вас может быть много пустых ящиков, потому что вы выбрали слишком большой диапазон для создания ячеек.