高速なシャッフル処理

１．はじめに

　Ｘ（旧Twitter）でシャッフル処理の話題があり、高速にシャッフルする方法について考察した結果をメモしておきたいと思います。
　今回は（も）ネットでググったり、ＡＩに聞いたりせずに自力で検討を進めました。
　自力で検討した場合、「車輪の再発明」になってしまうかもしれませんが、思考過程を楽しみたいこと及び、ググった場合はその手法に捕らわれて思考の広がりが制限されてしまうことを避けたいためです。

２．物理的なシャッフル操作

　もともとのお題としてはトランプのシャッフル動作をプログラム化することが話の発端です。
　具体的には一山のトランプからランダムに一枚を選び、そのカードをトランプの山から取り除き、一列に並べていくという動作を繰り返すことでシャッフルされたカードの列を作り出すというものです。

３．トランプ操作とは異なるシャッフル方法

　前項で書いたトランプの操作は直感的にも偏りなくランダムに並べ替えられることが直ぐに判りますが、下記の「シャッフル処理１」でシャッフルしても、確率計算してみると均等にシャッフルできることに気が付きました。尚、下記の処理では0から9までの10個の配列要素をシャッフルしています（以降の処理も同様）。

シャッフル処理１（BASIC） 　 10 DEFINT A-Z 20 N=10 30 FOR I=0 TO N-1:A(I)=I:NEXT 40 FOR I=0 TO N-1:SWAP A(RND(1)*N),A(I):NEXT

※RND(1)*N は自動的に整数変換された結果 0..N-1 の範囲の整数になる、SWAPは変数の値を交換する処理

　更に下記の「シャッフル処理２」の結果も確率計算してみると偏りなくランダムに並べ替えられるので、配列要素に連番を設定するループとシャッフルするためのループを同一にできました。

シャッフル処理２（BASIC） 　 10 DEFINT A-Z 20 N=10 30 FOR I=0 TO N-1:A(I)=I:SWAP A(RND(1)*(I+1)),A(I):NEXT

４．シャフル処理の改善

　上記の「シャッフル処理２」ではループ処理の最初の I=0 の時に A(0) と A(0) を入れ替えているので無駄な乱数発生を行っていることになります。このことからＮ個の要素をシャッフルするには（Ｎ－１）回の乱数発生を行えばいいことが判ります（上記２項の「物理的なシャッフル操作」の場合も同数の乱数発生が必要ですね）。
　変数の初期値が零であることを利用して乱数発生回数を最小限になるように「シャッフル処理２」を改善した処理が下記になります（Iの初期値を1に変更）。

シャッフル処理３（BASIC） 　 10 DEFINT A-Z 20 N=10 30 FOR I=1 TO N-1:A(I)=I:SWAP A(RND(1)*(I+1)),A(I):NEXT

　しかし、上記の処理は A(0) が零であることを前提にしているので、そのままでは再度シャッフルできないという欠点があります。
　そこでシャッフル処理だけに特化した下図の処理を考えました。これならば何度でもシャッフルすることが可能で、当然ですがシャッフル対象も連番である必要がないので汎用的なシャッフル処理として利用できます。

汎用化したシャッフル処理［（A(0)からA(N-1)の要素を高速にシャッフル］ 　 FOR I=1 TO N-1:SWAP A(RND(1)*(I+1)),A(I):NEXT

※Ｎはシャッフル対象要素の個数

５．フィッシャー・イェーツのシャッフル

　Ｘのコメントで教えて頂いたのですが「フィッシャー・イェーツのシャッフル」というシャッフル処理があります。ネットで「高速なシャッフル処理」を検索すると最初に出てきました。
　処理内容は上記２項に書いた「物理的なシャッフル操作」を効率よく行う処理になっています。計算量は上記の「汎用化したシャッフル処理」と同等で O(N) オーダーであり、高速です。

フィッシャー・イェーツのシャッフル 　 要素数が n の配列 a をシャッフルする(添字は0からn-1): i を n - 1 から 1 まで減少させながら、以下を実行する j に 0 以上 i 以下のランダムな整数を代入する a[j] と a[i]を交換する

※ウィキペディアより引用

６．あとがき

　ひょんなことからシャッフル処理の検討が始まり、現在最速と思われるフィッシャー・イェーツのシャッフルと同程度の速度で処理内容の異なるシャッフル処理まで辿り着きました。
　今回のような検討のトリガが得られるのもＸの醍醐味ではないかと思います。また、安易にネット検索やＡＩに聞かないことで思考の過程を楽しむことができました。
　尚、今回辿り着いたシャッフル処理を skyriverのシャッフル と命名しますｗ

Comments

乱数を必要としないシャッフルはあるのでしょうか。
シャッフル対象の数に対し、疑似乱数の循環が十分に大きい値でない場合や、乱数の質が十分でない場合はどうすればいいんでしょうか。

Posted by enaka at 2026年05月13日 20:17

その場合は量子ビットの出番かも・・・ｗ
複数の疑似乱数を掛け合わせる等の操作をして周期を伸ばすことが有効かもしれませんね

Posted by skyriver at 2026年05月13日 20:25