パック展開とバイトニックソート

結構前の、constexpr関数を高速化する方法 - よーるという記事で、低速なconstexpr文脈の中でもある程度の速さで配列操作を行う方法として、パック展開を利用した配列を一気に構築する手法を紹介しました。

これを利用したバイトニックソートは、たとえば私の作った lfl/lfl.hpp at master · lpha-z/lfl · GitHub （171行目から201行目）があります。

私が書く前に存在した実装としては、bitonic_sort.hpp · GitHubなどでしょうか。

ところで、パック展開を用いると、シャッフル的なことが簡単にできます。

#include <array>
#include <utility>

template<class T, std::size_t N>
constexpr T comparator( const std::array<T, N>& arr, std::size_t i, std::size_t j ) {
    return i < j ^ arr.at(i) < arr.at(j) ? arr.at(i) : arr.at(j);
}

template<class T, std::size_t N, std::size_t... Indeces>
constexpr std::array<T, N> sorter_impl( const std::array<T, N>& arr, std::index_sequence<Indeces...> ) {
    return std::array { comparator( arr, Indeces, Indeces^1 )... };
}

template<class T, std::size_t N>
constexpr std::array<T, N> sorter( const std::array<T, N>& arr ) {
    return sorter_impl( arr, std::make_index_sequence<N>{} );
}

template<std::size_t... Indeces>
constexpr auto swapper = []( const auto& arr ) { return std::array { arr[Indeces]... }; };
    
constexpr auto sort = []( auto arr ) {
    arr = sorter( arr );
    arr = swapper<0,3,1,2,4,7,5,6>( arr );
    arr = sorter( arr );
    arr = swapper<0,2,3,1,4,6,7,5>( arr );
    arr = sorter( arr );
    arr = swapper<0,7,1,6,2,5,3,4>( arr );
    arr = sorter( arr );
    arr = swapper<0,4,2,6,7,3,5,1>( arr );
    arr = sorter( arr );
    arr = swapper<0,2,1,3,4,6,5,7>( arr );
    arr = sorter( arr );
    return arr;
};    

#include <iostream>
int main()
{
    constexpr auto arr = sort( std::array { 1, 2, 5, 4, 6, 3, 7, 0 } );
    for( auto e : arr ) { std::cout << e << std::endl; }
}

上のコードの、swapperという関数で、配列の要素をシャッフルしています。関数ではなくラムダ式を使っているのは、引数のところをautoと書きたかったからです。こうすることで、template<class T, std::size_t N>のように書かなくて済むようになり、swapper関数のテンプレート引数部分にシャッフルする順番のみを書くことができます。

もちろん、このようなコードは配列の書き換えが多く非効率的です。ソートした結果をシャッフルする部分はひとまとめにできるので、以下のように改善が可能です。

#include <array>
#include <utility>

template<class T, std::size_t N>
constexpr T comparator( const std::array<T, N>& arr, std::size_t i, std::size_t j ) {
    return i < j ^ arr.at(i) < arr.at(j) ? arr.at(i) : arr.at(j);
}

template<std::size_t... Indeces>
constexpr auto swapper = []( const auto& arr ) { return std::array { comparator( arr, Indeces, Indeces^1 )... }; };
    
constexpr auto sort = []( auto arr ) {
    arr = swapper<0,3,1,2,4,7,5,6>( arr );
    arr = swapper<0,2,3,1,4,6,7,5>( arr );
    arr = swapper<0,7,1,6,2,5,3,4>( arr );
    arr = swapper<0,4,2,6,7,3,5,1>( arr );
    arr = swapper<0,2,1,3,4,6,5,7>( arr );
    arr = swapper<0,1,2,3,4,5,6,7>( arr );

    return arr;
};    

#include <iostream>
int main()
{
    constexpr auto arr = sort( std::array { 1, 2, 5, 4, 6, 3, 7, 0 } );
    for( auto e : arr ) { std::cout << e << std::endl; }
}

このようにしてもアクセスする順序が乱れているため高速ではないでしょう。このようなバイトニックソートの亜種は大量に存在します。

それにしても、（ハードコードされているとはいえ）こんな単純なコードでバイトニックソート（の亜種）が書けるパック展開は便利ですね。