Ruby의 Enumerable을 넘어, 슬라이딩 윈도 문제를 Ruby답게 추상화하는 방법과 상태를 가진 윈도 및 스트림 기반 설계를 살펴봅니다.
Enumerable은 아마도 Ruby의 가장 강력한 기능 가운데 하나이며, 아니 어쩌면 가장 강력한 기능일지도 모릅니다. 이것은 여러 유용한 반복 패턴을 더 일반적인 언어로 압축해 주고, 더 명령형인 언어에서 하듯 문제를 구성 요소 단위로 쪼개기보다 당면한 문제 자체에 직접 집중할 수 있게 해줍니다.
문제는 이것이 분명 강력하긴 하지만 할 수 있는 일에는 한계가 있다는 점입니다. 그렇다면 Enumerable을 넘어서는 문제를 만났을 때 우리는 어디에 서게 될까요? 이 연재는 그런 형태들 몇 가지와, Enumerable에서 배운 교훈이 그 바깥으로 한 걸음 나아간 뒤에도 여전히 아주 잘 적용된다는 점을 살펴봅니다.
우리의 첫 번째 걸음은 윈도로 들어갑니다.
Enumerable은 유창함, 가독성, 조합 가능성 측면에서 다른 많은 Ruby 라이브러리가 평가받는 기준입니다. 동시에 이것은 스트림이 널리 퍼지기 전 비슷한 시기의 Java 같은 언어에서 보았을 법한 것과는 뚜렷이 다른 방향을 보여주기도 합니다.
다른 언어에서 4보다 큰 짝수만 골라 각각 두 배로 만든 뒤 모두 더한다고 생각해 봅시다. 루프 하나, 누산기 하나를 쓰게 될 것이고, 그 루프 본문 안에는 필터링, 변환, 합산이라는 세 가지 서로 다른 아이디어가 들어가 일을 하게 됩니다:
sum = 0
for item in 1..100
sum += item * 2 if item > 4 && item.even?
end
sum
물론 잘 동작합니다. 하지만 그 관심사들이 전부 같은 자리에 들어 있습니다. 걸러내기, 두 배로 만들기, 합치기, 이 모든 것이 한 본문에 몰려 있어서 그중 무엇 하나만 바꾸려 해도 여러 구성 요소를 동시에 이해해야만 할 것처럼 느껴집니다. 문제 자체보다 원시적인 요소를 다루고 있고, 그 방식은 그다지 표현력이 좋아 보이지 않습니다.
Enumerable은 같은 내용을 이름 붙은 의도의 연쇄로 말할 수 있게 해줍니다:
(1..100).select { |v| v.even? && v > 4 }.map { |v| v * 2 }.sum
각 메서드 호출은 하나의 분명한 아이디어입니다. 4보다 큰 짝수만 남기고, 그것들을 두 배로 만든 다음 모두 더해 최종 결과를 얻습니다. 물론 루프는 여전히 그 안에 있습니다. 하지만 이제 더 이상 루프를 생각하지 않습니다. 조각들을 생각하는 대신 결과를 설명하는 단계들의 연속을 생각하게 됩니다. 그 체인에서 어느 부분이든 꺼내 이름을 붙이고, 독립적으로 테스트하고, 다른 것으로 바꿔 넣을 수 있습니다. 이것은 단순한 자잘한 편의가 아니라 컬렉션을 생각하는 완전히 다른 방식입니다.
그것이 Enumerable의 선물입니다. 데이터 위를 움직이는 흔한 방식들에 이름을 붙여준다는 점이죠:
map은 모든 원소를 다른 것으로 변환하는 방법입니다select는 조건에 맞는 원소만 남길 수 있게 해줍니다reduce와 sum은 그것들을 모두 하나의 최종 결과로 결합할 수 있게 해줍니다심지어 group_by, tally, chunk_while, partition 같은 메서드들도 있고, 그 밖에도 많이 있습니다. 각각은 그렇지 않았다면 여러 루프와 임시 변수들로 손수 만들어야 했을 순회를 이름 붙인 것입니다. 이름과 추상화가 생기는 순간 루프는 사라지고, 그와 함께 비교적 흔한 구현들에서 따라오던 온갖 종류의 버그도 함께 사라집니다.
이 모든 것은 아주 좋습니다. 그러다가 Enumerable에 이름이 없는 문제 하나를 만나기 전까지는요. 그때는 다시 수동 루프, 인덱스 변수, 손수 누적하는 방식으로 돌아가고 싶은 유혹을 느끼게 됩니다. 배열을 두 포인터나 슬라이딩 윈도로 훑으며 모든 장부 정리를 직접 떠맡게 될지도 모릅니다. 물론 때로는 그게 맞는 선택이기도 합니다. 하지만, 솔직히 지금 와서 그게 Ruby답게 느껴지지는 않지 않나요?
이런 흔한 형태를 충분히 많이 만나기 시작하면 패턴이 보이기 시작합니다. 그리고 패턴은 이름과 추상화를 부릅니다. Ruby는 순회에 이름을 붙이고 추상화하면 우리가 뜻하는 바를 분명하게 말하고 문제에 집중할 수 있다는 것을 가르쳐 주었습니다. 지금 그 이름이 없다는 이유만으로 이것이 더 이상 사실이 아닌 것은 아닙니다. 오히려 그 이름을 찾아내고 Ruby답게 느껴지는 추상화를 써 보라는 초대에 가깝습니다.
윈도는 그런 형태 가운데 하나이고, 이 글은 바로 그것을 탐구하려 합니다.
어떤 서비스의 응답 시간 목록을 들여다보고 있고, 잡음을 줄이기 위해 이동 평균을 구하고 싶다고 합시다. 한 번에 세 샘플씩 보고, 한 칸씩 옮기며, 각 묶음의 평균을 구하는 식입니다.
이때 each_cons를 집어 들게 됩니다. 정확히 그 용도니까요:
latencies.each_cons(3).map { |window| window.sum.fdiv(3) }
이것은 깔끔하게 읽히고, 뜻하는 바를 말하고, 다른 문제를 계속 풀 수 있게 해주는 Ruby다운 답입니다. each_cons는 고정된 크기의 슬라이딩 윈도를 제공하고, 많은 문제에서 이것만으로 충분합니다. 인접 비교, n-그램, 이웃 원소 다루기 같은 것들은 모두 each_cons로 처리할 수 있습니다.
하지만 곧 눈에 들어오는 문제가 있습니다. each_cons가 내주는 모든 윈도는 그냥 평범한 배열입니다. 그래서 매번 그 숫자들을 다시 더하게 되고, 윈도는 현재 맥락에 대한 어떤 정보도 기억하지 못합니다. 그저 잘라낸 조각일 뿐입니다.
원소가 세 개뿐이면 문제가 아니지만, 더 큰 윈도에서는 중요해집니다. each_cons 자체는 한 번 슬라이드할 때마다 O(1)이지만, 이전 상태를 기억하지 않는 평범한 배열을 넘겨주기 때문에 호출하는 쪽이 각 윈도마다 O(k) 작업을 하게 됩니다. 합을 다시 구하고, 다시 훑고, 이전 단계 사이에 증분 상태가 전달되지 않기 때문입니다.
문제를 살짝 바꿔 봅시다. 실제 많은 문제가 늘 그렇듯이요.
서드파티 API로 보낼 레코드들을 배치로 묶고 있는데, 그 API는 요청 페이로드 크기에 엄격한 상한이 있습니다. 고정된 개수 제한이 아니라 고정된 바이트 수 제한입니다. 그렇다면 각 배치마다 그 한도를 넘지 않는 선에서 가능한 한 많은 레코드를 담고 싶을 것입니다.
그러면 원소가 2개일 수도 있고, 10개일 수도 있고, 전혀 다른 수일 수도 있습니다! 윈도 크기가 더 이상 고정되어 있지 않으니 each_cons는 갑자기 우리를 도울 수 없게 됩니다. Rails에는 find_in_batches가 있지만 그것도 고정 개수 기준일 뿐이고, 레코드가 얼마나 큰지는 알지도 신경 쓰지도 않습니다.
chunk_while이나 slice_when 같은 메서드들은 컬렉션을 여러 그룹으로 나눌 수 있다는 점에서 조금 더 가까워 보이지만, 윈도 사이를 가로지르는 실행 중 맥락을 갖고 있지 않기 때문에 현재 누적 합을 매번 처음부터 다시 계산하지 않고는 알 수 없습니다.
그래서 결국 손으로 쓰게 됩니다. 우리 모두가 늘 하듯이요:
def pack_batches(records, max_bytes)
batches = []
current = []
size = 0
records.each do |record|
bytes = record.bytesize
if size + bytes > max_bytes && current.any?
batches << current
current = []
size = 0
end
current << record
size += bytes
end
batches << current if current.any?
batches
end
동작은 합니다. 하지만 실제로 그 안에 무엇이 들어 있는지 보세요. current 배열, 실행 중인 size, 둘 다를 위한 리셋, 빈 배치를 막기 위한 가드가 달린 여러 조건문이 있습니다. 특정 바이트 수 아래인 그룹을 원한다는, 우리가 정말 신경 쓰는 그 한 줄은 분명 안에 있긴 합니다. 하지만 이 더 원시적인 세부 사항들에 둘러싸여 있어서 그것을 찾으려면 시간이 좀 걸릴 겁니다.
어쩌면 이런 일은 한 번만 일어날 수도 있겠죠. 그런데 또 보게 됩니다. 그리고 또 보게 됩니다. 또. 또. 또. 이런 패턴은 계속 나타나고, 매번 쓰는 구현은 미묘하게 다르지만 그 형태는 분명히 거기에 있습니다. 그리고 Rubyist로서의 본능은 계속 번쩍이며 말합니다. “분명히 이보다 나은 방법이 있을 텐데!”
눈여겨보기 시작하면 이런 패턴이 꽤 자주 나타난다는 것을 알게 됩니다.
요청 속도 제한. 어떤 사용자가 임의의 60초 윈도 안에서 N번보다 많은 요청을 보냈는지 알고 싶습니다. 타임스탬프를 따라가며 “지난 60초 안의 요청들”이라는 윈도를 유지하고, 뒤쪽으로 밀려난 것들을 버리고, 개수를 확인합니다.
로그에서 급증 감지. 예를 들어 오류 5개를 포함하는 가장 짧은 로그 구간을 찾고 싶어서, 어디서부터 문제가 터졌는지 알아내려 합니다. 줄들을 따라가며 윈도를 키워 오류 5개를 담게 만들고, 그다음 앞쪽에서 줄여 가장 촘촘한 구간을 찾습니다.
가까운 이벤트 중복 제거. 시끄러운 이벤트 스트림을 정리하면서, 어떤 이벤트 ID도 반복되지 않는 가장 긴 연속 구간을 찾고 싶습니다. 이벤트를 따라가며 윈도를 키우다가, 중복을 보는 순간 그것이 사라질 때까지 앞에서 줄입니다.
서로 다른 세 영역입니다. 이제 이들이 무엇을 공유하는지 봅시다:
이 모든 것은 “윈도를 유지하고, 키우고, 규칙을 깨면 줄인다”로 설명할 수 있습니다. 이것은 단지 편리한 묘사일 뿐만 아니라 하나의 연산이며, 우리가 추상화하고 이름을 붙일 수 있는 것입니다.
LeetCode 문제를 봤거나 면접 준비를 해본 적이 있다면, 배열을 가로지르는 left와 right 포인터를 가진 “투 포인터”와 “슬라이딩 윈도”라는 개념에 익숙할 겁니다. 저는 그 틀이 늘 마음에 걸렸습니다. 포인터는 전체 아이디어라기보다 구현 세부 사항처럼 느껴졌기 때문입니다.
배치 알고리즘을 평범한 말로 소리 내어 말해 봅시다:
빈 구간에서 시작한다. 각 레코드를 받아들인다. 구간이 너무 커지는 동안 가장 오래된 레코드를 버린다. 남은 것이 하나의 배치다.
그 문장에는 포인터가 없습니다. 구간이 있고, 무언가를 받아들이고, 필요하면 내보내고, 자기 자신의 크기를 압니다. left와 right 인덱스는 그 일을 코드로 구현하는 한 가지 방법일 뿐입니다.
이것이 빠져 있던 추상화입니다. 포인터 묘기가 아니라, 상태를 조금 들고 있고 언제 커지고 줄어들어야 하는지 아는 윈도입니다. 이렇게 놓고 보면 우리가 만들고자 하는 추상화의 형태가 훨씬 선명해집니다.
그 실마리를 더 잡아당겨 보면, 이런 문제들에서 늘 마음에 걸리던 점은 장부 정리 규칙들 때문에 실제 중요한 내용을 놓치게 된다는 것입니다. current 배열이 있고 실행 중인 size가 있고, 이 문제에서 우리가 정말 관심 있는 한 줄(예산 안에 들어오는가)은 그 모든 것의 한가운데 파묻혀 있습니다. 윈도는 두 가지 일을 하고 있습니다(항목 보관과 총합 추적). 그리고 이런 종류의 문제가 나올 때마다 그 둘을 제가 매번 손수 관리하고 싶은 마음은 전혀 없습니다.
아마 우리가 먼저 해야 할 일은 자기 자신의 실행 중 합계와 자기 자신에 대한 맥락을 추적할 수 있는 윈도라는 개념을 만드는 것일 겁니다:
class Window
attr_reader :sum
def initialize
@items = []
@sum = 0
end
def size = @items.size
def empty? = @items.empty?
def to_a = @items.dup
def push(item)
@items << item
@sum += item
self
end
def shift
item = @items.shift
@sum -= item if item
item
end
end
여기서 얻는 이점은 윈도가 합을 증분 방식으로 유지한다는 점이며, 이를 가져오는 것은 각 그룹을 다시 더할 필요가 없는 O(1) 연산이 됩니다. 앞서의 each_cons 버전은 모든 그룹마다 합을 다시 계산했지만, 이 버전은 그렇지 않습니다.
이제 배치 루프는 더 이상 합을 손수 추적하지 않고 윈도에게 물어보기만 하면 됩니다:
def pack_batches_window(records, max_bytes)
batches = []
window = Window.new
records.each do |record|
if window.sum + record > max_bytes && !window.empty?
batches << window.to_a
window = Window.new
end
window.push(record)
end
batches << window.to_a unless window.empty?
batches
end
우리는 한 걸음 나아갔습니다. 이제 더 이상 sum을 손수 추적하지 않습니다. 하지만 아직 남아 있는 것을 보세요. 여전히 루프를 쓰고 있고, 언제 새 윈도를 시작할지와 언제 결과를 밀어 넣을지를 관리하고 있습니다. 윈도는 더 똑똑해졌지만, 슬라이딩 연산 자체는 여전히 손볼 부분이 있습니다.
다시 들여다보면 슬라이드는 구현마다 꽤 비슷해 보입니다. 항목 하나를 받아들이고, 어떤 규칙이 만족될 때까지 줄이고, 그다음 남은 것을 본다. 문제마다 달라지는 것은 이것을 결정하는 규칙뿐이니, 그것을 블록 함수로 뽑아냅니다:
def slide_while(items, window, &rule_function)
results = []
items.each do |item|
window.push(item)
window.shift until window.empty? || rule_function.call(window)
results << window.to_a unless window.empty?
end
results
end
이제 배치는 거의 아무것도 아닙니다:
slide_while(records, Window.new) { |w| w.sum <= max_bytes }.max_by(&:size)
규칙은 한 줄짜리 함수 하나이고, 명시적인 루프는 사라졌습니다. 그렇지 않았다면 매번 다시 썼을 슬라이드가 이제 한곳에 모였고, 새로운 문제는 다른 블록 함수 하나를 넘기는 일로 바뀝니다.
다만 여기서 한 가지 보입니다. records가 무언가의 입력으로 들어가고 있을 뿐, 우리가 작용하는 주체가 되지는 않습니다. 그리고 여전히 넘겨줄 Window를 손수 만들고도 있습니다. 형태는 훨씬 선명해졌지만, 더 잘할 수 있습니다.
정말로 Enumerable처럼 느껴지고 더 Ruby답게 되려면, 슬라이딩이라는 개념은 컬렉션 자체나 그것을 감싸는 어떤 래퍼에 속해야 합니다. 그러니 데이터를 함수에 넘기는 대신, 그 모든 세부 사항을 우리 대신 처리하는 래퍼를 만들어 봅시다.
다만 여기에는 함정이 하나 있고, 그것을 피하기 전에 분명히 보는 것이 좋습니다.
가장 먼저 떠올릴 수 있는 것은 스트림이 Enumerator 안으로 윈도 객체들을 내보내서, 그 결과에 max_by, select 같은 메서드를 체이닝할 수 있게 하는 것입니다. 멋져 보이죠. 하지만 윈도는 가변 객체라는 점을 떠올려 보세요. 여전히 계속 슬라이드하고 있습니다. 그것을 그대로 내보내면, 스트림 안의 모든 값은 같은 객체 가 됩니다. 그리고 max_by가 그것들을 비교할 때쯤이면 그 하나뿐인 윈도는 이미 슬라이딩을 끝내고 최종 상태를 보고하게 됩니다. 예외가 발생하지도 않습니다. 그냥 조용히 틀린 답을 얻게 됩니다.
그다음 시도할 수 있는 것은 스냅샷입니다. 각 단계에서 윈도의 상태를 복사하고, 얼리고, 그 얼린 복사본을 내보냅니다. 동작은 합니다! 하지만 이제 단계마다 객체를 하나씩 할당하게 됩니다. 항목이 20만 개라면 객체가 60만 개입니다. 그 대부분은 곧바로 버려집니다. 수동 루프의 장부 정리를 가비지 컬렉터 청구서로 바꾼 셈인데, 그건 우리가 바라던 거래가 아닙니다.
그러면 진짜 질문은 이것이 됩니다. 애초에 왜 윈도가 밖으로 나가야 할까요?
생각해 보면 소비자는 실제로 그 윈도로 무엇을 할까요? 배치 문제에서는 max_by(&:size)를 부릅니다. 이동 평균에서는 map(&:average)를 부릅니다. 두 경우 모두 소비자는 각 윈도에서 숫자 하나 만 읽고 나머지는 버립니다. 누군가 길이만 물어보려고 전체 배열을 복사하고 있는 셈인데, 꽤 낭비처럼 느껴집니다.
한 가지 접근은 이렇습니다. 윈도가 밖으로 나가지 못하게 하자. 블록 안으로 넘겨주고, 소비자가 필요한 것을 읽게 하고, 다음으로 넘어가자. 이것을 차근차근 만들어 봅시다.
먼저 컬렉션을 그 위로 윈도를 슬라이드시키는 법을 아는 스트림으로 감쌉니다. 스트림은 iterate_windows를 소유하고, 그것이 우리가 지금까지 손으로 써오던 add-evict-yield 루프를 담당합니다. 각 유효한 위치에서 살아 있는 윈도 를 블록에 넘겨줍니다:
module Rivulet
class BaseWindow
def initialize = (@items = [])
def size = @items.size
def empty? = @items.empty?
def add(item) = (@items.push(item); self)
def evict = @items.shift
end
class Stream
def initialize(source) = (@source = source)
# 핵심 루프: 윈도를 키우고, 규칙이 깨지면 줄이고,
# 각 유효한 위치에서 살아 있는 윈도를 넘긴다.
def iterate_windows(rule:)
window = new_window
@source.each do |item|
window.add(item)
window.evict until window.empty? || rule.call(window)
yield window unless window.empty?
end
end
private def new_window = BaseWindow.new
end
end
이것은 앞서의 slide_while이지만, 이제 데이터의 소유자인 객체 위에 자리 잡았습니다. 스트림이 윈도를 만들고, 슬라이드를 관리하고, 넘겨줍니다. 호출하는 쪽은 블록만 제공합니다. 입력 소스가 비어 있으면 아무것도 넘겨주지 않고, 규칙이 절대 성립하지 않으면 유효한 윈도도 생성되지 않습니다.
하지만 여전히 문제가 하나 남아 있습니다. 호출하는 쪽은 이 yield들로 무엇을 할까요? 여기서는 map이나 select를 그대로 쓸 수 없습니다. 그런 메서드들은 반복 사이에 윈도를 붙잡고 있어야 하는데, 방금 윈도가 가변 객체이므로 보관할 수 없다고 확인했기 때문입니다. 참조를 붙들지 않은 채 각 yield를 즉시 소비하고 결과로 접어 넣는 무언가가 필요합니다.
바로 그 지점에 빌더가 들어옵니다. 순회를 즉시 실행하는 대신, max_window는 규칙을 기억만 하는 빌더 객체를 반환하고 아직 반복은 시작하지 않습니다. 실제로 순회를 시작하는 것은 터미널 메서드(max_by, first, each_window)이며, 이것이 여러분의 블록을 iterate_windows에 넘겨주면서 실행을 시작합니다:
module Rivulet
class WindowBuilder
def initialize(stream, rule:)
@stream, @rule = stream, rule
end
# 윈도를 하나의 최선의 점수로 접는다.
# 유지되는 것은 점수뿐이며, 윈도 자체는 절대 유지되지 않는다.
def max_by(&block)
best = nil
@stream.iterate_windows(rule: @rule) do |w|
score = block.call(w)
best = score if best.nil? || score > best
end
best
end
# 각 유효한 윈도 위치에서 nil이 아닌 결과를 수집한다.
def each_window(&block)
results = []
@stream.iterate_windows(rule: @rule) do |w|
v = block.call(w)
results << v if v
end
results
end
# nil이 아닌 첫 결과를 반환하고 순회를 멈춘다.
def first(&block)
result = nil
@stream.iterate_windows(rule: @rule) do |w|
result = block.call(w)
break if result
end
result
end
end
class Stream
# max_window는 결과가 아니라 빌더를 반환한다.
# 순회는 터미널 메서드를 호출할 때 일어난다.
def max_window(&rule) = WindowBuilder.new(self, rule: rule)
# 고정 크기 윈도는 블록과 함께 즉시 실행된다(filter-map 의미론).
def windows(size, &block)
results = []
window = new_window
@source.each do |item|
window.add(item)
window.evict while window.size > size
next unless window.size == size
v = block.call(window)
results << v if v
end
results
end
end
end
max_by는 진행하면서 윈도를 최선의 점수 하나로 접습니다. each_window는 nil이 아닌 결과를 모읍니다(filter-map 의미론). first는 답을 얻는 순간 멈춥니다. 이 셋 모두 블록이 반환된 뒤 윈도를 붙잡아 두지 않습니다. 여러분의 블록이 그 안에서 뽑아낸 점수 만 유지할 뿐이고, 그것은 불변 숫자입니다. 아무도 윈도를 붙들고 있지 않으니 윈도는 계속 변이되어도 됩니다.
이것은 의식적인 선택입니다. 내부적으로 우리는 Enumerable이나 Enumerator를 사용하지 않습니다. 객체들의 지연 스트림 위에서 메서드를 체이닝하지도 않습니다. 이것은 의도적인 결정입니다. 내부는 덜 “Ruby답게” 만들어 두어, 호출자가 실제로 만지는 표면이 더 Ruby답게 느껴질 수 있도록 하기 위해서입니다. 사용자는 max_window { rule }.max_by { question }를 쓰고, Enumerable이 가르쳐 준 것과 같은 관심사의 분리(무엇을 순회할지, 각 원소마다 무엇을 할지)를 얻습니다. 동시에 누구도 원하지 않은 프로토콜을 만족시키기 위해서만 존재하는 중간 객체의 비용은 치르지 않습니다.
마지막 조각은 특화입니다. SumWindow는 실행 중 총합을 유지합니다. CountWindow는 빈도 해시를 유지합니다. 각 스트림 하위 클래스는 어떤 윈도를 쓸지 선택합니다:
module Rivulet
# 실행 중 합계를 추적한다. 어느 시점에서든 sum이나 average를 묻는 것은 O(1).
class SumWindow < BaseWindow
def initialize = (super; @sum = 0)
def add(item) = (@sum += item; super)
def evict = (item = super; @sum -= item if item; item)
def sum = @sum
def average = empty? ? nil : @sum.fdiv(size)
end
# 항목 빈도를 추적한다. 반복 여부나 서로 다른 항목 수 확인은 O(1).
class CountWindow < BaseWindow
def initialize = (super; @counts = Hash.new(0))
def add(item) = (@counts[item] += 1; super)
def evict
item = super
if item
@counts[item] -= 1
@counts.delete(item) if @counts[item].zero?
end
item
end
def repeats? = @counts.any? { |_, n| n > 1 }
def distinct = @counts.size
end
class SumStream < Stream
private def new_window = SumWindow.new
end
class CountStream < Stream
private def new_window = CountWindow.new
end
end
새로운 윈도 타입을 추가하는 일은 add, evict, 그리고 그 상태 종류에 맞는 질의 메서드들을 갖춘 클래스 하나를 만드는 일입니다. 스트림과 빌더는 전혀 바뀌지 않습니다.
우리가 관심 있는 상태의 종류를 이름으로 드러내는 진입점 뒤에 이 장치를 숨깁니다:
module Rivulet
def self.sum(source) = SumStream.new(source)
def self.count(source) = CountStream.new(source)
end
SumStream은 실행 중 총합을 추적합니다. CountStream은 항목 빈도를 추적합니다. 호출자는 윈도 클래스를 결코 보지 못하고, 직접 만들지도 않으며, 붙들고 있지도 않습니다. 그 모든 것은 내부 기계 장치입니다.
그래서 이 모든 이야기의 출발점이었던 배치 문제, “예산 안에 들어가는 가장 큰 배치는 무엇인가?”는 이렇게 됩니다:
Rivulet.sum(records).max_window { |w| w.sum <= max_bytes }.max_by { |w| w.size }
이동 평균은요?
Rivulet.sum(latencies).windows(3) { |w| w.average }
가장 긴 비반복 구간은요?
Rivulet.count(events).max_window { |w| !w.repeats? }.max_by { |w| w.size }
이 셋을 소리 내어 읽어 보세요. 여러분이 쓰는 것은 규칙뿐입니다. 윈도 타입이 어떤 상태를 유지할지 결정하고, 규칙이 무엇을 유효한 윈도로 만들지 결정하며, 터미널이 지나가는 각 유효 윈도에 무엇을 할지 결정합니다. 세 관심사는 모두 분리되어 있고, 모두 이름이 붙어 있으며, 루프는 사라졌습니다. 제게는 이것이 다시 Ruby처럼 느껴지기 시작합니다.
이것이 얼마나 멀리 뻗어 나가는지 감을 드리기 위해, 반복 문자가 없는 가장 긴 부분 문자열(LeetCode 3)은 이렇게 됩니다:
Rivulet.count(s.chars).max_window { |w| !w.repeats? }.max_by { |w| w.size } || 0
같은 형태, 다른 규칙입니다.
앞서의 요청 속도 제한과 급증 감지 예시는 여기서 도출한 것보다 더 많은 기능이 필요합니다(시간 기반 축출, 가장 작은 만족 윈도를 찾는 min_window). gem은 둘 다 처리하지만, 핵심 통찰은 같습니다. grow-shrink-yield 루프를 손에 넣고 나면, 새로운 문제는 다른 윈도 타입 위에 다른 규칙을 얹는 일일 뿐입니다.
숫자 20만 개의 목록에서 “예산 안에 들어가는 가장 큰 윈도는 무엇인가”를 답하기 위해, 스냅샷을 내보내는 접근은 60만 개가 넘는 객체를 할당합니다. 빌더 접근은 약 670개를 할당합니다. gem은 항목 배열 자체를 완전히 제거해서 40개 미만으로 더 최적화합니다. 손으로 작성한 루프와 답은 같습니다. 빌더는 속도도 약 두 배 조금 넘게 빨랐고, 메모리 이야기는 어떤 경우에도 유지됩니다. 이것이 바로 추가 공간 O(n)과 O(1)의 차이이며, 우리가 출발했던 손수 만든 포인터 버전과 현재 버전 사이의 차이입니다.
윈도는 결코 순회 밖으로 나가지 않습니다. 제자리에서 변이되고, 블록은 필요한 것만 읽고, 다음 단계가 그것을 덮어씁니다. 형태만 보면 이것은 바로 그 투 포인터 루프와 같고, 단지 장부 정리가 숨겨졌고 규칙이 눈에 보이는 자리로 빠져나왔을 뿐입니다. 우리는 가벼운 루프를 되찾았고, 문장도 함께 지켰습니다.
여기에는 이름 붙일 만한 더 넓은 교훈이 있습니다. 때로는 사용자에게 가장 Ruby답게 느껴지는 것을 주기 위해서, 그 아래에서는 덜 Ruby다운 일을 해야 할 때가 있습니다. 가변 상태, 수동 반복, 조합 가능한 객체를 반환하는 대신 블록에 yield하기. 이것이 반드시 타협인 것은 아닙니다. 60만 객체 버전은 내부적으로는 더 “Ruby다웠습니다”(Enumerator! Enumerable! 스냅샷!). 하지만 호출자가 신경 쓰는 모든 차원, 즉 메모리, 속도, 어디서 무엇이 할당되는지 이해해야 하는 인지 부담 측면에서 더 큰 비용을 치렀습니다. 사용하기에 Ruby처럼 느껴지는 버전은 내부에서 무슨 일이 일어날지에 대해 의도적이고 실용적인 선택을 한 버전입니다. 좋은 추상화는 자신이 보여주는 패턴과 같은 패턴으로 반드시 만들어져야 할 의무가 없습니다. 표준 라이브러리도 곳곳에서 같은 거래를 합니다. Array#sort는 C이고, each_cons도 C이며, Hash도 C입니다. 그것들은 호출자에게 가장 이로운 구현 위에 Ruby다운 표면을 제시하고, 누구도 거기에 이의를 제기하지 않습니다.
저는 이것을 Rivulet이라고 부르고 있습니다. “조금의 상태를 싣고 흐르는 작은 시냇물”이라는 뜻이 제법 잘 맞기 때문입니다. 하지만 이름은 처음이 아니라 마지막에 왔고, 바로 그 점이 중요합니다. 우리는 이름에서 시작하지 않았습니다. 못생긴 루프에서 시작했고, 적절한 것들에 적절한 순서로 짜증이 났고, 마침내 이름 붙일 가치가 있는 무언가가 생겼을 때에야 이름이 나타났습니다.
gem은 여기서 우리가 도출한 것보다 이미 더 멀리 나아가 있습니다. Rivulet.sum(records, &:bytesize)는 객체 자체가 아니라 각 객체의 어떤 속성을 합산하는데, 이것이 바로 배치 문제가 실제 운영 환경에서 필요로 하는 것입니다. min_window는 목표를 만족하는 가장 작은 윈도를 찾습니다(앞서의 “오류 다섯 개를 포함하는 가장 짧은 구간”). MinMaxWindow는 단조 덱을 통해 다시 훑지 않고도 롤링 최소/최대를 추적합니다. covers?를 가진 CountWindow는 부분 문자열 매칭 문제를 처리합니다. 이 어떤 것도 새로운 순회 로직을 요구하지 않았습니다. 모두 같은 grow-shrink 루프에 다른 상태가 함께 실려 가고, 다른 터미널이 다른 질문을 던질 뿐입니다.
제가 계속 저항하고 싶은 것은 이것을 그래프도 하고 비동기도 하고 그 밖의 모든 것도 하는 범용 스트림 처리 엔진으로 만들자는 유혹입니다. 이 도구의 가치는 언제나 작게 남는 데 있었습니다. 한 번 앉아서 이해할 수 있을 만큼 작고, 소스를 읽지 않고도 믿을 수 있을 만큼 작고, 추상화 비용이 대체하려는 코드보다 더 적을 만큼 작게요.
결국 이게 전부입니다. 표준 라이브러리의 메서드가 떨어지는 순간 우리는 바로 수동 루프를 집어 들었고, 알고 보니 눈앞의 지저분함은 하나의 문제가 아니라 우리가 수년 동안 이름도 붙이지 않은 채 손으로 계속 다시 만들고 있던 하나의 형태였습니다. 일단 이름을 붙이고, 그것이 루프를 안쪽에 숨긴 제대로 된 객체가 되게 하면, 자질구레한 버전은 사라지고 여러분이 정말 신경 쓰던 규칙만 남습니다. 이것은 오래전에 map과 select가 우리를 위해 해준 바로 그 거래이고, 저는 지금 그 거래를 멈출 이유를 보지 못하겠습니다.
윈도는 제가 이름 붙이고 싶었던 첫 번째 형태였습니다. 다음 글에서는 또 다른 형태를 다룹니다.