Комментарии 18
Ведь на гистограмму в четыре с лишним миллиардов элементов никакой памяти не хватит!
я не очень понял из статьи - а что именно мешает просто отсортировать данные за O(n*log(n)) вместо построения гистограммы?
Да как бы ничто не мешает, но сложности (n*log(n)) именно и хочется избежать. Исходные данные изначально несортированны, разумеется. А так сложность остаётся линейной, нам хочется детерминированного O(n). Ну и любой алгоритм поиска медианы, основанный на сортировке просядет по производительности на больших массивах. Это вот здесь уже обсуждалось немножко - Мой любимый алгоритм: нахождение медианы за линейное время
сортировать-то не надо, можно quickselect с O(N) в среднем
Это так, просто по моим наблюдениям классический quickselect в среднем примерно этак вдвое-втрое медленнее гистограммного метода. Собственно в nimpy вариации на тему quickselect и реализованы в selection.cpp И там и там линейное время, но общий наклон линии тоже хотелось бы уменьшить. Это больше не про теоретическую сложность, а про практическое время выполнения на данном наборе данных.
я думаю в нумпи просто не рассчитывали на читерскую гистограмму на 2^16 бакетов :-) оптимизация на конкретные данные она такая
она же кажется и слабое звено, потому что на массивах в 100 элементов будет только тормозить
впрочем, если продолжить мысль то получится эдакий radixselect, прикольно
че если брать по 8 бит например? и нельзя ли как-то заюзать simd
Про 8 бит я думал, но необходимость увеличенного вдвое количества проходов прибьёт идею, особенно если исходный массив в кэш не влезет — память, она медленная очень, кроме того чем дальше спускаться к младшим байтам, тем больше сравнений. Simd заюзать можно, но там очень много времени положить придётся. Простое включение AVX2 ничего не даёт - это я проверил, впрочем ассемблеровский листинг не смотрел. Проще вначале взять интеловский компилятор и посмотреть, что там векторизатор скажет.
В OpenCV нет метода вычисления медианы? Вы серьезно?
Весьма круто!
Заметно, что похоже на шаг корзинной сортировки. А он, как раз что-то типа O(n).
Ну, на самом деле у вас O(n*log(d)), где log(d) - это разрядность данных, а d - количество этих самых корзин. Вы же при увеличении разрядности таки увеличиваете количество проходов по исходному массиву, чтобы гистограмма помещалась в кэш)
Это для большой разрядности, конечно, или для какой-то универсальной библиотеки обработки даблов. В задачах обработки сигналов не видел, чтобы АЦП выдавало больше 16 бит с аццкой скоростью. 24 бит - скорость уже точно не аццкая, и потребности в медиане не видел.
Ну и смачный подход к обработке данных с плавающей точкой, как с целыми - достойно! Это почти как idSoftware с квадратным корнем. ЦП на десктопах и сейчас с целыми работают раза в 4 быстрее, чем с FP. А вот GPU - не уверен.
Спасибо! Если разрядность данных учитывать, то, конечно, асимптотика будет ещё хуже — там ведь не только больше проходов, но и больше сравнений потребуется. Но я всё-таки за сложность от количества данных, а не от типа. Практически же это действительно не так часто бывает нужно, да и отсутствие функции вычисления медианы в трёх библиотеках обработки изображений как бы намекает. Но если у кого-то медиана - "бутылочное горлышко", то как вариант.
Здорово, но не думаю, что окончалельный результат (ради чего все и делается) сильно бы изменился, если для нахождения медианы предварительно перевести float в int8. Будет ли в формуле медиана, 49 или 51 процентиль, скорее всего ничего особо не поменяется.Нужна ли такая точность как сейчас?
Требуемая точность в общем от задачи зависит; если отрезать младший байт от float, то по моим прикидкам мы потеряем что-то около сотой процента в точности. Можно даже два байта отчекрыжить, тогда потеряем всего-то около процента. Но если оставить только один байт, то потеря будет значительна - ведь у нас в распоряжении будет всего 256 значений на весь диапазон. В данном же случае интерес был более "спортивный", нежели прикладной — получить ровно тот же результат, что выдают пара других библиотечных функций, но за меньшее время.
Результат изменится. Все данные могут быть одного порядка, и тогда int8 будет один и тот-же, и все попадут в одну точку гистограммы. Или наоборот - при большом разбросе все попадут в две крайние точки.
Чтобы так легко сворачивать исходные данные, нужно про них что-то знать. А это как минимум ещё один проход по ним.
А я правильно понимаю, что NaN ваша реализация не совсем дружит?
Это хороший вопрос. Да, не совсем, если во входном массиве все элементы будут NaN, то сработает, а вот если перемешаны с "нормальными" — то нет (точнее не всегда). Я проверил как реагирует на NaN "референсная" NI реализация - там если хотя бы одно число NaN, то и результат всегда NaN, что в общем логично. Это просто элементарная проверка на первом прогоне, и она не должна сильно просадить производительность. Я добавлю, пожалуй, как только время появится. А с плюс минус бесконечностями вроде дружит.
Интересно сравнить с алгоритмом выбора медианы QuickSelect, работающим за O(n): Это что-то вроде сортировки QuickSort, только рекурсивный запуск после разбиения массива по ведущему элементу происходит только в одной половине - в которой и лежит медиана. Для четного случая после получения элемента слева от середины можно просто найти минимум в правой половине массива.
Я вчера в обеденный перерыв проверил навскидку (взяв за основу https://github.com/andralex/MedianOfNinthers). Скажем так - там всё сильно зависит от исходных данных. На случайном наборе гистограммный метод вроде равно чуть быстрее, но далеко не вдвое, однако если входные данные, скажем уже отсортированы, то в общем почти без шансов, разве что на одинарной точности, где всего два прохода надо.
Считаем медиану быстрее numpy