Optimal Batcher sieci nieparzystej parzystej parzystej dla rozmiarów innych niż 2^n

Question

W dzisiejszych czasach próbowałem wdrażać sieci sortujące do rozmiaru 32 z minimalną liczbą jednostek porównywania-jednostek (optymalne w rozmiarze rozmiar, nie w głębokość). Jak na razie udało mi się skorzystać z następujących zasobów do generowania moje sieci:

• sieć sortująca 0 Thru 16: Algorithm::Networksort module z „Best” algorytm Perla. Niestety, zapewnia tylko najbardziej znane sieci do rozmiaru 16.

• Sortowanie sieci 17 do 23: Using Symmetry and Evolutionary Search to Minimize Sorting Networks przez Valsalam i Miikkulainen.

Papier Finding Better Sorting Networks przez Baddar daje minimalną liczbę jednostek porównać wymiany wiadomo, że są potrzebne do sortowania sieci 0 do 32 (nie up-to-date od Valsalam i Miikkulainen zapewnienia lepszych algorytmów dla wielkości 17, 18, 19, 20, 21 i 22) i sposób ich znalezienia: w zasadzie trzeba rozdzielić tablicę, aby sortować na dwie części, a następnie sortować obie połówki przy użyciu najlepiej znanych sieci sortujących dla tych rozmiarów przed połączeniem ich za pomocą nieparzystej - nawet sieć łącząca (co odpowiada etapowi scalania z Batcher's odd-even mergesort).

Strona Wikipedia podaje następujący wdrożenie Pythona do Dozowniki dziwne nawet mergesort:

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) 

Etap oddeven_merge już izolowane, więc łatwo było go używać samodzielnie do generowania pary wskaźników potrzebnych do scalania dwie posortowane połówki oryginalnej tablicy. Jednak ta implementacja działa tylko wtedy, gdy rozmiar macierzy jest potęgą 2. Z tego względu pozwolił mi tylko znaleźć minimalną znaną liczbę jednostek porównywania danych potrzebnych do sortowania sieci o rozmiarze 32. Usunięcie par indeksów z najwyższy indeks pozwolił mi znaleźć równoważną sieć sortującą o rozmiarze 31, ale usunięcie większej liczby par nie przyniosło najlepiej znanych wyników dla rozmiarów mniejszych niż 31.

Moduł Perla Algorithm::Networksort zapewnia alternatywną implementację scalesortu Batchera, która działa z tablicami dowolnej wielkości, nie tylko z potęgą 2. Postanowiłem więc rzucić okiem na to, czy mogę wyodrębnić krok scalania z algorytmu. Oto odpowiednik Python (również odpowiada algorytm opisany przez Knuth w Sztuka programowania vol 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 

Niestety, ten algorytm wydaje się nieco tajemnicze moich oczach, a ja nie był w stanie w ogóle wyodrębnić z niego części scalającej. Udało mi się wyprowadzić łączącą się sieć, która dała mi minimalną znaną liczbę porównywalnych jednostek potrzebnych do sortowania sieci o rozmiarze 24, ale sztuczka, której użyłem, nie była skalowalna do żadnych innych rozmiarów (iz mojego zrozumienia, zdecydowanie nie było dziwne-parzyste połączenie).

Próbowałem jeszcze kilku rzeczy, aby zaadaptować krok scalania z dziwnego - nawet scalesortu Batchera dla macierzy, których rozmiar nie jest potęgą dwóch, ale nie byłem w stanie znaleźć najlepiej znanych sieci sortujących dla rozmiarów 25 , 26, 27, 28, 29 i 30. Jak mogę uzyskać ten krok scalania, aby znaleźć brakujące elementy układanki?

Answer 1

Algorytm Perla mentions in a comment, który jest algorytmem 5.2.2M w wyszukiwaniu i sortowaniu Knutha.

Z kolei Knuth wspomina, że ​​łączy posortowane sekwencje z czasem, gdy p = 1. Więc do generowania pary, które łączą sekwencję dla każdego N wystarczy uruchomić algorytm z 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 

Zauważ, że Dozowniki dziwne, nawet połączyć krok spodziewa posortowanych sekwencje przeplatane (even, odd , nawet, ...), ale tworzy posortowaną sekwencję, która jest ciągła.

Na przykład dla N = 25 generuje następujące sieci: