Я занимаюсь сортировкой и сетями медианного выбора для девяти элементов, основанных исключительно на двух минимальных/максимальных операциях с двумя входами. Knuth, TAOCP Vol. 3, 2-е изд. (стр. 226), что для девятиэлементной сортировочной сети требуется не менее 25 сравнений, что означает равное количество примитивов SWAP()
или 50 мин/макс. Очевидно, что сортировочная сеть может быть преобразована в сеть медиа-отбора, исключив избыточные операции. По-видимому, общепринятая мудрость заключается в том, что это не приводит к созданию оптимальной сети медианного отбора. Хотя это кажется эмпирически истинным, я не могу найти в литературе никаких доказательств, что это обязательно так.
Лукаш Секанина, "Эволюционное проектирование космических исследований для медианных цепей". В: EvoWorkshops, март 2004 г., стр. 240-249, дается минимальное количество операций min/max, необходимых для оптимальной сети с выбором из девяти входных медиа, как 30 (таблица 1). Я подтвердил, что это достигается как с помощью известной сети медианного отбора, предложенной Джоном Л. Смитом, "Реализация медианных фильтров в FPGA XC4000E". Журнал XCELL, том. 23, 1996, с. 16, а сеть медианных из более ранних работ Chaitali Chakrabarti и Li-Yu Wang, "Новая сортировка сетевых архитектур для фильтров ранжирования". IEEE-транзакции на очень крупных системах интеграции шкал, Vol. 2, № 4 (1994), стр. 502-507, где последний преобразуется в первый путем простого исключения избыточных компонентов. См. Варианты 4 и 5 в приведенном ниже коде.
Изучая опубликованные оптимальные девятиэлементные сортировочные сети для пригодности для преобразования в эффективные сети медианного отбора путем устранения избыточных операций, лучшая версия, которую мне удалось найти, - от Джона М. Гэмбла онлайновый генератор, для которого требуется 32 минуты/макс. операций, так что просто два застенчивых из оптимального количества операций. Это показано как вариант 1 в приведенном ниже коде. Другие оптимальные сортировочные сети сокращают до 36 мин/макс (вариант 2) и 38 мин/макс (вариант 3) соответственно.
Существует ли известная девятиэлементная сеть сортировки (т.е. с 50 двухминутными минимальными/максимальными операциями), которая сводится к оптимальной сетке выбора с девятью входами (с 30 двухминутными минимальными/максимальными операциями) путем устранения избыточные операции?
В приведенном ниже коде используются данные float
в качестве тестового примера, так как многие процессоры предлагают минимальные/максимальные операции для данных с плавающей запятой, но не целые данные, что является одним из исключений. Из-за проблем со специальными операндами с плавающей запятой (которые не встречаются в моем фактическом использовании) оптимальные кодовые последовательности обычно требуют использования режимов "быстрой математики", предлагаемых компиляторами, например, в этом тестовый стенд Godbolt.
#include <cstdlib>
#include <cstdio>
#include <algorithm>
#define VARIANT 1
#define FULL_SORT 0
typedef float T;
#define MIN(a,b) std::min(a,b)
#define MAX(a,b) std::max(a,b)
#define SWAP(i,j) do { T s = MIN(a##i,a##j); T t = MAX(a##i,a##j); a##i = s; a##j = t; } while (0)
#define MIN3(x,y,z) MIN(a##x,MIN(a##y,a##z))
#define MAX3(x,y,z) MAX(a##x,MAX(a##y,a##z))
#define MED3(x,y,z) MIN(MAX(MIN(a##y,a##z),a##x),MAX(a##y,a##z))
#define SORT3(x,y,z) do { T s = MIN3(x,y,z); T t = MED3(x,y,z); T u = MAX3(x,y,z); a##x=s; a##y=t; a##z=u; } while (0)
/* Use sorting/median network to fully or partially sort array of nine values
and return the median value
*/
T network9 (T *a)
{
// copy to scalars
T a0, a1, a2, a3, a4, a5, a6, a7, a8;
a0=a[0];a1=a[1];a2=a[2];a3=a[3];a4=a[4];a5=a[5];a6=a[6];a7=a[7];a8=a[8];
#if VARIANT == 1
// Full sort. http://pages.ripco.net/~jgamble/nw.html
SWAP (0, 1); SWAP (3, 4); SWAP (6, 7); SWAP (1, 2); SWAP (4, 5);
SWAP (7, 8); SWAP (0, 1); SWAP (3, 4); SWAP (6, 7); SWAP (0, 3);
SWAP (3, 6); SWAP (0, 3); SWAP (1, 4); SWAP (4, 7); SWAP (1, 4);
SWAP (2, 5); SWAP (5, 8); SWAP (2, 5); SWAP (1, 3); SWAP (5, 7);
SWAP (2, 6); SWAP (4, 6); SWAP (2, 4); SWAP (2, 3); SWAP (5, 6);
#elif VARIANT == 2
// Full sort. Donald E. Knuth, TAOCP Vol. 3, 2nd ed., Fig 51
SWAP (0, 1); SWAP (3, 4); SWAP (6, 7); SWAP (1, 2); SWAP (4, 5);
SWAP (7, 8); SWAP (0, 1); SWAP (3, 4); SWAP (6, 7); SWAP (2, 5);
SWAP (0, 3); SWAP (5, 8); SWAP (1, 4); SWAP (2, 5); SWAP (3, 6);
SWAP (4, 7); SWAP (0, 3); SWAP (5, 7); SWAP (1, 4); SWAP (2, 6);
SWAP (1, 3); SWAP (2, 4); SWAP (5, 6); SWAP (2, 3); SWAP (4, 5);
#elif VARIANT == 3
// Full sort. Vinod K Valsalam and Risto Miikkulainen, "Using Symmetry
// and Evolutionary Search to Minimize Sorting Networks". Journal of
// Machine Learning Research 14 (2013) 303-331
SWAP (2, 6); SWAP (0, 5); SWAP (1, 4); SWAP (7, 8); SWAP (0, 7);
SWAP (1, 2); SWAP (3, 5); SWAP (4, 6); SWAP (5, 8); SWAP (1, 3);
SWAP (6, 8); SWAP (0, 1); SWAP (4, 5); SWAP (2, 7); SWAP (3, 7);
SWAP (3, 4); SWAP (5, 6); SWAP (1, 2); SWAP (1, 3); SWAP (6, 7);
SWAP (4, 5); SWAP (2, 4); SWAP (5, 6); SWAP (2, 3); SWAP (4, 5);
#elif VARIANT == 4
// Chaitali Chakrabarti and Li-Yu Wang, "Novel sorting network-based
// architectures for rank order filters." IEEE Transactions on Very
// Large Scale Integration Systems, Vol. 2, No. 4 (1994), pp. 502-507
// sort columns
SORT3 (0, 1, 2);
SORT3 (3, 4, 5);
SORT3 (6, 7, 8);
// sort rows
SORT3 (0, 3, 6); // degenerate: MAX3 -> a6
SORT3 (1, 4, 7); // degenerate: MED3 -> a4
SORT3 (2, 5, 8); // degenerate: MIN3 -> a2
// median computation
SORT3 (2, 4, 6); // degenerate: MED3 -> a4 has rank 4
#elif VARIANT == 5
// John L. Smith, "Implementing median filters in XC4000E FPGAs",
// XCELL magazine, Vol. 23, 1996, p. 16
SORT3 (0, 1, 2);
SORT3 (3, 4, 5);
SORT3 (6, 7, 8);
a3 = MAX3 (0, 3, 6); // a3 has rank 2,3,4,5,6
a4 = MED3 (1, 4, 7); // a4 has rank 3,4,5
a5 = MIN3 (2, 5, 8); // a5 has rank 2,3,4,5,6
a4 = MED3 (3, 4, 5); // a4 has rank 4
#else
#error unknown VARIANT
#endif
#if FULL_SORT
// copy back sorted results
a[0]=a0;a[1]=a1;a[2]=a2;a[3]=a3;a[4]=a4;a[5]=a5;a[6]=a6;a[7]=a7;a[8]=a8;
#endif
// return median-of-9
return a4;
}