优化 9 元素排序网络，减少到一个优化的中位数 9 网络？
Optimal 9-element sorting network that reduces to an optimal median-of-9 network?
我正在研究完全基于两个输入最小/最大操作的九个元素的排序和中值选择网络。 Knuth，TAOCP 卷。 3，第 2 版。声明（第 226 页）九元素排序网络至少需要 25 次比较，这转化为相等数量的 SWAP() 原语或 50 分钟/最大操作。显然，通过消除冗余操作，可以将排序网络转换为中值选择网络。传统观点似乎认为这不会产生最佳的中值选择网络。虽然这在经验上似乎是正确的，但我在文献中找不到任何证据证明这是必然的。
Lukáŝ Sekanina，"Evolutionary Design Space Exploration for Median Circuits"。在：EvoWorkshops，2004 年 3 月，第 240-249 页，给出了最佳九输入中值选择网络所需的最少最小/最大操作数为 30（table 1).我验证了这是通过 John L. Smith "Implementing median filters in XC4000E FPGAs" 给出的著名的中值选择网络实现的。 XCELL 杂志，第 1 卷。 23, 1996, p. 16，以及来自 Chaitali Chakrabarti 和 Li-Yu Wang 早期工作的 9 中位数网络，"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，其中后者通过简单消除冗余组件转换为前者。请参阅下面代码中的变体 4 和 5。
检查已发布的最佳九元素排序网络是否适合通过消除冗余操作转换为高效的中值选择网络，我设法找到的最佳版本来自 John M. Gamble 的 online generator，它需要32 min / max 操作，所以只差两个最佳操作计数。这在下面的代码中显示为变体 1。其他最佳排序网络分别减少到 36 分钟/最大操作（变体 2）和 38 分钟/最大操作（变体 3）。
是否有任何已知的九元素排序网络（即具有 50 个二输入最小/最大操作）通过以下方式减少到最佳九输入中值选择网络（具有 30 个二输入最小/最大操作）单独消除冗余操作？
下面的代码使用 float 数据作为测试用例，因为许多处理器为浮点数据提供最小/最大操作而不是整数数据，GPU 是一个例外。由于特殊浮点操作数的问题（在我的实际用例中不会出现），最佳代码序列通常需要使用编译器提供的 "fast math" 模式，例如 Godbolt testbed.
#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;
}
我不确定这会满足您正在寻找的所有标准，但这里有一种方法可以将变体 5 转换为 25-swap、50-min/max 排序网络，然后将其缩减为 30-min/max 中值选择网络：
我们从使用三个 SORT3、一个 MAX3、一个 MIN3 和两个 MED3 的中值选择网络（John L. Smith，1996）开始：
我们将 MAX3、MIN3 和 MED3 全部改为 SORT3，并添加四个 SWAP 以获得完整的排序网络：
(我们不需要最后对三元组1,2,3和5,6,7进行全排序，因为2不能同时小于1和3，6也不能小于大于 5 和 7。)
当我们用 SWAP 替换 SORT3 时，我们得到这个标准的 25-swap 排序网络：
然后我们可以将其减少到这个 30-min/max 中值选择网络：
MIN = Math.min; MAX = Math.max;
function sortingNetwork9(a) { // 50x min/max
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(5,8); swap(2,5); swap(5,8);
swap(2,4); swap(4,6); swap(2,4);
swap(1,3); swap(2,3);
swap(5,7); swap(5,6);
function swap(i,j) {var tmp = MIN(a[i],a[j]); a[j] = MAX(a[i],a[j]); a[i] = tmp;}
}
function medianSelection9(a) { // 30x min/max
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);
max(0,3); max(3,6); // (0,3);
swap(1,4); min(4,7); max(1,4);
min(5,8); min(2,5); // (5,8);
swap(2,4); min(4,6); max(2,4);
// (1,3); // (2,3);
// (5,7); // (5,6);
function swap(i,j) {var tmp = MIN(a[i],a[j]); a[j] = MAX(a[i],a[j]); a[i] = tmp;}
function min(i,j) {a[i] = MIN(a[i],a[j]);}
function max(i,j) {a[j] = MAX(a[i],a[j]);}
}
var a = [5,7,1,8,2,3,6,4,0], b = [5,7,1,8,2,3,6,4,0];
sortingNetwork9(a);
medianSelection9(b);
document.write("sorted: " + a + "<br>median: " + b[4]);
我正在研究完全基于两个输入最小/最大操作的九个元素的排序和中值选择网络。 Knuth，TAOCP 卷。 3，第 2 版。声明（第 226 页）九元素排序网络至少需要 25 次比较，这转化为相等数量的 SWAP() 原语或 50 分钟/最大操作。显然，通过消除冗余操作，可以将排序网络转换为中值选择网络。传统观点似乎认为这不会产生最佳的中值选择网络。虽然这在经验上似乎是正确的，但我在文献中找不到任何证据证明这是必然的。
Lukáŝ Sekanina，"Evolutionary Design Space Exploration for Median Circuits"。在：EvoWorkshops，2004 年 3 月，第 240-249 页，给出了最佳九输入中值选择网络所需的最少最小/最大操作数为 30（table 1).我验证了这是通过 John L. Smith "Implementing median filters in XC4000E FPGAs" 给出的著名的中值选择网络实现的。 XCELL 杂志，第 1 卷。 23, 1996, p. 16，以及来自 Chaitali Chakrabarti 和 Li-Yu Wang 早期工作的 9 中位数网络，"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，其中后者通过简单消除冗余组件转换为前者。请参阅下面代码中的变体 4 和 5。
检查已发布的最佳九元素排序网络是否适合通过消除冗余操作转换为高效的中值选择网络，我设法找到的最佳版本来自 John M. Gamble 的 online generator，它需要32 min / max 操作，所以只差两个最佳操作计数。这在下面的代码中显示为变体 1。其他最佳排序网络分别减少到 36 分钟/最大操作（变体 2）和 38 分钟/最大操作（变体 3）。
是否有任何已知的九元素排序网络（即具有 50 个二输入最小/最大操作）通过以下方式减少到最佳九输入中值选择网络（具有 30 个二输入最小/最大操作）单独消除冗余操作？
下面的代码使用 float 数据作为测试用例，因为许多处理器为浮点数据提供最小/最大操作而不是整数数据，GPU 是一个例外。由于特殊浮点操作数的问题（在我的实际用例中不会出现），最佳代码序列通常需要使用编译器提供的 "fast math" 模式，例如 Godbolt testbed.
#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;
}
我不确定这会满足您正在寻找的所有标准，但这里有一种方法可以将变体 5 转换为 25-swap、50-min/max 排序网络，然后将其缩减为 30-min/max 中值选择网络：
我们从使用三个 SORT3、一个 MAX3、一个 MIN3 和两个 MED3 的中值选择网络（John L. Smith，1996）开始：
我们将 MAX3、MIN3 和 MED3 全部改为 SORT3，并添加四个 SWAP 以获得完整的排序网络：
(我们不需要最后对三元组1,2,3和5,6,7进行全排序，因为2不能同时小于1和3，6也不能小于大于 5 和 7。)
当我们用 SWAP 替换 SORT3 时，我们得到这个标准的 25-swap 排序网络：
然后我们可以将其减少到这个 30-min/max 中值选择网络：
MIN = Math.min; MAX = Math.max;
function sortingNetwork9(a) { // 50x min/max
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(5,8); swap(2,5); swap(5,8);
swap(2,4); swap(4,6); swap(2,4);
swap(1,3); swap(2,3);
swap(5,7); swap(5,6);
function swap(i,j) {var tmp = MIN(a[i],a[j]); a[j] = MAX(a[i],a[j]); a[i] = tmp;}
}
function medianSelection9(a) { // 30x min/max
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);
max(0,3); max(3,6); // (0,3);
swap(1,4); min(4,7); max(1,4);
min(5,8); min(2,5); // (5,8);
swap(2,4); min(4,6); max(2,4);
// (1,3); // (2,3);
// (5,7); // (5,6);
function swap(i,j) {var tmp = MIN(a[i],a[j]); a[j] = MAX(a[i],a[j]); a[i] = tmp;}
function min(i,j) {a[i] = MIN(a[i],a[j]);}
function max(i,j) {a[j] = MAX(a[i],a[j]);}
}
var a = [5,7,1,8,2,3,6,4,0], b = [5,7,1,8,2,3,6,4,0];
sortingNetwork9(a);
medianSelection9(b);
document.write("sorted: " + a + "<br>median: " + b[4]);