Online Algorithms and Competitive Ratio TODO
Concept
An online algorithm never gets to see the whole input in advance and has to make irrevocable decisions as each request arrives. Its performance is measured not in absolute cost but in competitive ratio, defined as the worst case over all input sequences of (online algorithm's cost) / (offline optimal's cost, knowing the whole input). For cache replacement (paging), with a cache of size k, both LRU and FIFO are k-competitive, and k is also the lower bound on the competitive ratio for any deterministic algorithm — which makes LRU optimal in that class. Allowing randomization, as in the marking algorithm, can lower the expected competitive ratio to logarithmic scale, because it prevents an adversarial input from predicting the algorithm's next move. Problems like ski rental, which are about deciding "when to buy," have a 2-competitive algorithm, and real-time selection problems in the secretary-problem family achieve constant-factor performance guarantees using randomized threshold rules.
Code that has to decide now, without knowing the future — caches, connection pools, real-time bidding, order matching — is everywhere, and average-case intuition alone falls apart under adversarial traffic. Competitive ratio is the one language that quantifies that worst case.
Code & Formula
# Day 15: 온라인 알고리즘과 경쟁비 — 캐시 교체(LRU/FIFO) 대 오프라인 최적(Belady)
# 미래를 모른 채 결정하는 온라인 알고리즘의 비용을 오프라인 최적과 비교해 경쟁비를 측정한다.
def lru_misses(seq, k):
cache, misses = [], 0
for x in seq:
if x in cache:
cache.remove(x); cache.append(x)
else:
misses += 1
if len(cache) >= k:
cache.pop(0)
cache.append(x)
return misses
def fifo_misses(seq, k):
cache, order, misses = set(), [], 0
for x in seq:
if x not in cache:
misses += 1
if len(cache) >= k:
oldest = order.pop(0)
cache.remove(oldest)
cache.add(x); order.append(x)
return misses
def belady_misses(seq, k):
cache, misses = [], 0
for i, x in enumerate(seq):
if x in cache:
continue
misses += 1
if len(cache) >= k:
future = seq[i + 1:]
farthest = max(cache, key=lambda c: future.index(c) if c in future else float("inf"))
cache.remove(farthest)
cache.append(x)
return misses
k = 4
seq = [1, 2, 3, 4, 1, 2, 5, 1, 2, 3, 4, 5] * 3 # LRU에 불리하도록 순환 접근 패턴
lru, fifo, opt = lru_misses(seq, k), fifo_misses(seq, k), belady_misses(seq, k)
print(f"캐시 크기 k={k}, 요청 {len(seq)}건")
print(f"LRU miss = {lru}, FIFO miss = {fifo}, 오프라인 최적(Belady) miss = {opt}")
print(f"LRU 경쟁비 ≈ {lru/opt:.2f} (이론 상한 k={k})")
print(f"FIFO 경쟁비 ≈ {fifo/opt:.2f}")
docs/code/algorithms/algorithms-15.py
Exercise
Implement LRU, FIFO, and random replacement under the same interface, then construct a cyclic access sequence sized to cache size k that's specifically designed to hit LRU's worst case, and measure whether the cost ratio against the offline optimum (Belady's algorithm) actually approaches k.
Practical Connection
A prediction-market order book that has to decide match-or-reject the instant each order arrives, or an RPC response cache exposed to an adversarial query pattern, are both exactly online decision problems.
Where it lands in Jayverse
- Verex: measure the CLOB's competitive ratio against an offline-optimal replay of the same order sequence. The same way LRU is graded against Belady's algorithm, replay a day's order flow through an offline-optimal matcher and compare — that turns "did the matcher do okay" into a number instead of an impression.
- Rabbit/Devnet: choose an explicit eviction policy for the RPC response cache and test it adversarially. Pick LRU, FIFO, or random deliberately, then construct an access sequence sized to the cache specifically to hit its worst case, since average-case traffic alone won't reveal it.
Key expressions
| Expression | 뜻 · 쓰이는 자리 |
|---|---|
| irrevocable | 돌이킬 수 없는 · 온라인 알고리즘은 매 요청마다 되돌릴 수 없는 결정을 내려야 함 · "has to make irrevocable decisions as each request arrives" |
| worst case | 최악의 경우 · 경쟁비를 정의할 때 기준이 되는 시나리오 · "the worst case over all input sequences" |
| lower bound | 하한(값) · 결정론적 알고리즘이 도달할 수 있는 최선의 한계 · "k is also the lower bound on the competitive ratio" |
| fall apart | 무너지다, 깨지다 · 평균적 직관이 최악의 입력 앞에서 통하지 않음 · "average-case intuition alone falls apart under adversarial traffic" |
| adversarial | 적대적인, 일부러 불리하게 짠 · 최악의 사례를 만들려는 입력을 가리킴 · "falls apart under adversarial traffic" |
| prevent ~ from ~ing | ~가 ~하지 못하게 막다 · 무작위성이 상대가 다음 수를 예측 못 하게 막음 · "prevents an adversarial input from predicting the algorithm's next move" |
| quantify | 수치화하다, 정량적으로 나타내다 · 경쟁비가 최악의 경우를 수치로 표현하는 유일한 언어라는 뜻 · "the one language that quantifies that worst case" |
| ski rental problem | 스키 대여 문제(ski rental problem) · '언제 살 것인가'를 결정하는 고전적 온라인 최적화 문제, 2-경쟁 알고리즘이 존재. "Problems like ski rental, which are about deciding when to buy" |
| secretary problem | 비서 문제(secretary problem) · 무작위 임계값 규칙으로 최적 후보를 실시간 선택하는 고전적 문제군. "real-time selection problems in the secretary-problem family" |
| Belady's algorithm | 벨레이디 알고리즘(Belady's algorithm) · 미래를 다 아는 상태에서 최적 캐시 교체를 계산하는 오프라인 기준 알고리즘. "the cost ratio against the offline optimum (Belady's algorithm)" |
If you study this on a given day, add a note link and a ✅ to this line in the source curriculum (docs/knowledge/dev-100-curriculum.md) and this spot will lead straight to the note body. You can also write directly on this page — but regenerating overwrites it, so it's safer to keep anything you want to save as markdown under docs/algorithms/.