오늘은 해시에 저장된 모든 키와 값을 원하는 형태로 변경할 수 있는 transform_keys와 transform_values 메서드부터 만들어 보자.
아래 코드를 보면 두 메서드 모두 each 메서드로 현재 MyHash 객체의 데이터를 하나씩 순회하면서 새로 만들어 놓은 MyHash 객체에 데이터를 추가해 넣는 단순한 로직이다.
다만 transform_keys 메서드는 전달된 블록에 키를 인수로 전달하여 실행한 결괏값을 '키'로 사용하고 transform_values 메서드는 값을 블록에 전달하여 실행한 결괏값을 '값'으로 사용한다는 것만 다르다.
class MyHash
...생략
def transform_keys
mh = MyHash.new
each do |k, v|
mh[yield(k)] = v
end
mh
end
def transform_values
mh = MyHash.new
each do |k, v|
mh[k] = yield(v)
end
mh
end
...생략
end코드를 my_hash.rb 파일에 저장한 후 irb를 실행하여 아래 그림처럼 테스트를 진행해 보자.
두 메서드 모두 잘 동작하고 원래의 MyHash 객체는 변함이 없다는 것도 알 수 있다.
지금까지 MyHash 객체를 생성하면서 추가한 데이터의 순서가 유지되지 않아 불편했는데 순서가 유지되도록 프로그램을 개선해 보자.
간단한 방법으로 인스턴스 변수를 하나 만들어 배열을 할당해 놓고 데이터가 추가되거나 삭제될 때 그 배열에도 함께 반영해 준다면, 전체 데이터를 순회할 때는 그 배열을 사용하면 순서를 유지할 수 있다.
그런데 데이터의 순서 유지를 위해 배열을 사용하게 될 경우 특정 데이터(entry)를 삭제하기 위해서는 인덱스가 아닌 값(object_id)을 비교해서 찾아야 하기 때문에 전체 요소에 대한 탐색이 필요할 수 있다.
그리고 (내부적으로) 삭제된 요소 다음의 요소들을 이동시켜야 하는 작업이 필요하므로 특히, 배열의 크기가 클 경우 성능에 안 좋은 영향을 줄 수 있다.
그래서 MyHash 클래스에서는 특정 데이터(entry)의 삭제를 빠르게 처리할 수 있도록 이중 연결 리스트(Doubly Linked List)를 사용하려고 한다.
물론 이중 연결 리스트를 사용해도 노드가 갖는 값을 기준으로 삭제 대상 노드를 찾는다면 전체 노드를 탐색해야 할 수도 있다.
그러나 MyHash 클래스에서는 키-값 쌍의 데이터를 보관하는 엔트리 자체를 노드로 사용할 것이기 때문에 삭제 대상 노드에 대한 탐색 없이 삭제 대상 노드의 이전 노드와 다음 노드를 서로 연결만 시켜주면 된다.
수정한 MyHash 클래스의 코드를 하나씩 살펴보자.
먼저 엔트리 자체를 노드로 사용하기 위해 Entry 클래스에 이전 노드와 다음 노드를 저장할 prev와 next 속성을 추가했고, MyHash 클래스에도 시작 노드와 마지막 노드를 저장할 @head와 @tail 인스턴스 변수를 추가했다.
이후에 전체 데이터를 순회하는 each 메서드를 @head 인스턴스 변수를 사용하도록 수정할 예정이다.
@tail은 새로운 데이터를 추가할 때 해당 노드(entry)를 가장 마지막에 연결하기 위해서 사용한다.
데이터 추가와 삭제 시 노드 간의 연결을 새로 만들기 위해 []= 연산자와 delete 메서드에서 각각 connect_entry와 disconnect_entry 메서드를 호출하도록 수정했다.
class MyHash
include Enumerable
Entry = Struct.new(:key, :value, :prev, :next)
attr_reader :default, :default_proc
def initialize(*default, &default_proc)
...생략
@head = nil
@tail = nil
end
...생략
def []=(key, value)
bucket, entry = bucket_and_entry(key)
if entry
entry.value = value
else
entry = Entry.new(key, value)
connect_entry(entry)
bucket << entry
value
end
end
def delete(key)
bucket, entry = bucket_and_entry(key)
if entry
disconnect_entry(entry)
bucket.delete(entry)
entry.value
elsif block_given?
yield(key)
end
end
...생략
private
def connect_entry(entry)
if @tail
@tail.next = entry
entry.prev = @tail
@tail = entry
else
@head = entry
@tail = entry
end
end
def disconnect_entry(entry)
prev_e = entry.prev
next_e = entry.next
if prev_e
prev_e.next = next_e
else
@head = next_e
end
if next_e
next_e.prev = prev_e
else
@tail = prev_e
end
end
endconnect_entry 메서드를 보면 @tail이 실제 마지막 노드를 참조하고 있다면 그 마지막 노드의 다음 노드(next)로 새롭게 추가되는 노드(entry)를 설정해 주고, 새롭게 추가되는 노드의 이전 노드로는 그 마지막 노드를 설정한다.
그러면 이제 새롭게 추가된 노드가 실제 마지막 노드이므로 @tail 인스턴스 변수의 값을 그 노드로 변경한다.
MyHash 객체가 비어 있는 상태에서 데이터가 추가될 때는 해당 노드가 시작 노드이면서 마지막 노드이므로 @head와 @tail이 같은 노드를 갖게 된다.
disconnect_entry 메서드는 삭제 대상 노드의 이전 노드가 있으면 그 이전 노드의 다음 노드로 삭제 대상 노드의 다음 노드를 설정하고 이전 노드가 없다면 시작 노드가 삭제되는 경우이므로 @head에 다음 노드를 설정한다.
그리고 삭제 대상 노드의 다음 노드가 있다면 그 다음 노드의 이전 노드로 삭제 대상 노드의 이전 노드를 설정하고 다음 노드가 없다면 마지막 노드가 삭제되는 경우이므로 @tail에 이전 노드를 설정한다.
즉 MyHash 객체에 데이터가 하나뿐이라면 해당 노드가 시작 노드이면서 마지막 노드이기 때문에 그 데이터를 삭제하게 되면 @head와 @tail의 값은 모두 nil이 될 것이다.
이제 실제 저장된 순서대로 데이터를 순회하도록 each 메서드를 수정하고, @bucket_list를 사용하여 데이터를 순회하던 몇 개의 메서드를 Enumerable 모듈이 제공하는 메서드를 사용하도록 수정하자.
그래야 keys나 values 메서드의 결괏값에서도 순서가 유지된 채로 나오는데, Enumerable 모듈의 메서드가 MyHash 클래스에서 정의한 each 메서드를 사용하기 때문이다.
each 메서드를 보면 while 문을 사용해서 @head에 저장된 노드부터 시작해서 다음 노드가 있을 때까지 블록을 반복해서 실행한다.
@head와 @tail은 항상 시작과 마지막 노드를 가지고 있고 새로운 데이터는 마지막 노드의 다음 노드로 연결해가는 방식이기 때문에 @head의 노드부터 다음 노드를 계속 따라가면 등록한 순서대로 모든 노드를 순회하게 된다.
class MyHash
... 생략
def size
count
end
def value?(value)
any? { |k, v| v.equal?(value) || v == value }
end
def keys
map { |k, v| k }
end
def values
map { |k, v| v }
end
def each
entry = @head
while entry
yield([entry.key, entry.value])
entry = entry.next
end
self
end
...생략
endvalue? 메서드는 any? 메서드를 사용해서 그리고 keys와 values 메서드는 map 메서드를 사용해서 데이터가 등록된 순서를 유지하면서도 기존 코드보다 더 간결해졌다.
이제 지금까지 수정한 코드를 my_hash.rb 파일에 저장한 후 irb를 실행하여 아래 그림처럼 테스트해 보자.
처음 MyHash 객체를 생성할 때 인수로 준 데이터들이 순서대로 잘 조회되는 것을 볼 수 있다.
그리고 순서 상 중간에 있는 데이터(:c=>3)를 삭제한 후 다시 동일한 키와 값을 저장하면 예상대로 가장 끝에 나오는 것을 볼 수 있다.
아래 지금까지 작성한 MyHash 클래스의 전체 코드를 볼 수 있다.
class MyHash
include Enumerable
Entry = Struct.new(:key, :value, :prev, :next)
attr_reader :default, :default_proc
def initialize(*default, &default_proc)
if block_given?
raise ArgumentError, "number of arguments must be 0" if default.size > 0
@default_proc = default_proc
elsif default.size > 1
raise ArgumentError, "number of arguments must be 0..1"
elsif default.size == 1
@default = default[0]
end
@bucket_cnt = 10
@bucket_list = Array.new(@bucket_cnt) { [] }
@head = nil
@tail = nil
end
def default=(default)
@default = default
@default_proc = nil
end
def default_proc=(default_proc)
raise ArgumentError, "argument type must be Proc" if !default_proc.nil? && !default_proc.is_a?(Proc)
@default_proc = default_proc
@default = nil
end
def [](key)
bucket, entry = bucket_and_entry(key)
if entry
entry.value
elsif default_proc.is_a?(Proc)
default_proc.call(self, key)
elsif !default.nil?
default
end
end
def []=(key, value)
bucket, entry = bucket_and_entry(key)
if entry
entry.value = value
else
entry = Entry.new(key, value)
connect_entry(entry)
bucket << entry
value
end
end
def size
count
end
def key?(key)
bucket, entry = bucket_and_entry(key)
entry != nil
end
def value?(value)
any? { |k, v| v.equal?(value) || v == value }
end
def keys
map { |k, v| k }
end
def values
map { |k, v| v }
end
def fetch(key, *default)
raise ArgumentError, "number of arguments must be 1..2" if default.size > 1
return self[key] if key?(key)
return default[0] if default.size > 0
raise KeyError, "Key not found: #{key.inspect}"
end
def delete(key)
bucket, entry = bucket_and_entry(key)
if entry
disconnect_entry(entry)
bucket.delete(entry)
entry.value
elsif block_given?
yield(key)
end
end
def dig(*keys)
raise ArgumentError, "number of arguments must be 1+" if keys.empty?
value = self[keys.shift]
if value.nil? || keys.empty?
value
else
value.dig(*keys)
end
end
def each
entry = @head
while entry
yield([entry.key, entry.value])
entry = entry.next
end
self
end
def inspect
str = map { |k, v| "#{k.inspect}=>#{v.inspect}" }.join(", ")
"MyHash{#{str}}"
end
def to_s
inspect
end
def select
MyHash[super]
end
def reject
MyHash[super]
end
def group_by
MyHash[super]
end
def merge(other)
raise ArgumentError, "argument type must be MyHash" if !other.is_a?(MyHash)
my_h = MyHash[to_a]
other.each do |k, v|
if my_h.key?(k) && block_given?
my_h[k] = yield(k, my_h[k], v)
else
my_h[k] = v
end
end
my_h
end
def transform_keys
mh = MyHash.new
each do |k, v|
mh[yield(k)] = v
end
mh
end
def transform_values
mh = MyHash.new
each do |k, v|
mh[k] = yield(v)
end
mh
end
def self.[](*args)
my_h = MyHash.new
if args.size == 1 && args[0].is_a?(Array)
args[0].each_with_index do |e, i|
raise ArgumentError, "element type must be array: idx = #{i}" if !e.is_a?(Array)
raise ArgumentError, "number of elements must be 1..2: idx = #{i}" if e.size == 0 || e.size > 2
my_h[e[0]] = e[1]
end
elsif args.size == 1 && args[0].is_a?(Hash)
args[0].each { |k, v| my_h[k] = v }
elsif args.size >= 1
raise ArgumentError, "number of arguments must be even" if args.size.odd?
args.each_slice(2) { |k, v| my_h[k] = v }
end
my_h
end
private
def bucket_and_entry(key)
index = key.hash % @bucket_cnt
bucket = @bucket_list[index]
entry = bucket.find { |e| key.hash == e.key.hash && key.eql?(e.key) }
[bucket, entry]
end
def connect_entry(entry)
if @tail
@tail.next = entry
entry.prev = @tail
@tail = entry
else
@head = entry
@tail = entry
end
end
def disconnect_entry(entry)
prev_e = entry.prev
next_e = entry.next
if prev_e
prev_e.next = next_e
else
@head = next_e
end
if next_e
next_e.prev = prev_e
else
@tail = prev_e
end
end
end
See you agian~~