naiの日記

ソフトウェアエンジニアから放射線科診断医にジョブチェンジしました。趣味のことを書きます。

Sharkovskii order (C) 解説 その1 ～真面目な解法編～

anarchy golf code golf

問題URL：anarchy golf - Sharkovskii order

8年前の問題ですが，qsortの比較関数にmainを渡したり，機械語を渡したりとやりたい放題やったので，個人的に印象に残っている問題です．

開催当時はC言語で1位をとったものの，自分のコードがなぜ動いているかわからなかったのですが，最近ようやく自分のコードを解読し，なぜ動いているか理解できたので，以下に解説を残しておきます．

 

（続き：その2～x86機械語編～）

問題概要

正の整数がいくつか与えられます．これらを以下の順番 (Sharkovskii order) でソートしてください．

  • 3, 5, 7, ...
  • 6, 10, 14, ...
  • 12, 20, 28, ...
  • ...
  • ..., 8, 4, 2, 1

General Approach

ビット演算

まず最初に，2で何回割れるかで比較を行う必要があります．整数 X の立っている最下位ビットは X & -X で取得できるので，これの大小を比較すれば良いです．

ただし，2のべき乗の整数だけは，他の2べきでない整数よりも後ろに置かなければいけません．整数 X が2のべき乗かどうか判定するには，以下のような方法があります．

  1. X & X - 1 が0かどうかで判定
  2. X & -X が Xと一致するかで判定

他の言語では2の方法をとっている解法が多いですが，C言語では微妙に書きづらいので1の方法を使いました．

qsort

具体的にソートを書く方法ですが，幸い，C言語にはソートを行う qsort 関数があるので，これを使ってやります．

qsortの第4引数には比較関数を渡します．比較関数は，2つのポインタ*a, *bを引数に取り，

  • *a < *b なら負の数
  • *a == *b なら0
  • *a > *b なら正の数

を返すような関数である必要があります．例えば，単純に整数を昇順にソートする場合は，*a - *bを返すようにしてあげれば良いです*1．

しかし，Sharkovskii orderの比較関数を素直に実装しようとすると，1つ困った点が生じます．前述の通り，*aや*bが2べきの場合は例外処理をしなければならないため，場合分けが多くなりすぎるのです．試しに，Sharkovskii orderの逆順でソートするための比較関数を書いてみると，以下のような実装になります（逆順の理由は後述）．

c;
f(int*a,int*b){
  c=*b&*b-1;
  return*a&*a-1?c?(*b&-*b)-(*a&-*a)?:*b-*a:1:c?-1:*a-*b;
}

それぞれの場合分けに対応して三項演算子が4つも登場し，一時変数まで必要になっています．さすがにこれは長すぎるのでどうにかしないといけません．

第一引数が2べきの場合，第二引数との比較をスキップできる

先に結論を書いてしまうと，入力をSharkovskii orderの逆順にソートすることにすれば，第一引数*aが2のべき乗なら，直ちに0以下の整数を返して，*bとの比較をスキップできます．

 

まず事前知識として，（少なくともglibcの）qsortの実装は，クイックソートではありません．簡潔なQ様の記事にも記述がありますが，データがよほど大きくなければマージソートが行われるようです．そしてマージソートには（クイックソートとは違い），以下のような嬉しい特徴があります．

  • a < b，つまりインデックスの小さい方が必ず第一引数として呼ばれる．*2
  • ソートが安定．

 

さて，Sharkovskii orderの逆順に並べるということは，まず最初に2のべき乗の整数を昇順に（1, 2, 4, 8, ...）並べ，その後それ以外の整数を並べるということになります．ということは，第一引数*aが2べき，第二引数*bが2べき以外の場合，これら2つの整数は望ましい順序で並んでいるので，swapする必要がありません（必ずaのインデックスのほうが小さいので）．

問題は*a，*bともに2のべき乗で，かつ*a > *bの場合です．この場合はswapしないとまずいですが，実は，このような引数が渡されて比較関数が呼ばれることはありません．

問題の入力をもう一度よく見てみましょう．なんと，偶然にも，2べきの整数は全て最初から昇順にソートされています．いやあ，凄い偶然だなぁ～（棒）．マージソートは安定ソートなので，2のべき乗の整数のみに注目すると，ソート中やソート後も常に大きさの昇順に並んでいることがわかります．ですので，先述のような引数の組み合わせは考慮しなくてもよいのです．

よって先程の比較関数fは次のように書けます．だいぶ短くなりました．

f(int*a,int*b){
  return*a&*a-1?*b&*b-1?(*b&-*b)-(*a&-*a)?:*b-*a:1:0;
}

第二引数が2べきかどうかの判定を省略

ここまでで随分短くなりましたが，まだ2べきかどうか判定するコードを，*aと*bでそれぞれ書いています．*b&*b-1の部分をどうにかして削れないでしょうか？

実は，できます．

入力に現れる2べきの整数は1, 2, 4, 8, 32の5種類ですが，例えば32なんかは立っている最下位ビットが32なので，2べきの条件を無視して普通にソートしてもほとんどの整数より前に（i.e. 望ましい順序で）ソートされます．実際，入力に現れる整数で32の倍数なのは，32の他には46368だけです．

問題は1や2など，最下位ビットが小さい2べきの整数たちです．これらは2べきの条件を無視して普通にソートしてしまうと後ろの方に行ってしまいます．ですが，偶然にも，入力内で1や2は最初の方に現れるため，比較関数の第二引数として渡されることがほとんどありません（！）．よって，偶然にも，*bが2べきかどうかの判定を省略しても，プログラムは正しく動きます．入力1と入力3において，入力が昇順ソートされていたのが決め手でしたね．

これにより，比較関数はさらに短くなりました．

f(int*a,int*b){
  return*a&*a-1?(*b&-*b)-(*a&-*a)?:*b-*a:0;
}

最短コードへ

あとは上記のfをqsortの比較関数として渡せば動くのですが，8年前の自分は何を考えたのか，main関数自身をqsortの比較関数にしてしまうという曲芸を披露しました．関数の数が1つ減るのと，第二引数のint*が共通化されるので，短くなるようです．（136バイト）

main(a,b)int*b;{
  return a<0&&(a=**(&b-1))&a-1?(*b&-*b)-(a&-a)?:*b-a:
    ~scanf("%d",++b)&&main(a+1)^qsort(b-a+1,a,4,main)^printf("%d\n",*b);
}

ショートコーディングなのにmainが3箇所も登場しており，これはこれで面白いのですが，残念ながら後述するvprintf()による短縮が使えず，最短コードには至りませんでした．

現在（2018/08/13）の最短コード（117バイト）はこちらです（解説のため変数名を変えています）．

v,n;
f(int*a,int*b){return(*b&-*b)%*a-(*a&-*a)?:*b-*a;}
main(){
  ~scanf("%d\n",&v+n++)?main()^vprintf():qsort(&v,n,4,f);
}

main再帰によりスタックをどんどん積んでいき，入力が最後に到達したらqsortでソートしてから，スタックをポップしながらvprintfで出力するというコードになっています．もはやおなじみになったテクニックですが，vprintfの引数を省略することで直前にscanfに渡したものが使われ，文字数を削減できています．

特筆すべきは(*b&-*b)%*a-(*a&-*a)の部分でしょう．*aが2のべき乗の場合，(*a&-*a)は*aと同じなので，上記の部分は

(*b&-*b)%*a-*a

となり，これは*bの値によらず0未満です．要はswapされずにスキップされることになります．

*aが2のべき乗でない場合ですが，(*b&-*b)は上述の通り，大抵は1とか2なので，(*b&-*b)%*aは大抵の場合(*b&-*b)と同じになり，この場合は普通に比較することになります．もちろん反例を考えることはできますが，実際に動かしてみると，偶然にもこれで正しく動作します．これにより，*aが2べきの場合の例外処理を5バイトも削減することができました．

 

その2～x86機械語編～ に続く．

 

*1:厳密にはオーバーフローの可能性があるので，ちゃんと場合分けをして-1や1等を返すほうが望ましい．

*2:厳密にはこれも実装依存ですが……．