ruby でのシンプルな連結リストの実装

ruby でシンプルな連結リストを実装し、配列との性能比較を行ったメモ。

データを読み込んで集計処理を行う場合に、配列にデータを格納しますが、
配列が最大サイズに達すると、サイズを拡大して再度データを格納するため、
実行時間が大幅に長くなる場合があります。

そこで、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