LoginSignup
88
28

More than 3 years have passed since last update.

@angeartin株式会社 DeNA Games Tokyo

闇の力を駆使すればO(1)でスターリンソートなぞ容易いものよ

Last updated at Posted at 2019-07-31

そう...Templateならね！！！

スターリンソートとは

なんと$O(N)$でソートが終了するという、実行速度にハートフルでピースフルなアルゴリズムです。
ピースフルなのでソート順に並んでいない要素は粛清されます。

公式リポジトリ

スターリンソートは素晴らしいアルゴリズムなので、なんと公式リポジトリが存在します。
素敵:relaxed:
https://github.com/gustavo-depaula/stalin-sort

先駆者達

計算量O(n)の画期的なソートアルゴリズムであるスターリンソートをHaskell で実装してみた #Haskell
計算量O(n)で噂のスターリンソートを実装してみた
[Rust] スターリンソートと PartialOrd
rubyでスターリンソートをやってみた（ブロック渡しも可能）
スターリンソート in perl
話題の粛清ソートアルゴリズム「スターリンソート」をPythonで実装した
Pythonワンライナーでスターリンソート

更に高みへ

コンパイルタイムで計算すれば$O(1)$なのでは？と思ったので実装しました。:sunglasses:

実装

若干余計なコードが含まれているかもしれない

#include <iostream>
#include <utility>

template<int...Seq>
using seq = std::integer_sequence<int, Seq...>;

template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01;


template <class Result>
struct stalin_sort_stopper {
    using result = Result;
};
// nextを展開するwrap
template<class Result, int CompTarget, int...Next>
constexpr stalin_sort_impl_01<Result, sizeof...(Next), CompTarget, Next...> stalin_sort_next_wrapper(seq<CompTarget,Next...>) {};
template<class Result>
constexpr stalin_sort_stopper<Result> stalin_sort_next_wrapper(seq<>){};


//seqへinsertする
template<int I, int... Seq>
constexpr seq<Seq...,I> insert(seq<Seq...>) {};

// Target粛清
template<class Result, bool Comp, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01 {
    using next = seq<CompTarget, Rest...>;
    using result = Result;
};

// Target同胞
template<class Result, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01<Result, true, CompTarget, InsertTarget, Rest...> {
    using next = seq<CompTarget, Rest...>;
    using result = decltype(insert<InsertTarget>(Result{}));
};

template<class Result, class Next>
struct stalin_sort_holder_detail : decltype(stalin_sort_next_wrapper<Result>(Next{})) {};
template<class Holder>
struct stalin_sort_holder : stalin_sort_holder_detail<typename Holder::result,typename Holder::next> {};

template<class Result, int A, int B, int ...Rest>
struct stalin_sort_impl_comp_insert : 
    stalin_sort_holder<
        stalin_sort_impl_comp_insert_01<Result, (A <= B), (A <= B) ? B:A, B, Rest...>
    > {};

// result, target, rest_size, rest
// rest_size > 1なら targetとrestのheadを比較
// rest_size = 0ならresult展開して終了
template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01 : stalin_sort_impl_comp_insert<Result, Target, Rest...> {};

template<class Result, int Target, int ...Rest>
struct stalin_sort_impl_01<Result, 0u, Target, Rest...> {
    using result = Result;
};

template<int Target, int...Rest>
struct stalin_sort : stalin_sort_impl_01<seq<Target>, sizeof...(Rest), Target, Rest...> {};

// printer
template<int Head, int ...Tail>
void print_impl() {
    auto& out = std::cout;
    out << Head;
    using expander = int[];
    (void)expander{0, (void(out << ',' << Tail), 0)...};
    out << std::endl;
}


template<int ...Seq>
void print(seq<Seq...>) {
    print_impl<Seq...>();
}



int main() {
    print(typename stalin_sort<0>::result{}); // => 0
    print(typename stalin_sort<2,3>::result{});
    print(typename stalin_sort<2,1,3>::result{}); // => 2,3
    print(typename stalin_sort<1,2,3,4,5>::result{}); // => 1,2,3,4,5
    print(typename stalin_sort<2,1,3,3,2,5,6>::result{}); // => 2,3,3,5,6
    return 0;
}

解説っぽいもの

stalin_sort（エントリ関数）

template<int Target, int...Rest>
struct stalin_sort : stalin_sort_impl_01<seq<Target>, sizeof...(Rest), Target, Rest...> {};

まず、ここで入力された数列に対してTargetとRestに分解し、先頭の数値をseq<Target>へ保持します。sizeof...(Rest)によって残りの数列の長さを取得しています。

stalin_sort_impl_01

// result, target, rest_size, rest
// rest_size > 1なら targetとrestのheadを比較
// rest_size = 0ならresult展開して終了
template<class Result, size_t RestSize, int Target, int ...Rest>
struct stalin_sort_impl_01 : stalin_sort_impl_comp_insert<Result, Target, Rest...> {};

template<class Result, int Target, int ...Rest>
struct stalin_sort_impl_01<Result, 0u, Target, Rest...> {
    using result = Result;
};

stalin_sort_impl_01はreduceと同じような仕組みでresultにデータを蓄積していく手法を取っています。また、ここでRestの長さが0の場合にResultを返しています。

比較と粛清

// Target粛清
template<class Result, bool Comp, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01 {
    using next = seq<CompTarget, Rest...>;
    using result = Result;
};

// Target同胞
template<class Result, int CompTarget, int InsertTarget, int ...Rest>
struct stalin_sort_impl_comp_insert_01<Result, true, CompTarget, InsertTarget, Rest...> {
    using next = seq<CompTarget, Rest...>;
    using result = decltype(insert<InsertTarget>(Result{}));
};

template<class Result, class Next>
struct stalin_sort_holder_detail : decltype(stalin_sort_next_wrapper<Result>(Next{})) {};
template<class Holder>
struct stalin_sort_holder : stalin_sort_holder_detail<typename Holder::result,typename Holder::next> {};

template<class Result, int A, int B, int ...Rest>
struct stalin_sort_impl_comp_insert : 
    stalin_sort_holder<
        stalin_sort_impl_comp_insert_01<Result, (A <= B), (A <= B) ? B:A, B, Rest...>
    > {};

比較関数の本体です。(A <= B) ? B : Aがキモで、比較対象の更新をここで行なっています。
stalin_sort_impl_comp_insert_01で(A <= B)による場合分けを行い、粛清したりしなかったりしています。
その結果をstalin_sort_holderとstalin_sort_holder_detailで取り出してstalin_sort_next_wrapperに渡します。
stalin_sort_next_wrapperはseq型になっているNextを展開し、CompTargetとNext...のパラメーターパックを取り出すためのトリックです。この中でstalin_sort_impl_01が呼び出されることによって再帰的に計算を実行できています。

Seqを展開して標準出力に表示する

// printer
template<int Head, int ...Tail>
void print_impl() {
    auto& out = std::cout;
    out << Head;
    using expander = int[];
    (void)expander{0, (void(out << ',' << Tail), 0)...};
    out << std::endl;
}


template<int ...Seq>
void print(seq<Seq...>) {
    print_impl<Seq...>();
}

seq型を展開してprintする為のイディオムです。int[]の直接初期化構文内でパラメーター展開が利用できる事を使用して出力文を書き、コンマ演算子によって0に評価した後、(void)で何もなかったことにしています。

結果

int main() {
    print(typename stalin_sort<0>::result{}); // => 0
    print(typename stalin_sort<2,3>::result{});
    print(typename stalin_sort<2,1,3>::result{}); // => 2,3
    print(typename stalin_sort<1,2,3,4,5>::result{}); // => 1,2,3,4,5
    print(typename stalin_sort<2,1,3,3,2,5,6>::result{}); // => 2,3,3,5,6
    return 0;
}

以上を用いることで無事$O(1)$でスターリンソートを実装することができました。

めでたしめでたし:tada:

Online Demo

PR

折角なのでPR出しておきました。レギュレーション違反だから通るかどうか心配だな:confounded:
https://github.com/gustavo-depaula/stalin-sort/pull/35

二度とやりたくない

追記1: 無事Mergeされました

image.png
や　っ　た　ぜ

追記2: 闇の同胞

闇の同胞がC++17でよりスマートに書いてくださいました！（PRを出すのです……）

88
28
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
88
28