Rubyによる多次元配列の実装方法について
[1] 多次元配列を実装する３つの方法
もともとコンピュータ――機械語レベル――には、メモリーという概念はあっても、配列という概念はありません。そのため、１次元配列は、メモリーある空間を割り当てることで実現できますが、２次元より高次の配列は、なんらかの工夫をしないと実現できません。
多次元配列を実装する方法は、アセンブラー時代から大きく分けると二つの方法がとられてきました。
ひとつは、下位の次元から順番に割り当てていく方法です。たとえば、３×４の２次元配列を実装するのに、連続した１２個の要素を割り当てて、２個の添え字i,jから、１個の添え字n(n = i * 4 + j)に変換する方法です。
もう一つの方法は、可変サイズの配列などを作成するときによく用いられる方法ですが、多段配列を用いて実装する方法です。Ruby的に書くと以下のようになります。
さて、RubyやPerlには、ハッシュという非常に強力な記憶クラスがあります。これを援用して多次元配列を作成することができます。
ary = [ [1,2,3,4 ], [ 5,6,7,8 ], [9,10,11,12 ] ]
ary[0][1] = 2
最もRuby的な方法は、Arrayオブジェクトをそのまま、キーに使用する方法です。また、添え字を文字列に変換してキーにすることもできます。
# Arrayをキーにした方法
ary = {}
ary[ [0,0] ] = 1
ary[ [0,1] ] = 2
..
ary[ [2,3] ] = 12
[2] 実装のテストとその結果
# Stringをキーにした方法
ary = {}
ary["#{i},#{j}"] = 1100
以下のようなテストプログラムを実行します。
30×30×30の三次元配列を作成し、各要素に値を代入。その配列の各要素を合計する処理を10回実行する
| DimByStd | 2.796 sec | # 標準的な実装法 |
| DimByAry | 1.641 sec | # 多段配列による実装 |
| DimByHashAry | 18.407 sec | # 配列を直接キーにしたHash |
| DimByHashPack | 2.500 sec | # 添字をpack('I*')でキーを作成し、ハッシュで管理 |
| DimByHashStr | 3.406 sec | # 添字をjoin(":")でキーを作成し、ハッシュで管理 |
意外だったのは、標準的な実装方法が、あまり早くなかったことです。掛け算命令が無かった8bit時代のＣＰＵならともかく、これは意外でした。
やはり重かったと思ったのが、Rubyで比較的よくつかわれる、Arrayをキーにする方法です。この方法は、Arrayという比較的重たい構造をキーにするため、メモリーの使用効率が悪く、しかも、遅いという二重苦になります。緊急避難的にしか使用できない方法です。
メモリー効率は、標準的な実装方法がもっともよく、次いで多段配列による実装になります。ハッシュによるアクセスは、キーが余分になりますので、無駄が多いことが予測されます。離散した集合を扱う場合を除いて、あまり意味がないと思われます。
[3] ソースコード
#!/usr/bin/rub
#=======================================================================#
# Ruby多次元配列の実装の実験
#
# DimByHashPack 2.500 sec
# DimByHashStr 3.406 sec
# DimByHashAry 18.407 sec
# DimByAry 1.641 sec
# DimByStd 2.796 sec
#=======================================================================#
XSIZE = 30
YSIZE = 30
ZSIZE = 30
COUNT = 10#=======================================================================#
# 引数をパック化して、ハッシュキーとする方法
#=======================================================================#
class DimByHashPack
def initialize(*arg)
@data = Hash.new
@dimension = *arg.size
end
def [](*arg)
raise IndexError unless arg.size == @dimension
return @data[arg.pack('I*')]
end
def []= (*arg)
val = arg.pop
raise IndexError unless arg.size == @dimension
@data[arg.pack('I*')] = val
return val
end
end#=======================================================================#
# 引数を文字列化して、ハッシュキーとする方法
#=======================================================================#
class DimByHashStr
def initialize(*arg)
@data = Hash.new
@dimension = *arg.size
end
def [](*arg)
raise IndexError unless arg.size == @dimension
return @data[arg.join(":")]
end
def []= (*arg)
val = arg.pop
raise IndexError unless arg.size == @dimension
@data[arg.join(":")] = val
return val
end
end#=======================================================================#
# 引数をArrayオブジェクトとしてそのままキーに使う
#=======================================================================#
class DimByHashAry
def initialize(*arg)
@data = Hash.new
@dimension = *arg.size
end
def [](*arg)
raise IndexError unless arg.size == @dimension
return @data[arg]
end
def []= (*arg)
val = arg.pop
raise IndexError unless arg.size == @dimension
@data[arg] = val
return val
end
end#=======================================================================#
# リンクによる多重配列を実現
#=======================================================================#
class DimByAry
attr_reader :data
def initialize(*arg)
@dimension = arg.clone
@data = make_array( arg.clone )
print @data
end
def make_array( dim )
dim = dim.dup
size = dim.shift
return Array.new( size ){ dim.size == 0 ? nil : make_array( dim ) }
end
def [](*arg)
raise IndexError unless arg.size == @dimension.size
val = @data
arg.each{ |idx|
return nil unless val = val[idx]
}
return val
end
def []= (*arg)
val = arg.pop
raise IndexError unless arg.size == @dimension.size
idx = arg.pop
ary = arg.inject( @data ){ |res,i|
res[i] = Array.new unless res[i]
res = res[i]
}
return ary[idx] = val
end
end#=======================================================================#
# 多次元配列を一次元に配列にマッピング
#=======================================================================#
class DimByStd
def initialize(*arg)
@dimension = *arg
@data = Array.new( @dimension.inject(1){|res,itm| res *= itm })
end
def [](*arg)
raise IndexError unless arg.size == @dimension.size
index = 0
arg.each_with_index { |idx,dix | index = index * @dimension[dix] + idx }
return @data[index]
end
def []= (*arg)
val = arg.pop
raise IndexError unless arg.size == @dimension.size
index = 0
arg.each_with_index { |idx,dix | index = index * @dimension[dix] + idx }
@data[index] = val
return val
end
end#=======================================================================#
# テスト
#=======================================================================#
klasses = [DimByStd, DimByAry, DimByHashAry, DimByHashPack, DimByHashStr]
klasses.each do |klass|
bgntime = Process.times.utime
dim = klass.new(XSIZE,YSIZE,ZSIZE)
(0..XSIZE-1).map{ |x|
(0..YSIZE-1).map{ |y|
(0..ZSIZE-1).map{ |z|
dim[x,y,z] = x+y+z
}
}
}
COUNT.times do
total = 0
(0 .. XSIZE-1).map{ |x|
(0 .. YSIZE-1).map{ |y|
(0 .. ZSIZE-1).map{ |z|
total += dim[x,y,z]
}
}
}
end
endtime = Process.times.utime
printf "%-20s %10.3f sec\n", klass.to_s, endtime - bgntime
dim = nil
GC.start
end
