[Review] A Practical Checklist for Algorithm Selection TODO

Algorithms · Day 19 / 100 · A. Advanced Algorithms & Data Structures (Day 1-19)

Concept

Algorithm choice isn't determined by asymptotic complexity alone — it depends on the combination of input size, data distribution, access pattern, memory hierarchy, update frequency, and worst-case versus average-case requirements. For example, when n is small, an O(n^2) algorithm with small constants beats O(n log n); when data is nearly sorted, an adaptive sort wins; and array-based structures with good cache locality often beat pointer-chasing structures in practice. If a workload is read-heavy, a static index is best; if write-heavy, a log-structured or amortization-friendly structure wins. If tail latency (p99) matters, avoid amortized algorithms that look good on average but are bad in the worst case. In the end, a checklist is a procedure: first identify which constraint dominates, then narrow to candidates that fit that constraint, and confirm with measurement.

Much of real-world performance trouble comes not from a wrong algorithm but from misidentifying the constraint, and that cost only shows up after the code has already hardened.

Code & Formula

# [복습] 알고리즘 선택 실전 기준표 — 입력 크기별 정렬 비용과 접근 패턴(배열 vs 연결리스트)의 실측 차이를 비교한다.

import time
import random

def insertion_sort(a):
    a = a[:]
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

def timeit(fn, *args, repeat=1):
    start = time.perf_counter()
    for _ in range(repeat):
        fn(*args)
    return (time.perf_counter() - start) / repeat

random.seed(42)
small = [random.randint(0, 100) for _ in range(10)]
large = [random.randint(0, 100) for _ in range(2000)]

t_ins_small = timeit(insertion_sort, small, repeat=2000)
t_sorted_small = timeit(sorted, small, repeat=2000)
t_ins_large = timeit(insertion_sort, large, repeat=5)
t_sorted_large = timeit(sorted, large, repeat=5)

# 배열 순회(지역성 좋음) vs 연결 리스트류 포인터 추적(지역성 나쁨) 비교
class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

arr = list(range(100_000))
head = None
for v in reversed(arr):
    head = Node(v, head)

def sum_linked(n):
    total = 0
    while n:
        total += n.value
        n = n.next
    return total

t_array = timeit(sum, arr, repeat=20)
t_linked = timeit(sum_linked, head, repeat=20)

print(f"n=10:   insertion_sort={t_ins_small * 1e6:.2f}us  builtin(Timsort)={t_sorted_small * 1e6:.2f}us")
print(f"n=2000: insertion_sort={t_ins_large * 1e3:.2f}ms  builtin(Timsort)={t_sorted_large * 1e3:.2f}ms")
print(f"n=100000 순회: array={t_array * 1e3:.3f}ms  linked-list={t_linked * 1e3:.3f}ms "
      f"(연결리스트가 {t_linked / t_array:.1f}배 — 캐시 지역성 차이)")

docs/code/algorithms/algorithms-19.py

Exercise

Pick a hot path you wrote recently, tabulate its input size, read/write ratio, and tail-latency requirements, then fill in the same columns for your current data structure and two alternatives to compare them on equal footing.

Practical Connection

On-chain code has one more axis because gas is a direct cost of complexity, while off-chain indexers and matching engines are often dominated by tail latency and update frequency.

Where it lands in Jayverse

• Verex: apply the checklist to the CLOB's order-book structure. Since it's write-heavy and p99-latency sensitive, prefer a log-structured/amortization-friendly book over a naive sorted array, and confirm the choice with measurement rather than asymptotics alone.
• Rabbit/Wallet: for session-key and mandate-check contract code, gas is the dominant constraint, so pick the structure with the smallest constant/storage-slot cost even when it's asymptotically worse, and document why in the contract.
• gitboard: for read-heavy dashboard queries (service status, latest block), prefer a static/cached index over recomputation, paying update cost per event instead of per read.

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/.

한국어

[복습] 알고리즘 선택의 실전 기준표 TODO

Algorithms · Day 19 / 100 · A. 고급 알고리즘·자료구조 (Day 1–19)

개념

알고리즘 선택은 점근 복잡도만으로 결정되지 않고, 입력 규모, 데이터 분포, 접근 패턴, 메모리 계층, 갱신 빈도, 최악 대 평균 요구사항이라는 축들의 조합으로 결정된다. 예를 들어 n이 작으면 상수가 작은 O(n^2)가 O(n log n)을 이기고, 데이터가 거의 정렬돼 있으면 적응적 정렬이 유리하며, 캐시 지역성이 좋은 배열 기반 구조가 포인터 추적 구조보다 실측에서 앞서는 일이 흔하다. 읽기 위주면 정적 인덱스, 쓰기 위주면 로그 구조나 상환 분석이 좋은 구조를 고른다. 지연시간 꼬리(p99)가 중요하면 평균이 좋아도 최악이 나쁜 상환 알고리즘은 피해야 한다. 결국 기준표란 "어떤 제약이 지배적인가"를 먼저 식별하고, 그 제약에 맞는 후보군으로 좁힌 뒤 실측으로 확정하는 절차이다.

실무 성능 사고의 상당수는 잘못된 알고리즘이 아니라 제약을 잘못 짚은 선택에서 나오고, 그 비용은 코드가 굳은 뒤에 드러난다.

코드 · 수식

# [복습] 알고리즘 선택 실전 기준표 — 입력 크기별 정렬 비용과 접근 패턴(배열 vs 연결리스트)의 실측 차이를 비교한다.

import time
import random

def insertion_sort(a):
    a = a[:]
    for i in range(1, len(a)):
        key = a[i]
        j = i - 1
        while j >= 0 and a[j] > key:
            a[j + 1] = a[j]
            j -= 1
        a[j + 1] = key
    return a

def timeit(fn, *args, repeat=1):
    start = time.perf_counter()
    for _ in range(repeat):
        fn(*args)
    return (time.perf_counter() - start) / repeat

random.seed(42)
small = [random.randint(0, 100) for _ in range(10)]
large = [random.randint(0, 100) for _ in range(2000)]

t_ins_small = timeit(insertion_sort, small, repeat=2000)
t_sorted_small = timeit(sorted, small, repeat=2000)
t_ins_large = timeit(insertion_sort, large, repeat=5)
t_sorted_large = timeit(sorted, large, repeat=5)

# 배열 순회(지역성 좋음) vs 연결 리스트류 포인터 추적(지역성 나쁨) 비교
class Node:
    __slots__ = ("value", "next")
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

arr = list(range(100_000))
head = None
for v in reversed(arr):
    head = Node(v, head)

def sum_linked(n):
    total = 0
    while n:
        total += n.value
        n = n.next
    return total

t_array = timeit(sum, arr, repeat=20)
t_linked = timeit(sum_linked, head, repeat=20)

print(f"n=10:   insertion_sort={t_ins_small * 1e6:.2f}us  builtin(Timsort)={t_sorted_small * 1e6:.2f}us")
print(f"n=2000: insertion_sort={t_ins_large * 1e3:.2f}ms  builtin(Timsort)={t_sorted_large * 1e3:.2f}ms")
print(f"n=100000 순회: array={t_array * 1e3:.3f}ms  linked-list={t_linked * 1e3:.3f}ms "
      f"(연결리스트가 {t_linked / t_array:.1f}배 — 캐시 지역성 차이)")

docs/code/algorithms/algorithms-19.py

연습

최근 직접 짠 핫 경로 하나를 골라 입력 규모·읽기쓰기 비율·꼬리지연 요구를 표로 적고, 현재 자료구조와 대안 두 개를 같은 기준으로 채워 비교해 보기.

실무 · Verex 연결

온체인 코드는 가스가 곧 복잡도 비용이라 축이 하나 더 붙고, 오프체인 인덱서·매칭 엔진은 꼬리지연과 갱신 빈도가 지배 제약이 되는 경우가 많다.

Jayverse에서의 위치

• Verex: CLOB의 오더북 구조에 체크리스트를 적용한다. 쓰기가 많고 p99 지연에 민감하므로, 단순 정렬 배열보다 로그 구조/상환 친화적 구조를 선호하고, 점근 복잡도만이 아니라 측정으로 그 선택을 확인한다.
• Rabbit/Wallet: 세션 키와 mandate 검사 컨트랙트 코드는 gas가 지배적 제약이므로, 점근적으로 더 나쁘더라도 상수/스토리지 슬롯 비용이 가장 작은 구조를 고르고 그 이유를 컨트랙트에 문서화한다.
• gitboard: 서비스 상태, 최신 블록 같은 읽기가 많은 대시보드 쿼리는 재계산 대신 정적/캐시된 인덱스를 선호하고, 읽기당이 아니라 이벤트당으로 갱신 비용을 지불한다.

공부한 날 원본 커리큘럼(docs/knowledge/dev-100-curriculum.md)의 이 줄에 노트 링크와 ✅ 를 붙이면, 이 자리는 노트 본문으로 바로 이어집니다. 노트 없이 이 페이지에 바로 적어도 됩니다 — 다만 다시 생성하면 덮어쓰이므로, 남길 글은 docs/algorithms/ 의 마크다운으로 쓰는 편이 안전합니다.