А могут ли большевики...

[rexy_craxy]

... найти медиану неотсортированного массива чисел за линейное время? Или хотя бы за время, лучшее O(n*log(n))?

Также интересуют "трюковые" способы, if any, сверхбыстрого нахождения медианы в наборах из 3-х, 5-ти и 8-ми чисел.

Just in case: во всех случаях числа суть 32-битовые беззнаковые целые.

Что же до прочего, то я считаю, что частная

Comments

[enotuss]

для 4-8 можно тупо перебором с SSE. А вообще говнопедия в помощь.

[rexy_craxy]

Можно подробнее?

[enotuss]

Конкретные ассемблерные команды (или сишные интринсикты) смотри в мануале, там их не так много.
Алгоритм:
1.грузишь 4 числа в XMM.
2.дублируешь первое число в другой XMM.
3.сравниваешь XMM.
4.считаешь количество бит результата (или грузишь маску, не помню какие там ограничения).
5. если количество бит (или маска) соответствует медиане, то выход, иначе повтор с шага 2 для следующего числа.

Каждый шаг - это 1-3 такта процессора. Для 32 битных чисел бенефит от SSE небольшой, а вот если 16 или 8 битные числа, то вполне.

[rexy_craxy]

> сравниваешь XMM

Вот этим озадачен! Вообще SIMD-расширениями пользуюсь иногда (в объеме, поддерживаемом GCC), но, ИМХО, для векторов даже теоретически не определена операция сравнения. Или имеется в виду что-то вроде побитового & или ^?

В поисках медианы

[vwr]

http://www.cs.dartmouth.edu/~doug/mdmspe.pdf

Re: В поисках медианы

[rexy_craxy]

Спасибо, поглядим.

[udpn]

Кормен.
Супероптимизация.

[vwr]

Что-то все на этого Кормена (и соавт.) ссылаются.
Нешто и впрямь специалист?

[udpn]

Если бы то же самое было хорошо описано у Седжвика или Кнута, ссылался бы на них. Но они извращенцы, а у Кормена есть хотя бы адекватный псевдокод.

[rexy_craxy]

"Супероптимизация" -- это название книги или раздела в книге? :)

[rexy_craxy]

Всем спасибо. Актуальность темы сильно понизилась, т.к. я, наконец-то, вдоволь навозился с самопальными алгоритмами выравнивания контраста, основанными на использовании СКАЛЯРНЫХ стат. величин. Все они неприемлемо ухудшают отношение сигнал/шум.

Так что буду делать старый добрый CLAHE, использующий РАСПРЕДЕЛЕНИЯ. А в нем моменты считать не надо :)