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

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

Posted at 02:48 on July 24, 2010

Last updated at 05:09 on February 21, 2011

Category: Non-News, Note

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

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

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17

@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. 出た数を除外していく

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19

@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秒ほどでした。

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

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

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

▲上に戻る▲

※ 追記（July 24, 2010）

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

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

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

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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

############################################################
#　　　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

▲上に戻る▲

※ さらに追記（September 18, 2010）

もう１つ、１から n までの整数をランダムに並べ替える方法を思いつきました。１から n までの整数と乱数を組み合わせた二次元配列を作り、乱数で並べ替えるというものです。

これを方法４として追加したら以下のようなコードになります。相変わらず Array#shuffle メソッドが最速ですが、方法４は方法２よりも高速なようです。n を10,000にした場合、方法２は約2.3秒、方法４は約0.5秒でした。ちなみに方法３は0.02秒ほど。ケタが違いますｗ　また、これくらいの要素数で方法１を試すと時間がかかりすぎていつまで経っても処理が終わらないのでご注意を。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49

############################################################
#　　　1からnまでの数をランダムな順番に並び替える
############################################################
 
require "benchmark"
 
Benchmark.bm do |x|
 
  n = ARGV[0].to_i
  sorted1, sorted2, sorted3, sorted4 = [], [], [], []
 
  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
 
  x.report() do       # 方法4. 2次元配列で並び替える
    n.times do |num|
      sorted4 << [num + 1, rand()]
    end
    sorted4 = sorted4.sort_by{|key| key[1]}.collect{|key| key[0]}
  end
 
  #puts ""
  #p sorted1
  #p sorted2
  #p sorted3
  #p sorted4
 
end

ちょっと調べてみると、array.sort_by{rand} でランダムソートできるみたいですね。速度は Array#shuffle のほうが上ですが、Array#shuffle 以外の方法であれば array.sort_by{rand} がいいかもしれません。

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

▲上に戻る▲

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

• MySQLで3つのテーブルをOUTER JOINする3つの方法を比較してみた
• Office 2007 Wordで「標準の文字数を使う」が勝手に「行数だけを指定する」に変更される件
• Railsのfindで複数のテーブルから検索する：includeでeager loading
• Ruby1.8.7以降ではtruncateメソッドの仕様が変わったらしくエラーが起きる
• 大学・大学院の新入生、研究室に配属される学生へ向けた、発声練習さんの必読記事

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

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

1. takutakku より:

   July 24, 2010 02:49

   書いた：: Rubyで1からnまでの整数をランダムに並び替える（処理速度の比較まで） http://j.mp/9DMQUK

     takutakku

   » このコメントを引用してコメントする
2. rubyist_bot より:

   July 24, 2010 02:49

   RT $Takutakku: 書いた：: Ｒｕｂｙで1からnまでの整数をランダムに並び替える（処理速度の比較まで） http://j.mp/9DMQUK

     rubyist_bot

   » このコメントを引用してコメントする
3. Ruby好き より:

   July 24, 2010 07:44

   Ruby1.8.7以降ならArray#shuffleを使うのが無難ではないでしょうか？

   1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21

   #!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 @きにきじ管理人

     » このコメントを引用してコメントする

     返信
4. odamasaki より:

   July 24, 2010 10:04

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

     odamasaki

   » このコメントを引用してコメントする