【アルゴリズムの勉強】Rubyでデータ構造のキューを書いてみる
アルゴリズムの勉強としてリングバッファによるキューをRubyで実装する。
キューとは
キュー(英: queue)、あるいは待ち行列はコンピュータの基本的なデータ構造の一つ。データを先入れ先出し[1]のリスト構造で保持するものである。キューからデータを取り出すときには、先に入れられたデータから順に取り出される。キューにデータを入れることをエンキュー[2]、取り出すことをデキュー[3]という。
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でデータ構造のスタックを書いてみる
スタックとは
スタックは、コンピュータで用いられる基本的なデータ構造の1つで、データを後入れ先出し(LIFO: Last In First Out; FILO: First In Last Out)の構造で保持するものである。抽象データ型としてのそれを指すこともあれば、その具象を指すこともある。
特にその具象としては、割込みやサブルーチンを支援するために極めて有用であることから、1970年代以降に新しく設計された、ある規模以上のコンピュータは、スタックポインタによるコールスタックをメモリ上に持っていることが多い。
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でハッシュ法(オープンアドレス法)を使用してデータの追加・検索・削除を行う
概要
ハッシュ法(オープンアドレス法)を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。
オープンアドレス法とは
衝突が発生した際、テーブル中の空いている別の番地を探す方式を開番地法と呼ぶ。その方法としてハッシュ関数とは別の関数を用いて次の候補となる番地を求める。別の番地を探す関数は繰り返し適用することによってテーブル内の全ての番地を走査できるように選ぶ。
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でハッシュ法(チェイン法)を使用してデータの追加・検索・削除を行う
概要
ハッシュ法(チェイン法)を用いてデータの追加・検索・削除を行う。
ハッシュ法を用いない方法と比べ、データの探索だけではなくデータの追加・削除も効率良く行う事ができる。
チェイン法とは
衝突を起こしたキー同士をポインタでつなぐ方式を連鎖法と呼ぶ。テーブルの各番地にはキーそのものではなく、同族キーを保持するリンクリストを格納する。
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個)の要素を無視することができる。
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つの意味で使われる。
・実データには出現しない、データの終了を表すための専用の値
・入力データを処理するループの終了条件が複数ある場合に、条件判定の数を削減するために置くダミーのデータ
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