Go to Qiita Advent Calendar 2024 Top
LoginSignup
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?

More than 5 years have passed since last update.

@sugunisu(スグニス)

RubyでHeapArrayを作って性能評価をやってみた

Last updated at Posted at 2016-12-13

#はじめに
rubyの配列は汎用的な作りをしているので,
あえてそれを専門的なものすれば動作が早くなるのではないかと思い調査した次第です

#比較するアルゴリズムについて
今回比較するプログラムは「priority queue」です
比較対象は以下のものを使用します

  1. 配列から最小値を探して取ってていくプログラム(あまりいい方法が思いつきませんでした)
  2. 配列を一度ソートして頭からデータを取っていく
  3. HeapArrayを使ったアルゴリズム(後述)

#HeapArrayアルゴリズムについて
配列を頭から1,2,4,8,...と取っていき二分木の木構造とみなします
するとiに対する子は(2i+1)と(2i+2)になります
この木構造で最小の値が常に根になるような配列のアルゴリズムです
##値の挿入
値を最下部に入れ込み親より小さければどんどん上に上げて,
親より大きくなる地点でストップします
##値の抜き出し
値を最上部を取り出し子の小さいほうを上にずらします

##プログラム

heap.rb
class HeapArray
  def initialize
    @heapArr = []
  end

  def push(n)
    i = @heapArr.size

    while i>0
      p = (i-1)/2
      break if @heapArr[p] <= n
      @heapArr[i] = @heapArr[p]
      i=p
    end

    @heapArr[i] = n
  end

  def pop
    min = @heapArr[0]
    n   = @heapArr.pop
    unless @heapArr.empty?
      i   = 0
      while (i*2+1) < @heapArr.size
        if @heapArr[i*2+2].nil?
          buf=i*2+1
        else
          buf=(@heapArr[i*2+1]<@heapArr[i*2+2])?i*2+1:i*2+2
        end
        break if @heapArr[buf] >= n
        @heapArr[i] = @heapArr[buf]
        i=buf
      end
      @heapArr[i]=n
    end
    return min
  end

  def show
    level=0
    p=0
    while p<@heapArr.size
      (2**level).times do
        if @heapArr[p].nil?
          print "x "
        else
          print "#{@heapArr[p]} "
        end
        p+=1
      end
      puts ""
      level+=1
    end
    puts ""
  end
end


=begin
ha = HeapArray.new

ha.push 19
ha.push 15
ha.push 13
ha.push 12
ha.push 17
ha.push 14
ha.push 20
ha.push 8
ha.show
8.times do
  puts "pop:#{ha.pop}"
  ha.show
end
=end

#検証方法について
以下のサイトを参考にして,benchmark-ipsのgemを使い検証しました
Rubyでベンチマークを取る

-10000から10000の乱整数を10000個配列に用意して
それを1つずつ読み込んで最小の値から1つずつ吐かせていきます
次の2つのケースについて考えます

  1. 全てのデータを与えた後に全て出す
  2. ランダムに入れるかデータを取り出すかが与えられる

検証用のプログラムは以下の通りです

  1. 全てのデータを与えた後に全て出す
heaptest.rb
require 'benchmark/ips'
require './heap.rb'

Benchmark.ips do |x|
  testData = 10000.times.map{rand(-10000..10000)}
  x.report("Array with Min Loop") {
    data = []
    testData.size.times do |i|
      data << testData[i]
    end
    data.size.times do
      min=data.min
      data.delete_at(data.index(min))
    end
  }
  x.report("Array with Sort Loop") {
    data = []
    testData.size.times do |i|
      data << testData[i]
    end

    data.sort!

    data.size.times do
      data.shift
    end
  }
  x.report("Heap Array"){
    ha=HeapArray.new
    testData.size.times do |i|
      ha.push testData[i]
    end
    testData.size.times do
      ha.pop 
    end
  }

  x.compare!
end
  1. ランダムに入れるかデータを取り出すかが与えられる
heaptest.rb
require 'benchmark/ips'
require './heap.rb'

Testtime = 10000

Benchmark.ips do |x|
  testData = Testtime.times.map{rand(-10000..10000)}
  store=0
  pushcnt=0
  pushflg = (Testtime*2).times.map{
    flg=rand(0..1)
    if (store==0||flg==1)&&pushcnt<Testtime
      store+=1
      pushcnt+=1
      1
    else
      store-=1
      0
    end
    
  }

  x.report("Array with Min Loop") {
    data = []
    p=0
    pushflg.each do |flg|
      if flg==1
        data << testData[p]
        p+=1
      else
        min=data.min
        data.delete_at(data.index(min))
      end
    end
  }
  x.report("Array with Sort Loop") {
    data = []
    p=0
    pushflg.each do |flg|
      if flg==1
        data << testData[p]
        p+=1
      else
        data.sort!
        data.shift
      end
    end

  }
  x.report("Heap Array"){
    ha=HeapArray.new
    p=0
    pushflg.each do |flg|
      if flg==1
        ha.push testData[p]
        p+=1
      else
        ha.pop
      end 
    end
  }

  x.compare!
end

#検証結果

result.txt
Warming up --------------------------------------
 Array with Min Loop     1.000  i/100ms
Array with Sort Loop     6.000  i/100ms
          Heap Array     1.000  i/100ms
Calculating -------------------------------------
 Array with Min Loop      0.045  (± 0.0%) i/s -      1.000  in  21.990645s
Array with Sort Loop     67.698  (± 5.9%) i/s -    342.000  in   5.077838s
          Heap Array      4.412  (±22.7%) i/s -     22.000  in   5.116938s

Comparison:
Array with Sort Loop:       67.7 i/s
          Heap Array:        4.4 i/s - 15.34x  slower
 Array with Min Loop:        0.0 i/s - 1488.73x  slower

最終的な総合結果はComparisonに出るそうです
最小値を抜き出す方法は論外(最小値を検索用と削除用で2回も探しているので)として
Heap方式に比べSort方式は圧倒的な計算スピードです(約15倍も早い)
Sort方式はSort1回だけなので当たり前っちゃ当たり前ですがなかなかの速さです

result2.txt
Warming up --------------------------------------
 Array with Min Loop     1.000  i/100ms
Array with Sort Loop     1.000  i/100ms
          Heap Array     1.000  i/100ms
Calculating -------------------------------------
 Array with Min Loop      0.573  (± 0.0%) i/s -      3.000  in   5.520816s
Array with Sort Loop      0.943  (± 0.0%) i/s -      5.000  in   5.444410s
          Heap Array      3.248  (±30.8%) i/s -     15.000  in   5.084138s

Comparison:
          Heap Array:        3.2 i/s
Array with Sort Loop:        0.9 i/s - 3.44x  slower
 Array with Min Loop:        0.6 i/s - 5.67x  slower

ランダムな入出力になったとたんにSort方式は一気に遅くなりました
一方でHeap方式は常にソートがかかっているので速さはあまり変わりません
普通の配列より約3.4倍早くなりました

以上よりデータが全て既知な場合であればsortして,未知の場合はHeapArrayを使った方がいいみたいです

速さを求める場合何かしらの制約がある場合はちゃんとアルゴリズムを使って書き換えた方がいいみたいです
特にC++のSTLのような構造をとるものは書き換えるといいかもしれません

1
0
0

Register as a new user and use Qiita more conveniently

  1. You get articles that match your needs
  2. You can efficiently read back useful information
  3. You can use dark theme
What you can do with signing up
Sign upLogin
1
0

Delete article

Deleted articles cannot be recovered.

Draft of this article would be also deleted.

Are you sure you want to delete this article?