Привет всем!

Подскажите есть ли способ за O(n) или O(n*logn) вычислить гистограму не имея начального представления о динамическом диапазоне чисел?

Добавлено через 14 минут и 29 секунд
Не, при этом я не имею ввиду 8битные числа или гигантских объектов памяти (т.е. bins -> singularity). 

W4FhLF, всмысле "гистограмму"? всмысле "вычислить"?

Добавлено через 4 минуты и 4 секунды
подсчет количества чисел в последовательности чисел?

если хранить гистограмму в map (dict) проблем с ДД не будет
или входная последовательность из непрерывных чисел? тогда - хз, действительно надо знать ДД чтоб квантовать их.

А как это связанно с вычислением гистограммы?


Да. Даже два один за O(n) второй за O(n*log(n))

Это сообщение отредактировал(а) Pavia - 8.8.2010, 17:57

Извиняюсь, если непонятно выразился. Попробую объяснить.

Числа на самом деле обычные float или double. Работаю я на графическом процессоре и никакие map и другие сложные структуры данных использовать нецелесообразно. Отсюда в общем-то и требование O(n), потому что любое обращение к памяти отжирает приличный кусок от производительности алгоритма в целом, ради которой собственно всё и делается.

Pavia, ну как я себе представляю простейший случай. Ищем max и min в выборке за O(n), далее разбиваем полученный динамический диапазон на заданной число корзин: (max - min) / n и потом "раскладываем" числа по корзинам. Явно не O(n*logn) и тем более не O(n).



Буду рад выслушать твои варианты. ;) 

W4FhLF, С оптимизацией под видео карты я незнаком.



Тут вы ошибаетесь. O(n) будет. 
Один раз чтение для нахождения минимума максимума. Один при занисении в корзину и чтение и запись обратно счетчика корзины. Итого 4 операции с памятью. O(4*n) константа 4 можно занести в O получаем O(n). Это свойство оператора O.

Второй вариант это отсортировать числа и пройтись по ним подсчитывая повторы. Это будет O(n*log(n)).

O - это асимптотическая оценка. Я её сам не люблю из-за таких выкрутасов. Нас интересует реальная оценки возможности.

Так вот если чисел очень много то вариант такой разбить на K групп. Т.е завести К массивов счетчиков.  1 число с первым массивом 2 во втором и тд до к. Потом K+1 будет в 1 и тд. По идее должно ускорить. Дальше сливаем эти массивы-гистограммы в один массив-гистограмму.
Возможно надо будет и по другому разбить.

Второй вариант применить быструю сортировку. Взять готовую реализацию под видео карту. Она должна сортировать в регистрах. Так как их много. На небольшом числе чисел от 10 до 1000 будет работать, быстро. Без затрат по обращению к памяти. А дальше уже можно порциями сортировать заносить в гистограмму.

Да, с оценкой я ошибся. Тоже не люблю эту O 

У меня задача не вычислить гистограмму большого объёма данных. Как раз объёмы выборок у меня небольшие.  Каждое графическое ядро вычисляет гистограмму своей выборки. Выборка берётся из общей для ядер памяти, в которой расположен большой массив и выборки между ядрами перекрываются, поэтому я не имею права менять расположение элементов в массиве. Алгоритм с перестановками не подходит. 

Возможно тут подойдёт какой-нибудь рекурсивный алгоритм с постепенным уточнением границ? Я пока себе с трудом это представляю.