続々: SQL使ってテーブルからランダムにN件引っ張りたい場合

前回のさらに続き・・・みたいなもの」

「SQLアンチパターン」に「15章ランダムセレクション」があってズバリこの話があるようです。が、MySQLだと「limit N offset n」はnが大きいときにパフォーマンス悪くなる話や、ランダム1件じゃなくてランダムN件引っ張ってきた場合の話がないので、たぶん私の書いた内容の方がよりつっこんでるとは思ってます。「SQLアンチパターン」は読み終わったらまたレビュー書く予定。

「1からcountまでの整数の中からランダムにN件重複なしに引っ張ってくる」やり方に少しツッコミができてたんでそこを補足。これを解く一般的なやり方は、前回書いた「1からcountまでの間の乱数を重複なしN個そろうまでひたすら振る」のは効率悪くて、実際はこんな手順になります。

1. 1からcountまでのcount個の数字を配列につっこむ
2. 1からcountの間の乱数を振る
3. ↑で出た値を配列から取り除き結果格納の配列に移す
4. N個そろうまでcount--しながら 2と3を繰り返す
5. 結果格納に目的のid(というかoffsetというかが入った状態になる

function make_random_list_string($maxnum, $count){
  $tmp_random_array = array();
  $result_array = array();
  for ($i=1; $i<=$maxnum; $i++){
    $tmp_random_array[] = $i;
  }
  for ($i=0; $i<$count; $i++){
    $maked_num = rand(0, $maxnum - $i);
    $result_array[] = $tmp_random_array[$maked_num];
    array_splice($tmp_random_array, $maked_num, 1);
  }
  return  implode(',', $result_array);
}

$countが大きいと$tmp_random_arrayや$result_arrayをメンテするコストもバカにならなくなってくるので、そういう場合はシャッフルを使う方が早いんじゃないかと。

function make_random_list_string($maxnum, $count){
  $tmp_random_array = array();
  $result_array = array();
  for ($i=1; $i<=$maxnum; $i++){
    $tmp_random_array[] = $i;
  }
  shuffle($tmp_random_array);
  return implode(',', array_splice($tmp_random_array, 0, $count));
}

確かに、make_random_list_string(100*10000,1)だと先の例の方が早かったけど、make_random_list_string(100*10000,100)だとこっちの方が早かった。ちなみに、PHPで大きい配列作ったりすると「Allowed memory size of 16777216 bytes exhausted」と怒られるので、そのときは /etc/php.ini に「memory_limit = 128M」とか書いときましょう。

とはいえ、$maxnumがさらにばかでかい(かつ$countが小さい)と、$tmp_random_arrayを作ることすらメモリが足りなくて現実的でなくなってしまう。そのときは、前回書いた例「重複しないN個がそろうまでひたすら乱数を振る」やり方が、アルゴリズム的には抜けがある(確率的になかなかN個そろわないことがどうしても起こりうる)けど、現実的には全く問題ないです。