最优的9元素排序网络如何转化为最优的中位数排序网络？

Question

我正在研究基于两个输入的最小/最大操作的九个元素的排序和中位数选择网络。Knuth，《TAOCP Vol. 3》，第2版指出（第226页），一个九元素排序网络至少需要25次比较，这相当于相同数量的SWAP()原语或50个最小/最大操作。显然，可以通过消除冗余操作将排序网络转换为中位数选择网络。传统智慧似乎认为这不会导致最佳中位数选择网络。虽然这似乎是经验性的，但我在文献中找不到证明这一点的证据。

Lukáŝ Sekanina，“Evolutionary Design Space Exploration for Median Circuits”。在：EvoWorkshops，2004年3月，第240-249页中，给出了实现优化的九输入中位数选择网络所需的最小最大操作数为30（表1）。我验证了这是由John L. Smith提供的著名中位数选择网络和Chaitali Chakrabarti和Li-Yu Wang早期工作中的中位数网络的结果。《Novel sorting network-based architectures for rank order filters》。IEEE Transactions on Very Large Scale Integration Systems，卷2，第4号（1994年），第502-507页，后者通过简单地消除冗余组件而转化为前者。请参见下面代码中的变体4和5。

检查已发布的最优九元素排序网络，以确定它们是否适合通过消除冗余操作转换为高效的中位数选择网络，我找到的最佳版本来自John M. Gamble的在线生成器，它需要32个最小/最大操作，仅比最优操作计数少两个。这在下面的代码中显示为变体1。其他最优排序网络分别减少到36个最小/最大操作（变体2）和38个最小/最大操作（变体3）。

是否存在任何已知的九元素排序网络（即具有50个两个输入的最小/最大操作），通过仅消除冗余操作就可以缩减为最佳的九输入中位数选择网络（具有30个两个输入的最小/最大操作）？

下面的代码使用float数据作为测试用例，因为许多处理器提供浮点数据的最小/最大操作，但不提供整数数据，GPU是一个例外。由于特殊浮点操作数的问题（在我的实际用例中不存在），最佳代码序列通常需要编译器提供的“快速数学”模式，例如在此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;
}

- njuffa

Answer 1

我不确定这个方案是否符合你所寻找的所有标准，但以下是一种将变异体5转换为25次交换、50次最小/最大排序网络，然后缩减为30次最小/最大中位数选择网络的方法：

我们从中位数选择网络（John L. Smith，1996）开始，该网络使用三个SORT3，一个MAX3，一个MIN3和两个MED3：

我们将所有的MAX3，MIN3和MED3都替换为SORT3，并添加四个SWAP来获得完整的排序网络：

当我们用SWAP替换SORT3时，我们得到了这个标准的25次交换排序网络：

（最后我们不需要完全排序三元组1,2,3和5,6,7，因为2不能比1和3都小，6也不能比5和7都大。）

我们可以将其简化为这个30分钟/最大中位数选择网络：

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]);

- m69 ''snarky and unwelcoming''

---

只有在将其转换为使用三操作数交换时，它才会这样做，因此这可能不是您要寻找的内容。 - m69 ''snarky and unwelcoming''

如果这个能够按照预期工作（目前的初步迹象看起来不错，我很兴奋），我将非常高兴地接受并添加50分的奖励。您是根据我的问题创建了这个排序网络，还是这反映了您之前的工作，可能已经发表或在草稿中？ - njuffa

没问题！这是Compiler Explorer（godbolt）的链接，以便说明。当作为排序网络构建时，有50个min/max操作；但是当编译成提取中位数时，只有30个min/max操作。我在我的测试框架中测试了该函数，以确保它可以正确运行。 - njuffa

@njuffa 现在我得编辑我的回答，让它看起来像我知道我在做什么 :-) （我猜我开始使用的中位数网络的高度对称性以及我添加的交换使其成为排序网络，这些都与它是最优解有关。） - m69 ''snarky and unwelcoming''

我认为答案本身已经很好了。你的想法是从一个最佳中位数选择网络开始，然后添加最少的交换次数，使其成为完整的排序网络，这是解决该问题的绝佳方法，而我一直太过专注于相反的方向。你的逐步解释工作的图表也很好。 - njuffa