Fisher-yatesアルゴリズムでコードゴルフ

コードゴルフしてたらたのしくなったので、コードゴルフテクの紹介記事を書こうと思います。

コードゴルフするコード

今回使用するコードはこちら

const shuffle = arr => {
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
};

これを変形させていきます。

とりあえず完成形をば

こうなりました。

const shuffle=(a,i=a.length,j)=>{for(;i;)[a[i],a[j]]=[a[j=0|Math.random()*i],a[--i]]};

不要なスペースを削除

初手はこれが安定ですよね。

const shuffle=arr=>{
    for(let i=arr.length-1;i>0;i--){
        const j=Math.floor(Math.random()*(i+1));
        [arr[i],arr[j]]=[arr[j],arr[i]];
    }
};

変数宣言を引数部分で行う

関数ならではの方法です。ここで6文字減らせました。

const shuffle=(arr,i=arr.length-1,j)=>{
    for(;i>0;i--){
        j=Math.floor(Math.random()*(i+1));
        [arr[i],arr[j]]=[arr[j],arr[i]];
    }
};

Math.floorをビット演算にすり替える

有名な手法ですね。

const shuffle=(arr,i=arr.length-1,j)=>{
    for(;i>0;i--){
        j=0|Math.random()*(i+1);
        [arr[i],arr[j]]=[arr[j],arr[i]];
    }
};

代入演算子が返す値を利用する

代入演算子は右辺の値を返します。

(a = 3) === 3 // true

これを利用して j=0|Math.random()*(i+1) を埋め込んでしまいます。

const shuffle=(arr,i=arr.length-1,j)=>{
    for(;i>0;i--){
        [arr[i],arr[j]]=[arr[j=0|Math.random()*(i+1)],arr[i]];
    }
};

だんだん変態チックになってきましたねえ。forの中身が1行になったのでカッコも外してしまいましょう。

const shuffle=(arr,i=arr.length-1,j)=>{
    for(;i>0;i--)
        [arr[i],arr[j]]=[arr[j=0|Math.random()*(i+1)],arr[i]];
};

i>0をiで置き換え

i は i!=0 と等価であって、 i>0 とは等価ではないのですが、今回iが負になることはないのでこれで大丈夫です。

const shuffle=(arr,i=arr.length-1,j)=>{
    for(;i;i--)
        [arr[i],arr[j]]=[arr[j=0|Math.random()*(i+1)],arr[i]];
};

i--を埋め込む

i-- をうまく分割代入の中に組み込みたいです。ここで先日書いた記事をもとに考えてみます。

www.pandanoir.info

分割代入では「右辺の要素を先頭から順に評価し、右辺が終わったら左辺の要素を先頭から順に評価する」ということをしていました。これをもとに考えると次のように変形が可能です。

const shuffle=(arr,i=arr.length,j)=>{
    for(;i;)
        [arr[i],arr[j]]=[arr[j=0|Math.random()*i],arr[--i]];
};

i--の実行を右辺の2番目で行うようにすれば Math.random()*(i+1) が Math.random()*i に、 i=arr.length-1 が i=arr.length になるという嬉しい特典もあります。

仕上げ

仕上げにインデントと改行、不要なセミコロンを消して、引数を1文字にして完成です。

const shuffle=(a,i=a.length,j)=>{for(;i;)[a[i],a[j]]=[a[j=0|Math.random()*i],a[--i]]};

アロー関数のカッコは、中身がfor文のため消すことができません。そのため、これで完成です。

はじめのコードと見比べると、かなり小さくなりました。

const shuffle = arr => {
    for (let i = arr.length - 1; i > 0; i--) {
        const j = Math.floor(Math.random() * (i + 1));
        [arr[i], arr[j]] = [arr[j], arr[i]];
    }
};

これの余計な空白と改行を削除したものと比べてみても、127バイトから86バイトと約30%削減できました。

終わりに

これ以上は短くならないんじゃないか、というくらい最適化できたと思います。もっと短くできる、という方はコメントで教えてください。

ちなみに、 for(;i;) と while(i) は等価です。お好きなほうでいいとおもいます。これ単体でgzipすると、むしろサイズが増大するのでgzip効率とか考えなくていいです。

2017-9-10 追記:

これ以上短くならないだろうと思っていたら、2バイトも小さく、しかもよりよく動作するコードを発見してしまったので記事を書き直しました。

おまけ: ES2015不使用版

function shuffle(a,i,j){for(i=a.length;i;)a[j=0|Math.random()*i]=[a[--i],a[i]=a[j]][0]}

ちなみにこれとES2015を組み合わせると先ほどのコードより1バイト小さくなります。

function shuffle(a,i=a.length,j){for(;i;)[a[i],a[j]]=[a[j=0|Math.random()*i],a[--i]]}

まあ、コードが完全には等価でないのでノーカンでお願いします。ES2015使うのにconstが使えないfunctionで関数宣言すんな