最佳Batcher奇偶合并网络的大小不同于2 ^ n

Question

这些天,我一直在尝试使用最少数量的比较交换单元(最大尺寸,而不是深度)实现最大尺寸为32的分拣网络.截至目前,我已经能够使用以下资源来生成我的网络:

• 排序网络0到16:Perl的Algorithm::Networksort模块采用"最佳"算法.不幸的是,它只提供最知名的网络直到16号.

• 排序网络17至23:使用对称和进化搜索来最小化 Valsalam和Miikkulainen的排序网络.

纸张找到更好的排序网络通过Baddar给出已知有需要用于分拣网络0〜32比较-交换单元的最小数目(未最多到时间Valsalam和Miikkulainen为尺寸17,18,19提供更好的算法, 20,21和22)以及用于查找它们的方法:基本上,必须将数组拆分为两个排序,然后使用最知名的排序网络对这些大小进行排序,然后使用奇偶合并网络合并它们(这对应于Batcher的奇偶合并的合并步骤).

维基百科页面为Batcher的奇偶合并提供了以下Python实现:

def oddeven_merge(lo, hi, r):
    step = r * 2
    if step < hi - lo:
        yield from oddeven_merge(lo, hi, step)
        yield from oddeven_merge(lo + r, hi, step)
        yield from [(i, i + r) for i in range(lo + r, hi - r, step)]
    else:
        yield (lo, lo + r)

def oddeven_merge_sort_range(lo, hi):
    """ sort the part of x with indices between lo and hi.

    Note: endpoints (lo and hi) are included.
    """
    if (hi - lo) >= 1:
        # if there is more than one element, split the input
        # down the middle and first sort the first and second
        # half, followed by merging them.
        mid = lo + ((hi - lo) // 2)
        yield from oddeven_merge_sort_range(lo, mid)
        yield from oddeven_merge_sort_range(mid + 1, hi)
        yield from oddeven_merge(lo, hi, 1)

def oddeven_merge_sort(length):
    """ "length" is the length of the list to be sorted.
    Returns a list of pairs of indices starting with 0 """
    yield from oddeven_merge_sort_range(0, length - 1)

该oddeven_merge步骤已经被隔离,因此很容易单独使用它来生成合并原始数组的两个有序半部分所需的索引对.但是,此实现仅在数组大小为2时才有效.因此,它只允许我找到大小为32的排序网络所需的最小已知数量的比较交换单元.删除索引对最高指数允许我找到大小为31的等效排序网络,但是对于小于31的大小,删除更多对不会产生最佳已知结果.

Perl的Algorithm::Networksort模块提供了一个替代Batcher的奇偶合并实现,它适用于任何大小的数组,而不仅仅是2的幂.因此,我决定看看它是否可以从算法中提取合并步骤.这是Python的等价物(它也对应于Knuth在The Computer of Computer Programming第3卷中描述的算法):

def oddeven_merge_sort(length):
    t = math.ceil(math.log2(length))

    p = 2 ** (t - 1)

    while p > 0:
        q = 2 ** (t - 1)
        r = 0
        d = p

        while d > 0:
            for i in range(length - d):
                if i & p == r:
                    yield (i, i + d)

            d = q - p
            q //= 2
            r = p
        p //= 2

不幸的是,这个算法对我来说似乎有些神秘,我根本无法从中提取合并部分.我设法得到一个合并网络,它给了我24小时排序网络所需的最小数量的比较交换单元,但我使用的技巧没有扩展到任何其他尺寸(根据我的理解,它绝对不是奇数合并).

我已经尝试了一些更多的东西来调整Batcher的奇偶合并的合并步骤,对于大小不是2的幂的数组,但我无法找到最适合大小的分类网络25,26,27 ,28,29和30.如何找到合并步骤以找到拼图的缺失部分？

Answer 1

Perl算法在评论中提到它是Knuth's Searching and Sorting中的算法5.2.2M。

反过来，Knuth 提到当p = 1时，它将排序的序列合并在一起。因此，要生成合并任意 N 序列的对，只需运行p = 1 的算法：

def oddeven_merge_step(length):
    t = math.ceil(math.log2(length))
    q = 2 ** (t - 1)
    r = 0
    d = 1

    while d > 0:
        for i in range(length - d):
            if i & 1 == r:
                yield (i, i + d)

        d = q - 1
        q //= 2
        r = 1

请注意，Batcher 的奇偶合并步骤期望排序序列交错（偶数、奇数、偶数……），但会生成连续的排序序列。

例如，对于 N = 25，它生成以下网络：