Comments 22
Если нужна гарантированная точность 0.5%-2%, то я бы просто завел массив из 200 счетчиков и инкременировал бы нужный (координата считается одной операцией деления, которая у вас тоже есть). При выходе за границы — пересчет массива в 2 раза, в пределе очень редкое событие… 2 таких расширения в худшем случае дадут сужение в 4 раза. Дальше допилил бы алгоритм уже по ситуации.
Или вы точность медианы не по крайним значениям считаете, а по сигме?
Или вы точность медианы не по крайним значениям считаете, а по сигме?
Точность я считаю в процентах от действительного значения медианы (а не как отклонение вычисленного значения от середины выборки)
С массивом не могли бы подробнее расписать? Мне кажется, Вы не учитываете некоторые моменты, которые возникают от того, что заранее неизвестно в каком диапазоне будут сосредоточены данные.
С массивом не могли бы подробнее расписать? Мне кажется, Вы не учитываете некоторые моменты, которые возникают от того, что заранее неизвестно в каком диапазоне будут сосредоточены данные.
Можно воспользоваться такой штукой github.com/HdrHistogram/HdrHistogram
По факту это такой же массив, но шкала нелинейна. Можно хранить значения от 0 до 3,600,000,000 с точностью до трёх знаков.
И считать не только медиану, но и другие квантили:)
Есть порты на другие ЯП!;-)
По факту это такой же массив, но шкала нелинейна. Можно хранить значения от 0 до 3,600,000,000 с точностью до трёх знаков.
И считать не только медиану, но и другие квантили:)
Есть порты на другие ЯП!;-)
>> в процентах от действительного значения медианы…
Т.е. я правильно понимаю что если значения сосредоточены скажем в диапазоне от 100.0 до 101.0 то даже совсем криво посчитанная медиана (по крайнему значению) заведомо даст ошибку в не более чем 1% (например, если метод ошибочно дает 101.0 а реальная медиана это 100.01). И наоборот если реальная медиана топчется возле нуля — то даже небольшая абсолютная ошибка в относительном значении может болтаться от минус до плюс бесконечности.
Но я просто не знаю реальной задачи, что там важно а что нет))
>>Вы не учитываете некоторые моменты, которые возникают от того, что заранее неизвестно в каком диапазоне будут сосредоточены данные.
Да, если хвосты длинные то диапазон будет очень широкий и почти все значения улягутся в один счетчик. Точность по границам будет выдержана но толку нет.
Вообще, мне кажется точность медианы нужно оценивать по тому на сколько полученное разделение отличается от 50/50. Например требовать не хуже 49/51. Если так, то мне на вскидку кажется это невозможно выдержать не сохраняя и анализирую все прошлые значения ((
Т.е. я правильно понимаю что если значения сосредоточены скажем в диапазоне от 100.0 до 101.0 то даже совсем криво посчитанная медиана (по крайнему значению) заведомо даст ошибку в не более чем 1% (например, если метод ошибочно дает 101.0 а реальная медиана это 100.01). И наоборот если реальная медиана топчется возле нуля — то даже небольшая абсолютная ошибка в относительном значении может болтаться от минус до плюс бесконечности.
Но я просто не знаю реальной задачи, что там важно а что нет))
>>Вы не учитываете некоторые моменты, которые возникают от того, что заранее неизвестно в каком диапазоне будут сосредоточены данные.
Да, если хвосты длинные то диапазон будет очень широкий и почти все значения улягутся в один счетчик. Точность по границам будет выдержана но толку нет.
Вообще, мне кажется точность медианы нужно оценивать по тому на сколько полученное разделение отличается от 50/50. Например требовать не хуже 49/51. Если так, то мне на вскидку кажется это невозможно выдержать не сохраняя и анализирую все прошлые значения ((
На разных распределениях точность работы очень разная, Вы можете сами увидеть это из данных в конце статьи. Для положительных данных с длинным хвостом (схожих с распределением Ципфа) точность замечательная, но всегда можно придумать контрпример, где она будет ужасная. Другое дело, что встретить в реальности такой контрпример будет затруднительно.
Нужно не только расширять интервал, но ещё и так же динамически увеличивать точность, добавлять счётчики — например, если диапазон от 0 до 1000, но большинство значений лежит между 0 и 1, то между 0 и 1 вам нужно соответственно больше счётчиков, иначе получите медиану где-то в районе ~5 вместо ~0,5.
Просто оставлю тут вот это — ru.wikipedia.org/wiki/%D0%A1%D0%BA%D0%BE%D0%BB%D1%8C%D0%B7%D1%8F%D1%89%D0%B0%D1%8F_%D1%81%D1%80%D0%B5%D0%B4%D0%BD%D1%8F%D1%8F
З. Ы. Добавьте, пожалуйста, таблички со сравнением вычисленной медианы по полной выборке, и вычисленной в итоге вашим методом на разных выборках.
З. Ы. Добавьте, пожалуйста, таблички со сравнением вычисленной медианы по полной выборке, и вычисленной в итоге вашим методом на разных выборках.
Добавил таблички, можете сравнить.
Я, может быть, чего-то не понял, но вроде бы автор говорил о медиане по всему набору данных, а в указанной статье речь в основном идёт об арифметическом среднем, причём скользящем, т.е. только по n последним значениям. Скользящие функции тривиально реализуются за O(n) времени и O(1) памяти, а вот по всему объёму — это уже интересней.
На самом деле предложенный мною алгоритм тоже является в какой-то мере скользящим — результат больше зависит от последних значений, чем от первых.
Но первые ведь тоже учитываются, верно? Просто для меня это немного разный класс алгоритмов. Статистика по окну ничем не отличается от статистики по небольшому набору данных. А вот статистику по всему большому набору получить гораздо сложнее, просто в силу ограничений памяти и процессорного времени.
Да, интересная задача. Если в один проход решать, то можно ткнуть в несколько случайных элементов и выбрать из них медиану. Если элементов будет порядка O(1/eps^2 \log(1/delta)), то вероятность, что выбранный элемент будет стоять от медианы на расстоянии не более eps * n будет не меньше 1 — delta.
А еще вроде есть хитрый алгоритм Мунро-Патерсона, который умеет эту задачу решать точно с O(1) памяти за O(log n) проходов.
А еще вроде есть хитрый алгоритм Мунро-Патерсона, который умеет эту задачу решать точно с O(1) памяти за O(log n) проходов.
Есть же Greenwald and Khanna GK01 и многочисленные его вариации, находятся по ключевым словам fast approximate quantiles.
По поводу эфективности… а оценка имеет наименьшую дисперсию в классе несмещённых оценок?
Такое ощущение, что вовсе нет.
Такое ощущение, что вовсе нет.
А почему в одном случае из десяти так резко отличается отклонение? Ещё я не вижу сильной корреляции на разных размерах выборки, вы пробовали задавать размер в районе 10^6 — 10^8?
Sign up to leave a comment.
Эффективная оценка медианы