はじめに
Rubyの配列は可変長配列であり、両端キューです。それは shift, unshift, push, pop のメソッドを持っている点から明らかです。
ではRubyで可変長配列を実装するとは何を言っているのでしょうか？
それはもしRubyが配列の要素数が増減したときに言語側でメモリの動的確保を行なってくれない言語だったらを仮定して、可変長配列を実装してみました。
両端キューには対応していませんが、C++のvectorを参考にスタック構造を実装しました。
劣化車輪の再発明でしかありませんが、勉強として作成したためアウトプットします。
実装
class MyVector
def initialize(*arr)
@heap = arr
@size = arr.size
@max_size = arr.size
keep_memory(arr)
end
attr_reader :heap
attr_reader :size
def [](idx)
@heap[idx]
end
def []=(idx, val)
@heap[idx] = val
end
def push(val)
if @size + 1 >= @max_size then
keep_memory(@heap)
end
@heap[@size] = val
@size += 1
end
alias << push
def pop
if @size.zero? then
raise 'failed'
end
@size -= 1
res = @heap[@size]
@heap[@size] = nil
return res
end
private
def keep_memory(a)
arr = a.dup
@max_size += 1
@heap = arr.concat(Array.new(@max_size, nil))
@max_size *= 2
end
end
usage
# 初期値が存在する場合
v = MyVector.new(1,2)
p [v.heap, v.size] # [[1, 2, nil, nil, nil], 2]
v.push 3
p [v.heap, v.size] # [[1, 2, 3, nil, nil], 3]
v << 4
v << 5
p [v.heap, v.size] # [[1, 2, 3, 4, 5], 5]
v << 6
p [v.heap, v.size] # [[1, 2, 3, 4, 5, 6, nil, nil, nil, nil, nil, nil], 6]
p v.pop # 6
p [v.heap, v.size] # [[1, 2, 3, 4, 5, nil, nil, nil, nil, nil, nil, nil], 5]
# 初期値が空の場合
v2 = MyVector.new
p [v2.heap, v2.size] # [[nil], 0]
v2.push 11
p [v2.heap, v2.size] # [[11], 1]
v2 << 12
v2 << 13
p [v2.heap, v2.size] # [[11, 12, 13, nil], 3]
おわり
確保している配列の要素数がいっぱいになったタイミングで現在の要素数+1の2倍確保するような実装にしました。
C++のvector::push_backの、
vectorの実装で行われるメモリ確保戦略では、再確保の際にそれら要素がぴったり収まるサイズを確保するのではなく、少し多めの1.5倍や2倍といったサイズのメモリを確保し、再確保の回数を減らしている。
を参考にしています。
現在の要素数+1なのは、初期値が存在しない場合を考慮してです。
元々の要素を拡張後の配列にコピーするのにC言語ならポインタのポインタを使うかループで新しく作成した配列に詰め直すかしますが、面倒だしconcatがあるのでconcatで実装しました。
C/C++で実装しなかった理由はRubyで書いたほうが処理を理解してもらいやすいと考えたからです。
でも def [](idx) や def []=(idx, val) の処理って普段見かけない処理なのでイマイチピンとこないですよね。Ruby 3.1 リファレンスマニュアル 演算子式を参考にして、コードを読み解いてください。
C++のvectorを見るだけでもまだまだ実装できそうなものはありますが、今回はここで終わります。
読んでいただきありがとうございました。