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

[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), но, ИМХО, для векторов даже теоретически не определена операция сравнения. Или имеется в виду что-то вроде побитового & или ^?

[enotuss]

Читай доки, есть там сравнение на больше-меньше. Результат в виде маски.
Интринсикты - это когда нужна какая-никакая кросплатформенность. Когда нужна скорость - только асм, ибо хрен его знает, во что интринсикты скомпилируются. Инлайн асма, как правило, хватает выше крыши.

[rexy_craxy]

Понятно, спасибо.