Rubyで1からnまでの整数をランダムに並び替える（処理速度の比較まで）

Posted at 02:48 on July 24, 2010

Last updated at 16:10 on July 24, 2010

Category: Non-News, Note

Tags: Ruby, ツール, パソコン, 仕事, 勉強

最近 Ruby の勉強を始めました。で、「Ruby を使って、１から n までの整数をランダム1な順番に並べ替える」ということを考える機会があったので備忘録代わりにポストしておきます。

やり方はとりあえず２つ思い付きました。単純に２つの方法でやってみて「できたー」じゃおもしろくないので、２つの方法それぞれで処理にかかる時間を比較してみました。

基本的なやり方は、n 個の整数をランダムにかつ重複しないように生成していくという感じです。

方法1. すでに出た数か判断して重複ならやり直す

１つ目のやり方は、n 以下の整数をランダムに生成してみて、もしそれがすでに出た数であればもう１度やり直すというものです。

@n = ARGV[0].to_i   #要素数を取得

def sort1           #方法1. すでに出た数か判断して重複ならやり直す
  sorted1 = []
  @n.times do
    number1 = rand(@n) + 1
    if sorted1.include?(number1)
      redo
    end
    sorted1 << number1
  end
  #print "\n["
  #for i in 1..(@n - 1)
  #  print sorted1[i - 1], ", "
  #end
  #print sorted1[@n - 1], "]\n"
end

１行目 @n = ARGV[0].to_i はいくつの整数を並び替えるのか入力させるための記述です。本質の部分ではないので、３行目 def sort1 から見ていきます。

まず、空の配列 sorted1 を作ります。これは生成された乱数を格納するための配列です。

それから、処理を n 回（整数の数分）繰り返します。繰り返す処理は、まず乱数を発生させ、それがすでに配列 sorted1 に格納済みかどうか評価します。格納済みであればもう１度やり直し、まだ格納されていなければ新たに格納します。

12行目以降の print 関係は、並び替えられた整数を配列っぽく（[1, 2, 3, 4] のように）表示する記述です。# を外してコメントじゃなくすれば表示されます。

▲上に戻る▲

方法2. 出た数を除外していく

２つ目のやり方は、出た数を乱数候補から除外していくというものです。

@n = ARGV[0].to_i   #要素数を取得

def sort2           #方法2. 出た数を除外していく
  nums = []
  1.upto(@n) do |j|
    nums << j
  end
  sorted2 = []
  @n.times do
    number2 = rand(nums.size)
    sorted2 << nums[number2]
    nums.delete_at(number2)
  end
  #print "["
  #for k in 1..(@n - 1)
  #  print sorted2[k - 1], ", "
  #end
  #print sorted2[@n - 1], "]\n"
end

１行目は方法１とまったく同じです。

方法２では、まず１から n までを要素とする配列 nums を作ります。この配列に格納されている数＝まだ出ていない乱数候補となります。

それから空の配列 sorted2 を作り、n 回処理を繰り返します。繰り返す処理は、乱数候補の数（nums の要素数）より小さい乱数を発生させ、発生した乱数番目にあたる数を乱数候補 nums から sorted2 に格納し、乱数候補 nums からその数を除外します。

▲上に戻る▲

２つの方法の処理にかかる時間を比較

以上、２つの方法を見てきました。どちらも一応ランダムな並び替えができます。で、処理速度に違いはあるのかな？　ということで比較してみました。

結果から言うと、方法２の圧勝でした。以下で結果を見てみましょう。

まず、要素数が100個程度の場合です。これくらいならどちらの方法でもほとんど差がなく、ほぼ０秒で処理が終わりました。

要素数を500個に増やしてみます。方法１が0.02～0.03秒くらいかかるのに対し、方法２はまだほぼ０秒でした。

要素数を1,000個にしてみます。このへんになると体感できるくらいの差が出てきました。方法１だと0.3～0.4秒くらいですが、方法２はまだほぼ０秒でした。

では要素数3,000個ではどうでしょうか。方法１では３秒ほど、方法２では0.005秒ほどでした。

無駄に表にまとめると以下のような結果になりました。

要素数	方法１	方法２
100個	約0.002秒	約0.000秒
500個	約0.025秒	約0.001秒
1,000個	約0.350秒	約0.001秒
3,000個	約3.000秒	約0.005秒

よく言われることですが、今回方法１で使っている include? や if などの条件判断系は処理が遅いようです。しかも include? の場合は要素数に比例して処理時間がどんどん増えてしまいますね。ということで、今回の場合は乱数候補を減らしていくという方法２がいいようです。

あぁ、ちなみにこれ、「１から n までの整数」じゃなくて「m から n までの整数」みたいに簡単にできますね。そうすればよかったかな……orz

▲上に戻る▲

※ 追記（July 24, 2010）

すばらしいコメントをいただきました（下のコメント欄参照）。

実は、Ruby には配列の要素をシャッフルする Array#shuffle メソッドが用意されていました！　実際にランダムな並び替えをしたいときはこのメソッドを使うほうがよさそうです。

Array#shuffle メソッドがあるということがわかったので今回考えたことが無駄になったように思えますが、「Ruby に親しむ」とか「自分の頭で考えてみる」という意味では無駄ではありませんでした。今回の経験は自分でメソッドを作らないといけなくなったときにきっと役に立つはず！ｗ

今回考えたコード、それにコメントを反映させたのが以下のものです。

############################################################
#　　　1からnまでの数をランダムな順番に並び替える
############################################################

require "benchmark"

Benchmark.bm do |x|

  n = ARGV[0].to_i
  sorted1, sorted2, sorted3 = [], [], []

  x.report() do       # 方法1. すでに出た数か判断して重複ならやり直す
    n.times do
      number1 = rand(n) + 1
      if sorted1.include?(number1)
        redo
      end
      sorted1 << number1
    end
  end

  x.report() do       # 方法2. 出た数を除外していく
    nums = (1..n).to_a
    n.times do
      number2 = rand(nums.size)
      sorted2 << nums[number2]
      nums.delete_at(number2)
    end
  end

  x.report() do       # 方法3. shuffleメソッドを使う
    nums = (1..n).to_a
    sorted3 = nums.shuffle
  end

  #puts ""
  #p sorted1
  #p sorted2
  #p sorted3

end

1 この記事では「ランダム」＝「人の恣意性を含まない」程度に考えてください。

▲上に戻る▲

よろしければ以下の関連（してそうな）記事もどうぞ！

« 前の記事：JavaScript のお勉強でストップウォッチを作ってみた
» 次の記事：RailsのWEBrickサーバを強制的に停止する方法

5 Responses to “Rubyで1からnまでの整数をランダムに並び替える（処理速度の比較まで）”

takutakku より:

July 24, 2010 02:49

書いた：: Rubyで1からnまでの整数をランダムに並び替える（処理速度の比較まで） http://j.mp/9DMQUK takutakku
» このコメントを引用してコメントする
rubyist_bot より:

July 24, 2010 02:49

RT $Takutakku: 書いた：: Ｒｕｂｙで1からnまでの整数をランダムに並び替える（処理速度の比較まで） http://j.mp/9DMQUK rubyist_bot
» このコメントを引用してコメントする
Ruby好きより:

July 24, 2010 07:44
Ruby1.8.7以降ならArray#shuffleを使うのが無難ではないでしょうか？
```
#!ruby -Ks
# -*- coding: Windows-31J -*-
require 'benchmark'

Benchmark.bm do |x|

  m, n = ARGV
  array = (m..n).to_a
  sh, sa = [], []

  # 1.8.7 or later
  x.report(":shuffle --> ") {sh = array.shuffle}
#  p sh
#  puts "[#{sh*', '}]"

  # 1.8.8 or later
#  x.report(":sample  --> ") {sa = array.sample(array.size)}
#  p sa
#  puts "[#{sa*', '}]"

end
```
Ruby好き
» このコメントを引用してコメントする
返信
- Takku @きにきじ管理人より:
  
  July 24, 2010 12:23
  
  Ruby好きさん
  
  コメントありがとうございます。
  
  shuffle なんてメソッドがあったとは……。「こんな処理してくれる機能ありそうだよな～」とは思っていましたが、ずばりあったのですね。
  
  それと、コードの書き方という点でRuby好きさんのコメントは非常に参考になります。m, n = ARGV のように書けること、to_a メソッドで簡単に配列を作れること、print や puts メソッドではなく p メソッドを使えば配列を普通に [1, 2, 3, 4] のように表示できることなどを知りませんでした。puts "[#{sh*', '}]" という書き方は（今回は実は使う必要がありませんが）目から鱗でした。
  
  自分が書いたコードよりもスマートなコードを見たとき、僕は美しい芸術作品に出会ったような感動を覚えます。Ruby好きさんのコメントでこの感動を味わうことができました。ありがとうございます！ Takku @きにきじ管理人
  » このコメントを引用してコメントする
  
  返信
odamasaki より:

July 24, 2010 10:04

素晴らしい‼ 学んだことをスグにアウトプットする姿勢、処理速度まで考える深い思考、さすがです‼ RT @Takutakku: 書いた：: Rubyで1からnまでの整数をランダムに並び替える（処理速度の比較まで） http://j.mp/9DMQUK odamasaki
» このコメントを引用してコメントする

「きにきじ」：今日の気になる記事をきまぐれにご紹介