Самый быстрый код C / C ++ для выбора медианы в наборе из 27 значений с плавающей запятой

Question

Это хорошо известный алгоритм выбора. см http://en.wikipedia.org/wiki/Selection_algorithm.

Мне нужно, чтобы найти медианное значение набора значений вокселей 3x3x3. Поскольку объем состоит из миллиарда вокселей, а алгоритм рекурсивный, лучше быть немного быстрее. В целом можно ожидать, что значения относительно близки.

Самый быстрый из известных алгоритмов, которые я когда-либо пробовал, использует функцию секционирования быстрой сортировки. Я хотел бы знать, есть ли более быстрый.

Я «изобрел» 20% более быстрый, используя две кучи, но ожидал еще более быстрый, используя хэш. Прежде чем реализовать это, я хотел бы знать, существует ли уже быстрое быстрое решение.

Тот факт, что я использую числа с плавающей запятой, не должен иметь значения, поскольку их можно рассматривать как целое число без знака после инвертирования знакового бита. Заказ будет сохранен.

РЕДАКТИРОВАТЬ: тест и исходный код перенесены в отдельный ответ, как это было предложено Дэви Лэндман. Ниже приведен ответ от chmike.

РЕДАКТИРОВАТЬ : На сегодняшний день Boojum ссылается на наиболее эффективный алгоритм как ссылку на статью Быстрая медиана и двусторонняя фильтрация , которая теперь является ответом на этот вопрос. Первая разумная идея этого метода - использовать радикальную сортировку, вторая - объединить медианный поиск соседних пикселей, которые совместно используют много пикселей.

Answer 1

Мой сверхбыстрый алгоритм для вычисления медианы одномерного набора данных выполняет работу в три этапа и не требует сортировки (!!!) набора данных.

Очень общее описание выглядит следующим образом:

• Пропуск 1: сканирует одномерный набор данных и собирает некоторую статистическую информацию о наборе данных
• Пропуск 2. Использует статистическую информацию набора данных и применяет некоторые данные для создания промежуточного (вспомогательного) массива
• Пропуск 3: сканирует промежуточный (вспомогательный) массив, чтобы найти медиану

Алгоритм предназначен для нахождения медианы чрезвычайно больших наборов 1-D данных, превышающих 8GE (гигаэлементы) значений с плавающей запятой одинарной точности (в настольной системе с 32 ГБ физической памяти и 128 ГБ виртуальной памяти), или для нахождения медиан малых наборов данных в жестких условиях реального времени.

Алгоритм:

• быстрее, чем классический алгоритм, основанный на алгоритме сортировки кучи или слияния, в ~ 60 - ~ 75 раз
• реализовано на чистом языке C
• не использует встроенные функции Intel
• не использует никаких встроенных инструкций ассемблера
• абсолютно переносимый между компиляторами C / C ++, такими как MS, Intel, MinGW, Borland, Turbo и Watcom
• абсолютно переносимо между платформами

С наилучшими пожеланиями, Сергей Костров

Answer 2

Возможно, вы захотите взглянуть на упражнение Кнута 5.3.3.13. Он описывает алгоритм Флойда, который находит медиану из n элементов, используя (3/2) n + O (n ^ (2/3) log n) сравнений, и константа, скрытая в O (·), по-видимому, не слишком большой на практике.

Answer 3

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

Что я на самом деле говорю, так это то, что «скорость» не будет происходить из-за небольшого сложения, потому что 27 значений недостаточно, чтобы нотация Big O была реальным фактором.

Answer 4

Если есть 3x3x3 = 27 возможных значений (если так, почему поплавки?), Можете ли вы создать массив из 27 элементов и считать каждую возможность за один проход данных?

Answer 5

Если вы хотите увидеть алгоритмы, посмотрите книги Дональда Кнута.

PS. Если вы думаете, что изобрели что-то лучшее, вы должны показать, что сложность аналогична или лучше, чем сложность известных алгоритмов. Что для вариаций, основанных на ведре и основании, равно O (n), с другой стороны, быстрая сортировка равна только O (n.log (n)). Метод, который на 20% быстрее, по-прежнему O (n.log (n)), пока вы не сможете показать алгоритм: -)