BASEプロダクトチームブログ

ネットショップ作成サービス「BASE ( https://thebase.in )」、ショッピングアプリ「BASE ( https://thebase.in/sp )」のプロダクトチームによるブログです。

そのシャッフル、本当にシャッフルですか?何気ない落とし穴にハマった話

こんにちは、BASEのフロントエンドチームでエンジニアリングマネージャーをやっている松原(@simezi9)です。 私は最近ではマネージャーとしてコードを書くことよりもチームの編成や採用などをメインに業務を行っているのですが、 そんな中でチラっと書いたコードで見事に落とし穴にハマって失敗をしたのでその共有記事です

まえがき

BASEのフロントエンドチームは現在15名ほど(うち業務委託5名)で運営されています。 この人数は今後もどんどん増えていく予定なのですが、目下全社的にリモートワークになっている事情も手伝ってメンバー同士の関係性が希薄になってしまう懸念を持っていました。 BASEの中では常に複数のプロジェクトが走っているのですが、それぞれのプロジェクトにフロントエンドエンジニアは2〜3名ずつ配置されています。 そんななかでアサインされた人同士がフロントエンドエンジニア同士であるにも関わらず、お互いのことをよくわからないという状態が今後おきうるというのは組織として問題があると考えpeer 1on1という制度を開始しました。

peer 1on1

peer 1on1は組織によってはシャッフルランチなどの名前で開催されてもいるようですが、要は「ランダムに選出されたメンバー二人で1on1をする」という時間です。1on1とかっこよく言っていますが、つまるところお互いを知る雑談の場を作るというものです。 現在は週1回30分の時間を取って行っています。BASEでは最近全社的な雑談の場所としてDiscordが用意されましたが、 Discordの気軽なボイスチャット機能との親和性も高く、それなりに盛り上がって運用されています。 (1対1で話すのは少し疲れるという話もあり、3人単位に変えたりといろいろと運用は試行錯誤しています)

そしてこのpeer 1on1を始めるにあたって、メンバーをランダムに組み合わせるためのツールをGoogle Apps Scriptでパパっと書きました。

f:id:simezi9:20210309135453p:plain

こんな感じでA列に今いるメンバーを入力しておき、メンバー生成ボタンを押すと毎回の二人組が作られていきます

発生する問題

このシートを作った当初は、「(見た目はさておき)またいっちょツールを作ってしまったぜ・・・実コード10行程度)」などと悦に入っていたのですが、いざ運用を始めてみてしばらく回数を重ねるこんな苦情が寄せられるようになります

f:id:simezi9:20210309135804p:plain

f:id:simezi9:20210309135540p:plain

最初はまあ、ランダムだしこんなこともあるでしょ!ぐらいに考えていたのですが、

f:id:simezi9:20210309135557p:plain

対象メンバーが10名を超えるような状況でこの偏りは流石におかしいということで調査を始めるとすぐに原因を突き止められました。

バグを抱えたシャッフルの実装と修正

このシートの実装は

  1. メンバーの一覧をシートから取得
  2. その配列をシャッフル
  3. 結果列にそのまま出力

というシンプルなフローになっていました その核となるシャッフルのロジックは以下のようなコードになっていました。

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
arr.sort(() => Math.random() - 0.5);

この実装自体は素朴なもので、ほとんどの人に直感的に理解できるものです。 Math.randomの動作は

0 以上 1 未満 (0 は含むが、 1 は含まない) の範囲で浮動小数点の擬似乱数を返します

というものなので、そこで得られた結果から 0.5を引けば、正の数、負の数が擬似乱数から均等に生成されることを期待できます。 あとはこれをArray.sortに渡すことで無秩序なソート操作が行えるので、配列がシャッフルされるというものです。 実際に、このコードは数回試してみると見た目上は正しく動作します 試しに検証コードをchromeのコンソールで実行してみたら以下のようになります。

const arr = [1, 2, 3, 4, 5, 6, 7, 8, 9];
let tmpArr;

tmpArr = [...arr];
tmpArr.sort(() => Math.random() - 0.5);
console.log(tmpArr); //  [1, 6, 4, 7, 5, 9, 2, 8, 3]

tmpArr = [...arr];
tmpArr.sort(() => Math.random() - 0.5);
console.log(tmpArr); // [8, 5, 1, 6, 9, 7, 2, 4, 3]

tmpArr = [...arr];
tmpArr.sort(() => Math.random() - 0.5);
console.log(tmpArr); //[8, 3, 1, 6, 4, 9, 2, 5, 7]

それっぽく動いているような気がします。 ただこのコードは組み込みのsort関数の比較関数の結果をランダムにすればシャッフルされるという前提に立って実装されていますが、考えてみると、この想定自体が随分といい加減です。 大体のソート処理は、一定のルールに基づいて2つの要素を取り出し、その要素同士を比較関数で比較し、結果に応じて並べ替えるという操作を繰り返し行います。 そのソート処理の内部実装は処理系に依存していますが、例えばChromeのJSエンジンであるV8の実装ではTimsortを利用しています。Timsortはざっくりいうと、マージソートをベースにして、いくつかのソートアルゴリズムのアイデアを取り入れて性能を改善したアルゴリズムです。 ここで問題になるのが、先程の比較関数に乱数を利用する考え方では、ソートアルゴリズムの詳細を無視して比較関数さえランダムにすればすべての要素が乱雑に配置されるという想定をしていることです。実際にはその想定は間違っていて、操作後の配列の分布は大きく偏ります。

Will it shuffle?というサイトではその偏りを視覚化して見ることができます 以下の画像はそのスクリーンショットですが、比較関数をRandomにした場合の結果の偏りが大きいことがわかります 特に先頭部分、末尾部分があまりシャッフルされていない結果になっています (なぜそうなるのかという原理的な部分はwikipediaなどでも解説があります)

f:id:simezi9:20210309135619p:plain

ではどうすればいいのかというと、こうしたシンプルなアルゴリズムの研究はしっかり行われているのでちゃんとその知識を拝借しましょうということで、今回のツールではフィッシャーイェーツのアルゴリズムを利用したものに変更しました。 このアルゴリズムは、とても素朴なものでランダムな順番の数列を生成してそのとおりに要素を並べるだけのものではありますが、 ソートするなどの余計な処理を挟まない分、計算量的にもとてもスマートで正しく動きます

こちらのアルゴリズムでの結果も先程のWill it shuffle?のサイトに用意されており、配置の偏りが少ないことが視覚的にわかります。 他にもこのフィッシャーイェーツの改良アルゴリズムなどいくつか手法は開発されているようでしたが、今回のようなちょっとしたツールにはこれで十分そうでした。

f:id:simezi9:20210309135655p:plain

結果

圧倒的改善をうみました 😭

f:id:simezi9:20210309135714p:plain

コードの見た目がシンプルだからといって、正しく動いてる保証は無く、 特にアルゴリズムを適応するような操作についてはきちんと動作を考える必要があると改めて反省をする機会になりました。 このシャッフルの操作については、最初のバギーな実装を紹介しているサイトが検索結果にも多数出てくるため結構ハマってしまいそうなケースが多そうだなと思います。 私自身もシャッフルの偏りというような内容の記事を以前に見た記憶はあったのですが、自分で実装して罠にハマっていることに気づいたのは指摘された後でした。

あまりフロントエンドとは関係のない内容ですが、これでメンバー同士の交流も円滑に行っていくことができそうです。

採用情報 | BASE, Inc.

採用情報-フロントエンドエンジニア 採用情報-Webアプリケーションエンジニア