Ideal Batcher ímpar-par mesclar redes para tamanhos diferentes de 2 ^ n

9

Atualmente, tenho tentado implementar redes de classificação até o tamanho 32 com um número mínimo de unidades de comparação (ótimo tamanho , não em profundidade ) . A partir de agora, pude usar os seguintes recursos para gerar minhas redes:

O artigo Como encontrar melhores redes de classificação por Baddar fornece o número mínimo de unidades de troca de comparação conhecidas como necessárias para classificar as redes de 0 a 32 (não atualizadas, já que Valsalam e Miikkulainen fornecem melhores algoritmos para os tamanhos 17, 18, 19, 20, 21 e 22) e o método usado para localizá-los: basicamente, é preciso dividir a matriz para classificar em duas, depois classificar as duas metades usando as redes de classificação mais conhecidas para esses tamanhos antes de mesclá-las usando uma rede de mesclagem ímpar (que corresponde à etapa de mesclagem de mesclador ímpar de lotes do Batch ).

A página da Wikipedia fornece a seguinte implementação do Python para o mesclador ímpar de pares do Batch:

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)

A etapa oddeven_merge já está isolada, por isso foi fácil usá-la sozinha para gerar os pares de índices necessários para mesclar as duas metades classificadas da matriz original. No entanto, essa implementação só funciona quando o tamanho da matriz é uma potência de 2. Portanto, só me permitiu encontrar o número mínimo conhecido de unidades de troca de comparação necessárias para uma rede de classificação de tamanho 32. Removendo os pares de índices com o tamanho o índice mais alto me permitiu encontrar a rede de classificação equivalente do tamanho 31, mas remover mais pares não produziu os resultados mais conhecidos para tamanhos menores que 31.

O módulo Algorithm::Networksort do Perl fornece uma implementação ímpar-uniforme do mesmo que funciona com arrays de qualquer tamanho, não apenas potências de 2. Por isso, decidi dar uma olhada para ver se eu poderia extrair o passo de mesclagem do algoritmo. Aqui está o equivalente em Python (ele também corresponde ao algoritmo descrito por Knuth em A Arte da Programação de Computador, volume 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

Infelizmente, este algoritmo parece um pouco enigmático para os meus olhos, e eu não consegui extrair a parte da fusão. Consegui derivar uma rede de fusão que me deu o número mínimo conhecido de unidades de troca de comparação necessárias para uma rede de classificação de tamanho 24, mas o truque que usei não escalou para nenhum outro tamanho (e, do meu ponto de vista, definitivamente não uma mesclagem ímpar).

Eu tentei mais algumas coisas para adaptar a etapa de mesclagem do fusível-ímpar do Batcher para matrizes cujo tamanho não é uma potência de dois, mas não consegui encontrar as redes de classificação mais conhecidas para tamanhos 25, 26, 27, 28, 29 e 30. Como posso derivar essa etapa de mesclagem para encontrar as peças que faltam no quebra-cabeça?

    
por Morwenn 24.10.2015 в 18:20
fonte

1 resposta

2

O algoritmo Perl menciona em um comentário que é algoritmo 5.2.2M na Pesquisa e Classificação de Knuth.

Por sua vez, Knuth menciona que mescla as sequências classificadas com p = 1 . Então, para gerar seus pares que mesclam a sequência para qualquer N, basta executar o algoritmo com 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

Observe que o passo de mesclagem ímpar-par de Batcher espera que as sequências classificadas intercaladas (par, ímpar, par, ...), mas produzam uma sequência classificada que seja contígua.

Por exemplo, para N = 25, gera a seguinte rede:

    
por orlp 01.12.2015 / 17:45
fonte