【アルゴリズムの勉強】Rubyでデータ構造のキューを書いてみる

アルゴリズムの勉強としてリングバッファによるキューをRubyで実装する。

キューとは

キュー(英: queue)、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。

キュー (コンピュータ) - Wikipedia

Rubyで実装

class Queue
  def initialize(capacity)
    @number = @front = @rear = 0
    @max = capacity
    @que = Array.new(capacity)
    p @que
  end

  def enque(value)
    if @number >= @max
      puts "キューは満杯です"
    else
      @que[@rear] = value
      @number += 1
      if (@rear + 1) == @max
        @rear = 0
      else
        @rear += 1
      end
      p @que
    end
  end

  def deque
    if @number <= 0
      puts "キューは空です"
    else
      result = @que[@front]
      @number += -1
      if (@front + 1) == @max
        @front = 0
      else
        @front += 1
      end
      puts "#{result}を取り出しました"
    end
  end

  def next_value
    if @number <= 0
      puts "キューは空です"
    else
      result = @que[@front]
      puts "次に取り出される値は#{result}です"
    end
  end

  def search(value)
    for i in 0..(@number - 1)
      index = (i + @front) % @max
      if @que[index] == value
        puts "#{value}はキュー内に存在します"
        return
      end
    end
    puts "#{value}はキュー内に存在しません"
  end

  def clear
    @number = @front = @rear = 0
    puts "キューを空にしました。"
  end

  def capacity
    puts "キューの容量は#{@max}です"
  end

  def number_of_data
    puts "キューには#{@number}つのデータが格納されています"
  end

  def empty?
    if @number <= 0
      puts "キューは空です"
    else
      puts "キューは空ではありません"
    end
  end

  def full?
    if @number >= @max
      puts "キューは満杯です"
    else
      puts "キューはまだ空き領域が存在します"
    end
  end

  def dump
    if @number <= 0
      puts "スタックは空です"
    else
      for index in 0..(@number - 1)
        puts @que[index]
      end
    end
  end
end

queue = Queue.new(5)
# => [nil, nil, nil, nil, nil]
queue.enque(5)
# => [5, nil, nil, nil, nil]
queue.enque(12)
# => [5, 12, nil, nil, nil]
queue.deque
# => 5を取り出しました
queue.enque(2)
# => [5, 12, 2, nil, nil]
queue.enque(52)
# => [5, 12, 2, 52, nil]
queue.deque
# => 12を取り出しました
queue.next_value
# => 次に取り出される値は2です
queue.search(2)
# => 2はキュー内に存在します
queue.capacity
# => キューの容量は5です
queue.number_of_data
# => キューには2つのデータが格納されています
queue.empty?
# => スタックはまだ空き領域が存在します
queue.enque(87)
# => [5, 12, 2, 52, 87]
queue.enque(32)
# => [32, 12, 2, 52, 87]
queue.enque(412)
# => [32, 412, 2, 52, 87]
queue.enque(999)
# => キューは満杯です
queue.clear
# => キューを空にしました。
queue.empty?
# => キューは空です

参考文献、参考リンク

【アルゴリズムの勉強】Rubyでデータ構造のスタックを書いてみる

アルゴリズムの勉強としてRubyでスタックを実装する。

スタックとは

スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し(LIFO: Last In First Out; FILO: First In Last Out)の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。

スタック - Wikipedia

Rubyで実装

class Stack
  def initialize(capacity)
    @pointer = 0
    @max = capacity
    @stack = Array.new(capacity)
    p @stack
  end

  def push(value)
    if @pointer >= @max
      puts "スタックは満杯です"
    else
      @stack[@pointer] = value
      @pointer += 1
      p @stack
    end
  end

  def pop
    if @pointer <= 0
      puts "スタックは空です"
    else
      @pointer += -1
      puts "#{@stack[@pointer]}を取り出しました"
    end
  end

  def next_value
    if @pointer <= 0
      puts "スタックは空です"
    else
      result = @stack[@pointer - 1]
      puts "次に取り出される値は#{result}です"
    end
  end

  def search(value)
    for index in 0..(@pointer - 1)
      if @stack[index] == value
        puts "#{value}はスタック内に存在します"
        return
      end
    end
    puts "#{value}はスタック内に存在しません"
  end

  def clear
    @pointer = 0
    puts "スタックを空にしました。ポインタの位置は#{@pointer}です"
  end

  def capacity
    puts "容量のサイズは#{@max}です"
  end

  def number_of_data
    puts "スタックには#{@pointer}つのデータが格納されています"
  end

  def empty?
    if @pointer <= 0
      puts "スタックは空です"
    else
      puts "スタックはまだ空き領域が存在します"
    end
  end

  def full?
    if @pointer >= @max
      puts "スタックは満杯です"
    else
      puts "スタックはまだ空き領域が存在します"
    end
  end

  def dump
    if @pointer <= 0
      puts "スタックは空です"
    else
      for index in 0..(@pointer - 1)
        puts @stack[index]
      end
    end
  end
end

stack = Stack.new(5)
# => [nil, nil, nil, nil, nil]
stack.push(5)
# => [5, nil, nil, nil, nil]
stack.push(12)
# => [5, 12, nil, nil, nil]
stack.pop
# => 12を取り出しました
stack.push(2)
# => [5, 2, nil, nil, nil]
stack.push(52)
# => [5, 2, 52, nil, nil]
stack.next_value
# => 次に取り出される値は52です
stack.search(2)
# => 2はスタック内に存在します
stack.capacity
# => 容量のサイズは5です
stack.number_of_data
# => スタックには3つのデータが格納されています
stack.empty?
# => スタックはまだ空き領域が存在します
stack.push(87)
# => [5, 2, 52, 87, nil]
stack.push(12)
# => [5, 2, 52, 87, 12]
stack.full?
# => スタックは満杯です

参考文献、参考リンク

【アルゴリズムの勉強】Rubyでハッシュ法(オープンアドレス法)を使用してデータの追加・検索・削除を行う

概要

ハッシュ法(オープンアドレス法)を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。

オープンアドレス法とは

衝突が発生した際、テーブル中の空いている別の番地を探す方式を開番地法と呼ぶ。その方法としてハッシュ関数とは別の関数を用いて次の候補となる番地を求める。別の番地を探す関数は繰り返し適用することによってテーブル内の全ての番地を走査できるように選ぶ。

ハッシュテーブル - Wikipedia

Rubyで実装

OCCUPIED = 0
EMPTY = 1
DELETED = 2
KEY = 0
STATUS = 1
ALONE = true

def create_hash_table(table_size)
  return Array.new(table_size, [nil, EMPTY])
end

def get_hash_value(key, table_size)
  return key % table_size
end

def get_rehash_value(hash_value, table_size)
  return (hash_value + 1) % table_size
end

def add_data(key, hash_table, table_size)
  result = search(key, hash_table, table_size)
  if result != nil
    puts "この値は既に追加済みです"
    return
  end
  hash_value = get_hash_value(key, table_size)
  target = hash_table[hash_value]

  table_size.times {|index|
    if target[STATUS] == EMPTY || target[STATUS] == DELETED
      hash_table[hash_value] = [key, OCCUPIED]
      p hash_table
      return
    end
    hash_value = get_rehash_value(hash_value, table_size)
    target = hash_table[hash_value]
  }
  puts "値を追加するスペースが存在しません"
end

def delete_data(key, hash_table, table_size)
  result = search(key, hash_table, table_size)
  return if result.nil?
  result[STATUS] = DELETED
  p hash_table
end

def search(key, hash_table, table_size, is_alone = false)
  hash_value = get_hash_value(key, table_size)
  target = hash_table[hash_value]
  table_size.times {|index|
    if target[STATUS] == EMPTY || target[STATUS] == DELETED
      puts "#{key}は見つかりませんでした" if is_alone
      return nil
    end
    if target[STATUS] == OCCUPIED && target[KEY] == key
      puts "#{key}はハッシュテーブルに存在します" if is_alone
      return target
    end
    hash_value = get_rehash_value(hash_value, table_size)
    target = hash_table[hash_value]
  }
  return nil
end

table_size = 5
hash_table = create_hash_table(table_size)
p hash_table
# => [[nil, 1], [nil, 1], [nil, 1], [nil, 1], [nil, 1]]

add_data(13, hash_table, table_size)
# => [[nil, 1], [nil, 1], [nil, 1], [13, 0], [nil, 1]]
add_data(3, hash_table, table_size)
# => [[nil, 1], [nil, 1], [nil, 1], [13, 0], [3, 0]]
add_data(4, hash_table, table_size)
# => [[4, 0], [nil, 1], [nil, 1], [13, 0], [3, 0]]
add_data(9, hash_table, table_size)
# => [[4, 0], [9, 0], [nil, 1], [13, 0], [3, 0]]
add_data(12, hash_table, table_size)
# => [[4, 0], [9, 0], [12, 0], [13, 0], [3, 0]]
add_data(12, hash_table, table_size)
# => この値は既に追加済みです
add_data(11, hash_table, table_size)
# => 値を追加するスペースが存在しません
search(4, hash_table, table_size, ALONE)
# => 4はハッシュテーブルに存在します
delete_data(12, hash_table, table_size)
# => [4, 0], [9, 0], [12, 2], [13, 0], [3, 0]]
search(12, hash_table, table_size, ALONE)
# => 12は見つかりませんでした

参考文献、参考リンク

【アルゴリズムの勉強】Rubyでハッシュ法(チェイン法)を使用してデータの追加・検索・削除を行う

概要

ハッシュ法(チェイン法)を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。

チェイン法とは

衝突を起こしたキー同士をポインタでつなぐ方式を連鎖法と呼ぶ。テーブルの各番地にはキーそのものではなく、同族キーを保持するリンクリストを格納する。

ハッシュテーブル - Wikipedia

Rubyで実装

original_data = [3, 6, 10, 12, 13, 15, 31, 40]
KEY = 0
NEXT = 1

def create_hash_table(table_size)
  return Array.new(table_size)
end

def get_hash_value(key, table_size)
  return key % table_size
end

def add_data(key, hash_table, table_size)
  hash_value = get_hash_value(key, table_size)
  target = hash_table[hash_value]

  while !target.nil?
    if target[KEY] == key
      puts "この値は既に追加済みです"
      return
    end
    target = target[NEXT]
  end

  data = [key, hash_table[hash_value]]
  hash_table[hash_value] = data
end

def delete_data(key, hash_table, table_size)
  hash_value = get_hash_value(key, table_size)
  target = hash_table[hash_value]
  past_target = nil

  while !target.nil?
    if target[KEY] == key
      if past_target == nil
        hash_table[hash_value] = target[NEXT]
      else
        past_target[NEXT] = target[NEXT]
      end
      return
    end
    past_target = target
    target = target[NEXT]
  end

  puts "#{key}は見つかりませんでした"
end

def search(key, hash_table, table_size)
  hash_value = get_hash_value(key, table_size)
  target = hash_table[hash_value]

  while !target.nil?
    if target[KEY] == key
      puts "#{key}はハッシュテーブルに存在します"
      return
    end
    target = target[NEXT]
  end

  puts "#{key}は見つかりませんでした"
end

table_size = 5
hash_table = create_hash_table(table_size)
p hash_table
# => [nil, nil, nil, nil, nil]

# 元のデータをハッシュテーブルに追加
original_data.each{|data|
  add_data(data, hash_table, table_size)
}
p hash_table
# => [[40, [15, [10, nil]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil]

# 新しくデータを追加
add_data(35, hash_table, table_size)
p hash_table
# => [[35, [40, [15, [10, nil]]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil]

# 検索
search(15, hash_table, table_size)
# => 15はハッシュテーブルに存在します

# 削除
delete_data(15, hash_table, table_size)
p hash_table
# => [[35, [40, [10, nil]]], [31, [6, nil]], [12, nil], [13, [3, nil]], nil]

参考文献、参考リンク

【アルゴリズムの勉強】Rubyでハッシュ法を使用せずデータの追加を行う

概要

ハッシュ法を使用せず昇順にソートされた状態のデータに新しい値の追加を行う。
バイナリサーチのアルゴリズムを用いて挿入すべき位置を見つけ値を追加し、それ以降の全要素を一つずつ後方へ移動するため、ハッシュ法を用いたデータの追加と比べ効率は悪い。

Rubyで実装

original_data = [1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 20, 24, 30]

def add_data(value, asc_sorted_data)
  number_of_elements = asc_sorted_data.count
  insert_location = get_insert_location(value, asc_sorted_data, number_of_elements)
  if insert_location == -1
    puts "#{value}は既に追加済みです"
    return asc_sorted_data
  end
  while insert_location <= number_of_elements
    original_value = asc_sorted_data[insert_location]
    asc_sorted_data[insert_location] = value
    value = original_value
    insert_location += 1
  end
  return asc_sorted_data
end

def get_insert_location(target, asc_sorted_data, number_of_elements)
  left = 0
  right = number_of_elements - 1

  # バイナリサーチのアルゴリズムを使用
  while left <= right
    center = (left + right) / 2
    return -1 if asc_sorted_data[center] == target
    if asc_sorted_data[center - 1] < target && asc_sorted_data[center] > target
      break
    end
    if asc_sorted_data[center] < target
      left = center + 1
    else
      right = center - 1
    end
  end
  if center == (number_of_elements - 1) && asc_sorted_data[center] < target
    insert_location = center + 1
  else
    insert_location = center
  end

  return insert_location
end

p original_data
# => [1, 3, 5, 6, 8, 10, 12, 13, 15, 17, 20, 24, 30]
data = add_data(11, original_data)
p data
# => [1, 3, 5, 6, 8, 10, 11, 12, 13, 15, 17, 20, 24, 30]

【アルゴリズムの勉強】Rubyで二分探索(バイナリサーチ)を書いてみる

アルゴリズムの勉強としてRubyで二分探索(バイナリサーチ)を実装する。

二分探索とは

ソート済みのリストや配列に入ったデータ(同一の値はないものとする)に対する検索を行うにあたって、 中央の値を見て、検索したい値との大小関係を用いて、検索したい値が中央の値の右にあるか、左にあるかを判断して、片側には存在しないことを確かめながら検索していく。
大小関係を用いるため、未ソートのリストや大小関係の定義されない要素を含むリストには二分探索を用いることはできない。
n個のデータがある場合、時間計算量はOlog2nである(O記法)。
n個のデータの中央の値を見ることで、1回の操作でn/2個程度(奇数の場合は(n-1)/2個、偶数の場合はn/2個または(n/2)-1個)の要素を無視することができる。

二分探索 - Wikipedia

Rubyで実装

arr = [2, 4, 6, 9, 10, 12, 15, 20, 25, 60]
number_of_elements = arr.count

def binary_search(arr, number_of_elements, target)
  left = 0
  right = number_of_elements - 1

  while left <= right
    center = (left + right) / 2
    if arr[center] == target
      return center
    elsif arr[center] < target
      left = center + 1
    else
      right = center - 1
    end
  end

  return -1
end

target = 20
result = binary_search(arr, number_of_elements, target)
if result == -1
  puts "値が#{target}の要素は配列内に存在しません"
else
  puts "要素の値が#{target}のインデックス => #{result}"
end

参考文献、参考リンク

【アルゴリズムの勉強】Rubyで番兵法を用いた線形探索を書いてみる

アルゴリズムの勉強としてRubyで番兵法を用いた線形探索を実装する。

番兵法とは

データの終了を示すために配置される特殊なデータを指す。この用語は、微妙に異なる以下の2つの意味で使われる。
・実データには出現しない、データの終了を表すための専用の値
・入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ

番兵 - Wikipedia

Rubyで実装

arr = [4, 20, 6, 10, 2, 15, 60, 9, 25, 12]
number_of_elements = arr.count

def linear_search_with_sentinel_method(arr, number_of_elements, target)
  index = 0
  arr[number_of_elements] = target

  loop do
    break if arr[index] == target
    index += 1
  end

  if index == number_of_elements
    return -1
  else
    return index
  end
end

target = 10
result = linear_search_with_sentinel_method(arr, number_of_elements, target)
if result == -1
  puts "値が#{target}の要素は配列内に存在しません"
else
  puts "要素の値が#{target}のインデックス => #{result}"
end

参考文献、参考リンク