ruby でシンプルな連結リストを実装し、配列との性能比較を行ったメモ。
データを読み込んで集計処理を行う場合に、配列にデータを格納しますが、
配列が最大サイズに達すると、サイズを拡大して再度データを格納するため、
実行時間が大幅に長くなる場合があります。
そこで、1から1千万の整数を生成して、以下の方法で処理時間を比較してみました。
・方法1: 配列に値を全て格納してから出力
・方法2: 連結リストに値を全て格納し、配列に変換してから出力
※連結リストの実装例は最後に記します。
実行結果では、方法2は方法1の約1/2の実行時間でした。
以下、各方法のプログラムと、実行時間です。
■方法1: 配列に値を全て格納してから出力
■方法2: 連結リストに値を全て格納し、配列に変換してから出力
■連結リストの実装例
データを逐次追加するのが主要な使い方のため、連結リストの末尾に値を追加する push と、
連結リストを配列に変換する to_a のみを実装。
データを読み込んで集計処理を行う場合に、配列にデータを格納しますが、
配列が最大サイズに達すると、サイズを拡大して再度データを格納するため、
実行時間が大幅に長くなる場合があります。
そこで、1から1千万の整数を生成して、以下の方法で処理時間を比較してみました。
・方法1: 配列に値を全て格納してから出力
・方法2: 連結リストに値を全て格納し、配列に変換してから出力
※連結リストの実装例は最後に記します。
実行結果では、方法2は方法1の約1/2の実行時間でした。
以下、各方法のプログラムと、実行時間です。
■方法1: 配列に値を全て格納してから出力
num = 10000000
# データ登録
arr = Array.new
1.upto(num) do |i|
arr.push(i)
end
# 表示
arr.each do |elem|
printf("%s\n", elem)
end
実行時間 real 0m36.069s user 0m35.909s sys 0m0.156s
■方法2: 連結リストに値を全て格納し、配列に変換してから出力
num = 10000000
# データ登録
require 'list'
list = List.new
1.upto(num) do |i|
list.push(i)
end
# リストを配列に変換
arr = list.to_a()
# 出力
arr.each do |elem|
printf("%s\n", elem)
end
実行時間 real 0m18.227s user 0m17.907s sys 0m0.316s
■連結リストの実装例
データを逐次追加するのが主要な使い方のため、連結リストの末尾に値を追加する push と、
連結リストを配列に変換する to_a のみを実装。
class List
class Cell
attr_accessor :val
attr_accessor :next
def initialize(val = nil)
@val = val
@next = nil
end
end
def initialize()
@num = 0
@head = nil
@tail = @head
end
def push(val)
if @head.nil?
@tail = @head = Cell.new(val)
else
@tail.next = Cell.new(val)
@tail = @tail.next
end
@num += 1
end
def to_a()
arr = Array.new(@num)
i = 0
cell = @head
while cell
arr[i] = cell.val
cell = cell.next
i += 1
end
return arr
end
end
