非常频繁地调用std :: nth

本文介绍了非常频繁地调用std :: nth_element（）函数的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

我没有在任何地方找到这个特定的主题...

我调用nth_element（）算法约40万次每秒对不同的数据在std :: 23个整数的向量，更精确的无符号短值。

我想提高计算速度，这个特殊的调用需要大量的CPU时间。 现在我注意到，与std :: sort（）一样，nth_element函数在分析器中是可见的，即使具有最高优化级别和NDEBUG模式（Linux Clang编译器），因此比较内联，但不是函数调用本身。因为数据的大小很小，我使用二次排序进行了实验，所以我们可以使用一个二次排序函数PIKSORT，当数据大小小于20个元素时，它通常比调用std :: sort更快，可能是因为函数将是内联的。

template< class CONTAINER> inline void piksort（CONTAINER& arr）//确实这是插入排序 { typename CONTAINER :: value_type a; const int n =（int）arr.size（）; for（int j = 1; j< n; ++ j）{ a = arr [j]; int i = j; while（i> 0&& a< arr [i-1]）{ arr [i] = arr [i-1] i--; } arr [i] = a; } }

但是这比使用nth_element更慢。

此外，使用统计方法是不合适的，比std :: nth_element更快的东西

最后，由于值在0到约20000的范围内，适当。

我的问题：有没有人知道一个简单的解决方案？我想我可能不是唯一一个非常频繁调用std :: sort或nth_element。

解决方案

数组的大小始终为 23 。此外，使用的类型是 unsigned short 。在这种情况下，您可能尝试使用大小 23 的排序网络;因为你的类型是 unsigned short ，用排序网络排序整个数组可能比使用 std :: nth_element 。这是一个非常直接的C ++ 14实现的大小 23 与 118 比较交换单位的排序网络，如 使用对称和进化搜索以最小化网络排序所述：

模板< typename RandomIt，typename Compare = std :: less< void network_sort23（RandomIt first，Compare compare = {}） { swap_if（first [1u]，first [20u]，compare）; swap_if（first [2u]，first [21u]，compare）; swap_if（first [5u]，first [13u]，compare）; swap_if（first [9u]，first [17u]，compare）; swap_if（first [0u]，first [7u]，compare）; swap_if（first [15u]，first [22u]，compare）; swap_if（first [4u]，first [11u]，compare）; swap_if（first [6u]，first [12u]，compare）; swap_if（first [10u]，first [16u]，compare）; swap_if（first [8u]，first [18u]，compare）; swap_if（first [14u]，first [19u]，compare）; swap_if（first [3u]，first [8u]，compare）; swap_if（first [4u]，first [14u]，compare）; swap_if（first [11u]，first [18u]，compare）; swap_if（第一个[2u]，第一个[6u]，比较）; swap_if（first [16u]，first [20u]，compare）; swap_if（first [0u]，first [9u]，compare）; swap_if（first [13u]，first [22u]，compare）; swap_if（first [5u]，first [15u]，compare）; swap_if（first [7u]，first [17u]，compare）; swap_if（first [1u]，first [10u]，compare）; swap_if（first [12u]，first [21u]，compare）; swap_if（first [8u]，first [19u]，compare）; swap_if（first [17u]，first [22u]，compare）; swap_if（first [0u]，first [5u]，compare）; swap_if（first [20u]，first [21u]，compare）; swap_if（first [1u]，first [2u]，compare）; swap_if（first [18u]，first [19u]，compare）; swap_if（first [3u]，first [4u]，compare）; swap_if（first [21u]，first [22u]，compare）; swap_if（first [0u]，first [1u]，compare）; swap_if（first [19u]，first [22u]，compare）; swap_if（first [0u]，first [3u]，compare）; swap_if（first [12u]，first [13u]，compare）; swap_if（first [9u]，first [10u]，compare）; swap_if（first [6u]，first [15u]，compare）; swap_if（first [7u]，first [16u]，compare）; swap_if（first [8u]，first [11u]，compare）; swap_if（first [11u]，first [14u]，compare）; swap_if（first [4u]，first [11u]，compare）; swap_if（first [6u]，first [8u]，compare）; swap_if（first [14u]，first [16u]，compare）; swap_if（first [17u]，first [20u]，compare）; swap_if（first [2u]，first [5u]，compare）; swap_if（first [9u]，first [12u]，compare）; swap_if（first [10u]，first [13u]，compare）; swap_if（first [15u]，first [18u]，compare）; swap_if（first [10u]，first [11u]，compare）; swap_if（first [4u]，first [7u]，compare）; swap_if（first [20u]，first [21u]，compare）; swap_if（first [1u]，first [2u]，compare）; swap_if（first [7u]，first [15u]，compare）; swap_if（first [3u]，first [9u]，compare）; swap_if（first [13u]，first [19u]，compare）; swap_if（first [16u]，first [18u]，compare）; swap_if（first [8u]，first [14u]，compare）; swap_if（first [4u]，first [6u]，compare）; swap_if（first [18u]，first [21u]，compare）; swap_if（first [1u]，first [4u]，compare）; swap_if（first [19u]，first [21u]，compare）; swap_if（first [1u]，first [3u]，compare）; swap_if（first [9u]，first [10u]，compare）; swap_if（first [11u]，first [13u]，compare）; swap_if（first [2u]，first [6u]，compare）; swap_if（first [16u]，first [20u]，compare）; swap_if（first [4u]，first [9u]，compare）; swap_if（first [13u]，first [18u]，compare）; swap_if（first [19u]，first [20u]，compare）; swap_if（first [2u]，first [3u]，compare）; swap_if（first [18u]，first [20u]，compare）; swap_if（first [2u]，first [4u]，compare）; swap_if（first [5u]，first [17u]，compare）; swap_if（first [12u]，first [14u]，compare）; swap_if（first [8u]，first [12u]，compare）; swap_if（first [5u]，first [7u]，compare）; swap_if（first [15u]，first [17u]，compare）; swap_if（first [5u]，first [8u]，compare）; swap_if（first [14u]，first [17u]，compare）; swap_if（第一个[3u]，第一个[5u]，比较）; swap_if（first [17u]，first [19u]，compare）; swap_if（first [3u]，first [4u]，compare）; swap_if（first [18u]，first [19u]，compare）; swap_if（first [6u]，first [10u]，compare）; swap_if（first [11u]，first [16u]，compare）; swap_if（first [13u]，first [16u]，compare）; swap_if（first [6u]，first [9u]，compare）; swap_if（first [16u]，first [17u]，compare）; swap_if（first [5u]，first [6u]，compare）; swap_if（first [4u]，first [5u]，compare）; swap_if（first [7u]，first [9u]，compare）; swap_if（first [17u]，first [18u]，compare）; swap_if（first [12u]，first [15u]，compare）; swap_if（first [14u]，first [15u]，compare）; swap_if（first [8u]，first [12u]，compare）; swap_if（first [7u]，first [8u]，compare）; swap_if（first [13u]，first [15u]，compare）; swap_if（first [15u]，first [17u]，compare）; swap_if（first [5u]，first [7u]，compare）; swap_if（first [9u]，first [10u]，compare）; swap_if（first [10u]，first [14u]，compare）; swap_if（first [6u]，first [11u]，compare）; swap_if（first [14u]，first [16u]，compare）; swap_if（first [15u]，first [16u]，compare）; swap_if（first [6u]，first [7u]，compare）; swap_if（first [10u]，first [11u]，compare）; swap_if（first [9u]，first [12u]，compare）; swap_if（first [11u]，first [13u]，compare）; swap_if（first [13u]，first [14u]，compare）; swap_if（first [8u]，first [9u]，compare）; swap_if（first [7u]，first [8u]，compare）; swap_if（first [14u]，first [15u]，compare）; swap_if（first [9u]，first [10u]，compare）; swap_if（first [8u]，first [9u]，compare）; swap_if（first [12u]，first [14u]，compare）; swap_if（first [11u]，first [12u]，compare）; swap_if（first [12u]，first [13u]，compare）; swap_if（first [10u]，first [11u]，compare）; swap_if（first [11u]，first [12u]，compare）; }

swap_if 函数使用谓词比较两个参数 x 和 y 如果 compare（y，x），则交换它们。我的示例使用一个通用的 swap_if 函数，但如果你知道你将比较 unsigned short 值与运算符< 反正（你可能不需要这样的函数，如果你的编译器识别和优化比较交换，但遗憾的是，并不是所有的编译器都这样 - 我使用g ++ 5.2与 -O3 ，我仍然需要以下功能的性能）：

void swap_if（unsigned short& x，unsigned short& y） { unsigned short dx = x; unsigned short dy = y; unsigned short tmp = x = std :: min（dx，dy）; y ^ = dx ^ tmp; }

现在，为了确保它确实更快， std :: nth_element 当需要部分排序只有前10个元素与排序整个23个元素与排序网络（1000000次与不同混洗阵列）。这是我得到的：

std :: nth_element 1158ms network_sort23 487ms

也就是说，我的电脑运行了一段时间，有点慢，但性能上的差异是整洁的。我相信这个差异将保持不变，当我重新启动我的电脑。我可以稍后尝试，让你知道。

关于这些时间是如何产生的，我使用了一个修改版本的 this benchmark 来自我的 cpp-sort library 。原始排序网络和 swap_if 函数也来自那里，因此您可以确定它们已经被测试了多次：）

编辑：这里是结果，现在我已经重新启动我的电脑。 network_sort23 版本仍然比 std :: nth_element 的快两倍：

std :: nth_element 369ms network_sort23 154ms

EDIT²：如果你需要在中位数中，你可以简单地删除不需要的比较交换单位来计算将在第11个位置的最终值。所得到的大小为23的中位数查找网络使用与前一个大小不同的23分类网络，并且产生稍微更好的结果：

swap_if（first [0u]，first [1u]，compare）; swap_if（first [2u]，first [3u]，compare）; swap_if（first [4u]，first [5u]，compare）; swap_if（first [6u]，first [7u]，compare）; swap_if（first [8u]，first [9u]，compare）; swap_if（first [10u]，first [11u]，compare）; swap_if（first [1u]，first [3u]，compare）; swap_if（first [5u]，first [7u]，compare）; swap_if（first [9u]，first [11u]，compare）; swap_if（first [0u]，first [2u]，compare）; swap_if（first [4u]，first [6u]，compare）; swap_if（first [8u]，first [10u]，compare）; swap_if（first [1u]，first [2u]，compare）; swap_if（first [5u]，first [6u]，compare）; swap_if（first [9u]，first [10u]，compare）; swap_if（first [1u]，first [5u]，compare）; swap_if（first [6u]，first [10u]，compare）; swap_if（first [5u]，first [9u]，compare）; swap_if（first [2u]，first [6u]，compare）; swap_if（first [1u]，first [5u]，compare）; swap_if（first [6u]，first [10u]，compare）; swap_if（first [0u]，first [4u]，compare）; swap_if（first [7u]，first [11u]，compare）; swap_if（first [3u]，first [7u]，compare）; swap_if（first [4u]，first [8u]，compare）; swap_if（first [0u]，first [4u]，compare）; swap_if（first [7u]，first [11u]，compare）; swap_if（first [1u]，first [4u]，compare）; swap_if（first [7u]，first [10u]，compare）; swap_if（first [3u]，first [8u]，compare）; swap_if（first [2u]，first [3u]，compare）; swap_if（first [8u]，first [9u]，compare）; swap_if（first [2u]，first [4u]，compare）; swap_if（first [7u]，first [9u]，compare）; swap_if（first [3u]，first [5u]，compare）; swap_if（first [6u]，first [8u]，compare）; swap_if（first [3u]，first [4u]，compare）; swap_if（first [5u]，first [6u]，compare）; swap_if（first [7u]，first [8u]，compare）; swap_if（first [12u]，first [13u]，compare）; swap_if（first [14u]，first [15u]，compare）; swap_if（first [16u]，first [17u]，比较）; swap_if（first [18u]，first [19u]，compare）; swap_if（first [20u]，first [21u]，compare）; swap_if（first [13u]，first [15u]，compare）; swap_if（first [17u]，first [19u]，compare）; swap_if（first [12u]，first [14u]，compare）; swap_if（first [16u]，first [18u]，compare）; swap_if（first [20u]，first [22u]，compare）; swap_if（first [13u]，first [14u]，compare）; swap_if（first [17u]，first [18u]，compare）; swap_if（first [21u]，first [22u]，compare）; swap_if（first [13u]，first [17u]，compare）; swap_if（first [18u]，first [22u]，compare）; swap_if（first [17u]，first [21u]，compare）; swap_if（first [14u]，first [18u]，compare）; swap_if（first [13u]，first [17u]，compare）; swap_if（first [18u]，first [22u]，compare）; swap_if（first [12u]，first [16u]，compare）; swap_if（first [15u]，first [19u]，compare）; swap_if（first [16u]，first [20u]，compare）; swap_if（first [12u]，first [16u]，compare）; swap_if（first [13u]，first [16u]，compare）; swap_if（first [19u]，first [22u]，compare）; swap_if（first [15u]，first [20u]，compare）; swap_if（first [14u]，first [15u]，compare）; swap_if（first [20u]，first [21u]，compare）; swap_if（first [14u]，first [16u]，compare）; swap_if（first [19u]，first [21u]，compare）; swap_if（first [15u]，first [17u]，compare）; swap_if（first [18u]，first [20u]，compare）; swap_if（first [15u]，first [16u]，compare）; swap_if（first [17u]，first [18u]，compare）; swap_if（first [19u]，first [20u]，compare）; swap_if（first [0u]，first [12u]，compare）; swap_if（first [2u]，first [14u]，compare）; swap_if（first [4u]，first [16u]，compare）; swap_if（第一个[6u]，第一个[18u]，比较）; swap_if（first [8u]，first [20u]，compare）; swap_if（first [10u]，first [22u]，compare）; swap_if（first [2u]，first [12u]，compare）; swap_if（first [10u]，first [20u]，compare）; swap_if（first [4u]，first [12u]，compare）; swap_if（first [6u]，first [14u]，compare）; swap_if（first [8u]，first [16u]，compare）; swap_if（first [10u]，first [18u]，compare）; swap_if（first [8u]，first [12u]，compare）; swap_if（first [10u]，first [14u]，compare）; swap_if（first [10u]，first [12u]，compare）; swap_if（first [1u]，first [13u]，compare）; swap_if（first [3u]，first [15u]，compare）; swap_if（first [5u]，first [17u]，compare）; swap_if（first [7u]，first [19u]，compare）; swap_if（first [9u]，first [21u]，compare）; swap_if（first [3u]，first [13u]，compare）; swap_if（first [11u]，first [21u]，compare）; swap_if（first [5u]，first [13u]，compare）; swap_if（first [7u]，first [15u]，compare）; swap_if（first [9u]，first [17u]，compare）; swap_if（first [11u]，first [19u]，compare）; swap_if（first [9u]，first [13u]，compare）; swap_if（first [11u]，first [15u]，compare）; swap_if（first [11u]，first [13u]，compare）; swap_if（first [11u]，first [12u]，compare）;

可能有更聪明的方法来生成中位数查找网络，已经对这一主题进行了广泛的研究。因此，它可能是你现在可以使用的最好的方法。结果不是很棒，但它仍然使用104比较交换单位，而不是118.

I did not find this specific topic anywhere...

I am calling the nth_element() algorithm about 400,000 times per second on different data in a std::vector of 23 integers, more precise "unsigned short" values.

I want to improve computation speed and this particular call needs a significant portion of CPU time. Now I noted, as with std::sort(), that the nth_element function is visible in the profiler even with highest optimisation level and NDEBUG mode (Linux Clang compiler), so the comparison is inlined but not the function call itself. Well, more preise: not nth_element() but std::__introselect() is visible.

Since the size of the data is small, I experimented with using a quadratic sorting function PIKSORT, which is often quicker than calling std::sort when the size of data is less than 20 elements, probably because the function will be inline.

template <class CONTAINER> inline void piksort(CONTAINER& arr) // indeed this is "insertion sort" { typename CONTAINER::value_type a; const int n = (int)arr.size(); for (int j = 1; j<n; ++j) { a = arr[j]; int i = j; while (i > 0 && a < arr[i - 1]) { arr[i] = arr[i - 1]; i--; } arr[i] = a; } }

However this was slower than using nth_element in this case.

Also, using a statistical method is not appropriate, Something faster than std::nth_element

Finally, since the values are in the range from 0 to about 20000, a histogram method does not look appropriate.

My question: does anyone know a simple solution to this? I think I am probably not the only one to have to call std::sort or nth_element very frequently.

解决方案

You mentioned that the size of the array was always known to be 23. Moreover, the type used is unsigned short. In this case, you might try to use a sorting network of size 23; since your type is unsigned short, sorting the whole array with a sorting network might be even faster than partially sorting it with std::nth_element. Here is a very straightforward C++14 implementation of a sorting network of size 23 with 118 compare-exchange units, as described by Using Symmetry and Evolutionary Search to Minimize Sorting Networks:

template<typename RandomIt, typename Compare = std::less<>> void network_sort23(RandomIt first, Compare compare={}) { swap_if(first[1u], first[20u], compare); swap_if(first[2u], first[21u], compare); swap_if(first[5u], first[13u], compare); swap_if(first[9u], first[17u], compare); swap_if(first[0u], first[7u], compare); swap_if(first[15u], first[22u], compare); swap_if(first[4u], first[11u], compare); swap_if(first[6u], first[12u], compare); swap_if(first[10u], first[16u], compare); swap_if(first[8u], first[18u], compare); swap_if(first[14u], first[19u], compare); swap_if(first[3u], first[8u], compare); swap_if(first[4u], first[14u], compare); swap_if(first[11u], first[18u], compare); swap_if(first[2u], first[6u], compare); swap_if(first[16u], first[20u], compare); swap_if(first[0u], first[9u], compare); swap_if(first[13u], first[22u], compare); swap_if(first[5u], first[15u], compare); swap_if(first[7u], first[17u], compare); swap_if(first[1u], first[10u], compare); swap_if(first[12u], first[21u], compare); swap_if(first[8u], first[19u], compare); swap_if(first[17u], first[22u], compare); swap_if(first[0u], first[5u], compare); swap_if(first[20u], first[21u], compare); swap_if(first[1u], first[2u], compare); swap_if(first[18u], first[19u], compare); swap_if(first[3u], first[4u], compare); swap_if(first[21u], first[22u], compare); swap_if(first[0u], first[1u], compare); swap_if(first[19u], first[22u], compare); swap_if(first[0u], first[3u], compare); swap_if(first[12u], first[13u], compare); swap_if(first[9u], first[10u], compare); swap_if(first[6u], first[15u], compare); swap_if(first[7u], first[16u], compare); swap_if(first[8u], first[11u], compare); swap_if(first[11u], first[14u], compare); swap_if(first[4u], first[11u], compare); swap_if(first[6u], first[8u], compare); swap_if(first[14u], first[16u], compare); swap_if(first[17u], first[20u], compare); swap_if(first[2u], first[5u], compare); swap_if(first[9u], first[12u], compare); swap_if(first[10u], first[13u], compare); swap_if(first[15u], first[18u], compare); swap_if(first[10u], first[11u], compare); swap_if(first[4u], first[7u], compare); swap_if(first[20u], first[21u], compare); swap_if(first[1u], first[2u], compare); swap_if(first[7u], first[15u], compare); swap_if(first[3u], first[9u], compare); swap_if(first[13u], first[19u], compare); swap_if(first[16u], first[18u], compare); swap_if(first[8u], first[14u], compare); swap_if(first[4u], first[6u], compare); swap_if(first[18u], first[21u], compare); swap_if(first[1u], first[4u], compare); swap_if(first[19u], first[21u], compare); swap_if(first[1u], first[3u], compare); swap_if(first[9u], first[10u], compare); swap_if(first[11u], first[13u], compare); swap_if(first[2u], first[6u], compare); swap_if(first[16u], first[20u], compare); swap_if(first[4u], first[9u], compare); swap_if(first[13u], first[18u], compare); swap_if(first[19u], first[20u], compare); swap_if(first[2u], first[3u], compare); swap_if(first[18u], first[20u], compare); swap_if(first[2u], first[4u], compare); swap_if(first[5u], first[17u], compare); swap_if(first[12u], first[14u], compare); swap_if(first[8u], first[12u], compare); swap_if(first[5u], first[7u], compare); swap_if(first[15u], first[17u], compare); swap_if(first[5u], first[8u], compare); swap_if(first[14u], first[17u], compare); swap_if(first[3u], first[5u], compare); swap_if(first[17u], first[19u], compare); swap_if(first[3u], first[4u], compare); swap_if(first[18u], first[19u], compare); swap_if(first[6u], first[10u], compare); swap_if(first[11u], first[16u], compare); swap_if(first[13u], first[16u], compare); swap_if(first[6u], first[9u], compare); swap_if(first[16u], first[17u], compare); swap_if(first[5u], first[6u], compare); swap_if(first[4u], first[5u], compare); swap_if(first[7u], first[9u], compare); swap_if(first[17u], first[18u], compare); swap_if(first[12u], first[15u], compare); swap_if(first[14u], first[15u], compare); swap_if(first[8u], first[12u], compare); swap_if(first[7u], first[8u], compare); swap_if(first[13u], first[15u], compare); swap_if(first[15u], first[17u], compare); swap_if(first[5u], first[7u], compare); swap_if(first[9u], first[10u], compare); swap_if(first[10u], first[14u], compare); swap_if(first[6u], first[11u], compare); swap_if(first[14u], first[16u], compare); swap_if(first[15u], first[16u], compare); swap_if(first[6u], first[7u], compare); swap_if(first[10u], first[11u], compare); swap_if(first[9u], first[12u], compare); swap_if(first[11u], first[13u], compare); swap_if(first[13u], first[14u], compare); swap_if(first[8u], first[9u], compare); swap_if(first[7u], first[8u], compare); swap_if(first[14u], first[15u], compare); swap_if(first[9u], first[10u], compare); swap_if(first[8u], first[9u], compare); swap_if(first[12u], first[14u], compare); swap_if(first[11u], first[12u], compare); swap_if(first[12u], first[13u], compare); swap_if(first[10u], first[11u], compare); swap_if(first[11u], first[12u], compare); }

The swap_if utility function compares two parameters x and y with the predicate compare and swaps them if compare(y, x). My example uses a a generic swap_if function, but you can used an optimized version if you known that you will be comparing unsigned short values with operator< anyway (you might not need such a function if your compiler recognizes and optimizes the compare-exchange, but unfortunately, not all compilers do that - I am using g++5.2 with -O3 and I still need the following function for performance):

void swap_if(unsigned short& x, unsigned short& y) { unsigned short dx = x; unsigned short dy = y; unsigned short tmp = x = std::min(dx, dy); y ^= dx ^ tmp; }

Now, just to make sure that it is indeed faster, I decided to time std::nth_element when required to partial sort only the first 10 elements vs. sorting the whole 23 elements with the sorting network (1000000 times with different shuffled arrays). Here is what I get:

std::nth_element 1158ms network_sort23 487ms

That said, my computer has been running for a bit of time and is a bit slow, but the difference in performance is neat. I believe that this difference will remain the same when I restart my computer. I may try it later and let you know.

Regarding how these times were generated, I used a modified version of this benchmark from my cpp-sort library. The original sorting network and swap_if functions come from there as well, so you can be sure that they have been tested more than once :)

EDIT: here are the results now that I have restarted my computer. The network_sort23 version is still two times faster than std::nth_element:

std::nth_element 369ms network_sort23 154ms

EDIT²: if all you need in the median, you can trivially delete the compare-exchange units that are not needed to compute the final value that will be at the 11th position. The resulting median-finding network of size 23 that follows uses a different size-23 sorting network than the previous one, and it yields slightly better results:

swap_if(first[0u], first[1u], compare); swap_if(first[2u], first[3u], compare); swap_if(first[4u], first[5u], compare); swap_if(first[6u], first[7u], compare); swap_if(first[8u], first[9u], compare); swap_if(first[10u], first[11u], compare); swap_if(first[1u], first[3u], compare); swap_if(first[5u], first[7u], compare); swap_if(first[9u], first[11u], compare); swap_if(first[0u], first[2u], compare); swap_if(first[4u], first[6u], compare); swap_if(first[8u], first[10u], compare); swap_if(first[1u], first[2u], compare); swap_if(first[5u], first[6u], compare); swap_if(first[9u], first[10u], compare); swap_if(first[1u], first[5u], compare); swap_if(first[6u], first[10u], compare); swap_if(first[5u], first[9u], compare); swap_if(first[2u], first[6u], compare); swap_if(first[1u], first[5u], compare); swap_if(first[6u], first[10u], compare); swap_if(first[0u], first[4u], compare); swap_if(first[7u], first[11u], compare); swap_if(first[3u], first[7u], compare); swap_if(first[4u], first[8u], compare); swap_if(first[0u], first[4u], compare); swap_if(first[7u], first[11u], compare); swap_if(first[1u], first[4u], compare); swap_if(first[7u], first[10u], compare); swap_if(first[3u], first[8u], compare); swap_if(first[2u], first[3u], compare); swap_if(first[8u], first[9u], compare); swap_if(first[2u], first[4u], compare); swap_if(first[7u], first[9u], compare); swap_if(first[3u], first[5u], compare); swap_if(first[6u], first[8u], compare); swap_if(first[3u], first[4u], compare); swap_if(first[5u], first[6u], compare); swap_if(first[7u], first[8u], compare); swap_if(first[12u], first[13u], compare); swap_if(first[14u], first[15u], compare); swap_if(first[16u], first[17u], compare); swap_if(first[18u], first[19u], compare); swap_if(first[20u], first[21u], compare); swap_if(first[13u], first[15u], compare); swap_if(first[17u], first[19u], compare); swap_if(first[12u], first[14u], compare); swap_if(first[16u], first[18u], compare); swap_if(first[20u], first[22u], compare); swap_if(first[13u], first[14u], compare); swap_if(first[17u], first[18u], compare); swap_if(first[21u], first[22u], compare); swap_if(first[13u], first[17u], compare); swap_if(first[18u], first[22u], compare); swap_if(first[17u], first[21u], compare); swap_if(first[14u], first[18u], compare); swap_if(first[13u], first[17u], compare); swap_if(first[18u], first[22u], compare); swap_if(first[12u], first[16u], compare); swap_if(first[15u], first[19u], compare); swap_if(first[16u], first[20u], compare); swap_if(first[12u], first[16u], compare); swap_if(first[13u], first[16u], compare); swap_if(first[19u], first[22u], compare); swap_if(first[15u], first[20u], compare); swap_if(first[14u], first[15u], compare); swap_if(first[20u], first[21u], compare); swap_if(first[14u], first[16u], compare); swap_if(first[19u], first[21u], compare); swap_if(first[15u], first[17u], compare); swap_if(first[18u], first[20u], compare); swap_if(first[15u], first[16u], compare); swap_if(first[17u], first[18u], compare); swap_if(first[19u], first[20u], compare); swap_if(first[0u], first[12u], compare); swap_if(first[2u], first[14u], compare); swap_if(first[4u], first[16u], compare); swap_if(first[6u], first[18u], compare); swap_if(first[8u], first[20u], compare); swap_if(first[10u], first[22u], compare); swap_if(first[2u], first[12u], compare); swap_if(first[10u], first[20u], compare); swap_if(first[4u], first[12u], compare); swap_if(first[6u], first[14u], compare); swap_if(first[8u], first[16u], compare); swap_if(first[10u], first[18u], compare); swap_if(first[8u], first[12u], compare); swap_if(first[10u], first[14u], compare); swap_if(first[10u], first[12u], compare); swap_if(first[1u], first[13u], compare); swap_if(first[3u], first[15u], compare); swap_if(first[5u], first[17u], compare); swap_if(first[7u], first[19u], compare); swap_if(first[9u], first[21u], compare); swap_if(first[3u], first[13u], compare); swap_if(first[11u], first[21u], compare); swap_if(first[5u], first[13u], compare); swap_if(first[7u], first[15u], compare); swap_if(first[9u], first[17u], compare); swap_if(first[11u], first[19u], compare); swap_if(first[9u], first[13u], compare); swap_if(first[11u], first[15u], compare); swap_if(first[11u], first[13u], compare); swap_if(first[11u], first[12u], compare);

There are probably smarter ways to generate median-finding networks, but I don't think that extensive research has been done on the subject. Therefore, it's probably the best method you can use as of now. The result isn't awesome but it still uses 104 compare-exchange units instead of 118.