【Ruby】配列でアルゴリズムを学ぶ

はじめに

プログラミング能力を高めるため、アルゴリズムの基礎を学びます。
いつもコードを書こうとすると、頭が真っ白な状態に陥ってしまいます。
その原因は足掛かりとなる知識がないからだと思います。
まず、地盤を築き、それ自体を使用もしくは応用したりできる思考力を身に付けることがゴールです。

本記事は線形構造の配列を使って学習を進めます。
RubyにはArrayとして組み込まれていますが、それを簡単に真似して自作していきます。
さらに、それを操作するメソッドを作成することで学んだ知識を応用できるようにします。

RSpecを利用してテストコードも実装しましたが、記事が長くなるため私のgo-on-ruby-algo-tripリポジトリに置きました。

(2026.01.14)
MyArrayのpushを可変長引数に対応させようと思います。

配列

配列は、順序付きのデータを格納する線形構造です。
各要素にはインデックス(順序)でアクセスすることができます。

メモリ上で連続して配置されている場合が多いため、ランダムアクセスは高速(O(1))です。ただし、末尾以外への挿入や削除は、要素をシフトする必要があるため最大O(n)の計算量がかかります。

コード

class MyArray
  def initialize
    @data  = {}
    @size = 0
  end
  
  def push(var)
    @data[@size] = var
    @size += 1
  end
  
  def get(index)
    raise(ArgumentError, "Please specify an existing array index") if index < 0 || index >= @size
      
    @data[index]
  end

  def []=(index, var)
    raise(ArgumentError, "Please specify an existing array index") if index < 0 || index >= @size
      
    @data[index] = var 
  end
  
  def insert(index, var)
    raise(ArgumentError, "Please specify an existing array index") if index < 0 || index >= @size
      
    i = @size - 1
    while i > index - 1 
      @data[i + 1] = @data[i]
      i = i - 1
    end
    @data[index] = var
    @size += 1
  end
  
  def delete(index)
    raise(ArgumentError, "Please specify an existing array index") if index < 0 || index >= @size
      
    value = @data[index]
    i = index
    while i < @size
      @data[i] = @data[i + 1]
      i = i + 1
    end
    @data[@size - 1] = nil
    @size -= 1
    value
  end
  
  def size
    @size 
  end
end

「設計方針」

このクラスから生成されるMyArrayの各インスタンスは、それぞれが独立した状態(要素とサイズ)を保持するため、インスタンス変数・インスタンスメソッドとして実装しています。
内部データ構造として@data = {}を採用した理由は、Rubyの組み込みArrayをそのまま使用すると、挿入・削除などの処理を既存メソッドに任せてしまい、アルゴリズムを自分で実装する学習効果が薄れるためです。

「配列と同じインターフェース[]を実装する」

instance.get(index)ではなく、Rubyの組み込みArrayと同様にinstance[index]という形式で要素を取得したい場合、以下のように[]メソッドを定義します。

def [](index)
  get(index)
end

「出力を配列形式にする」

putsは引数に渡されたオブジェクトのto_sを呼び出し、pはinspectを呼び出します。
そのため、以下のようにto_sとinspectを実装すると、putsやpにインスタンスを渡した際に、内部状態を配列として確認できるようになります。

def to_a
  (0...@size).map { |i| @data[i] }
end

def to_s
  to_a.to_s
end

def inspect
  to_a.inspect
end

「insert/deleteをdownto/uptoを使って実装する」

AIに評価してもらったところ、insertとdeleteメソッドについて、whileを使わずにRubyの downtoとuptoを使った実装を提案してもらいました。
アルゴリズム自体はどちらも同じで、要素をシフトするため計算量は O(n)です。ただし、コード量が減り、処理の意図が読み取りやすくなります。

  def insert(index, val)
    raise "Index out of bounds" if index < 0 || index > @size
    (@size - 1).downto(index) { |i| @data[i+1] = @data[i] }
    @data[index] = val
    @size += 1
  end

  def delete(index)
    raise "Index out of bounds" if index < 0 || index >= @size
    val = @data[index]
    index.upto(@size-2) { |i| @data[i] = @data[i+1] }
    @data.delete(@size-1)
    @size -= 1
    val
  end

downtoは、レシーバの値から引数の値まで、1ずつ減らしながらブロックの処理を繰り返します。大きい値から順に扱うため、insertによる配列要素の末尾から右にシフトしていく処理に利用できます。

uptoは、レシーバの値から引数の値まで、1ずつ増やしながらブロックの処理を繰り返します。小さい数値から順に扱うため、deleteによる配列要素の前方から左にシフトしていく処理に利用できます。

応用：操作メソッド

1. 「配列に10個の数値をpushして出力する」

while文はすでに別の箇所で使用しているため、ここではfor文とtimesメソッドを使って実装しました。

def call_myarray_push_with_for_sentence
  array = MyArray.new
  for i in 1..10
    array.push(i)
  end
  array
end

def call_myarray_push_with_times_sentence
  array = MyArray.new 
  10.times do |i|
    array.push(i + 1) # 出力結果を揃えるため、1を可算している
  end
  array
end

2. 「偶数だけを削除するメソッドを作る」

配列の各要素を走査し、要素の値が偶数である場合にdeleteメソッドを使って削除します。
この処理を配列の先頭から行うと、deleteによって要素が削除された時点で、後続の要素が左にシフトされます。
その結果、次に処理すべき要素のインデックスが変わってしまい、要素をスキップしてしまう可能性があります。

先頭から走査する場合、delete実行後にインデックスiを進めなければ、要素のシフトによるズレに対応できます。

def delete_only_even_numbers_from_begining_of_array
  array = call_myarray_push_with_for_sentence
  i = 0
  while i < array.size
    if array[i].even?
      array.delete(i)  # 削除した場合はiを進めない
    else
      i += 1
    end
  end
  array
end

一方で、配列の末尾から先頭に向かって処理すれば、削除によるインデックスのズレを考慮する必要がなく、安全に要素を削除できます。

def delete_only_even_numbers_from_end_of_array
  array = call_myarray_push_with_times_sentence
  (array.size - 1).downto(0) { |x| array.delete(x) if array[x].even? }
  array
end

3. 「配列内の最大値・最小値を自作で求める」

Rubyのmaxやminメソッドを使わずに配列の最大値・最小値を求めます。
まず、配列の先頭要素を変数に代入して初期値とします。
次に、2番目の要素から末尾まで線形探索を行い、変数の値より大きい(または小さい)要素が見つかったら変数の値を更新します。
最終的に、変数には最大値(または最小値)が保持されます。

def find_max_value_from_myarray
  array = call_myarray_push_with_for_sentence
  max_value = array[0]
  (1...array.size).each do |x|
    max_value = array[x] if max_value < array[x]
  end
  max_value
end

def find_min_value_from_myarray
  array = call_myarray_push_with_for_sentence
  min_value = array[0]
  (1...array.size).each do |x|
    min_value = array[x] if min_value > array[x]
  end
  min_value
end

4. 「配列を逆順に並べ替えるメソッドを作る」

配列の先頭要素(i = 0)と末尾の要素(配列サイズ - 1 - i)を入れ替えます。
それ以降、iを1ずつ増やしながら同じ処理を繰り返していきます。
交換処理を配列サイズの半分(配列サイズ / 2の商値)だけ繰り返せば、すべての要素を逆順に並べ替えられます。

def reverse_myarray
  array = call_myarray_push_with_for_sentence
  (0).upto(array.size / 2 -1) { |x|
    opposite_index = array.size - 1 -x
    array[x], array[opposite_index] = array[opposite_index], array[x]}
  end
  array
end

upto(array.size / 2 -1)このようにしている理由は、upto が終了値も含めて繰り返す仕様のためです。-1を付けないと、想定より1回多く処理されてしまいます。

おわりに

今回は、配列の実装によって線形探索アルゴリズムを学びました。
概念としてではなく、頭の中に物体を想像しながら考えられるようになりました。

1つの処理だけで済ませず、気になった別の方法も試すようにしました。
その結果、配列だけでも多くの知識を得られ、理解が深まりました。
以前は苦手意識がありましたが、今では楽しさも感じられるようになりました。