Bảng tra độ phức tạp
Tham chiếu nhanh độ phức tạp thời gian và không gian cho các thao tác chính của mỗi pattern. Dùng nó để so sánh đánh đổi trước khi chọn pattern.
Cách đọc bảng
- n = số phần tử / item
- k = độ dài key (cho cấu trúc đánh key bằng chuỗi)
- m = số hàm hash (Bloom filter)
- L = số tầng (skip list, LSM tree)
- Chi phí phân bổ trung bình ghi (phân bổ)
Cấu trúc dữ liệu
| Pattern | Thêm | Tra | Xoá | Bộ nhớ | Ghi chú |
|---|---|---|---|---|---|
| Bitmask | O(1) | O(1) | O(1) | O(1) | Kích thước cố định; giới hạn theo độ rộng word (32/64 flag) |
| Ring Buffer | O(1) | O(1) | O(1) | O(n) | Sức chứa cố định; ghi đè lên cái cũ nhất khi đầy |
| Tagged Union | — | O(1) | — | O(variant lớn nhất) | Dispatch theo tag; không cấp phát động |
| Min Heap | O(log n) | O(1) peek | O(log n) | O(n) | Truy cập min O(1); dùng cho hàng đợi ưu tiên |
| Trie | O(k) | O(k) | O(k) | O(n × k) | Không phụ thuộc tổng số entry; truy vấn prefix O(k + kết quả) |
| Bloom Filter | O(m) | O(m) | ✗ | O(n) | Theo xác suất; có thể có dương tính giả, không có âm tính giả |
| LRU Cache | O(1) | O(1) | O(1) | O(n) | Hash map + linked list hai chiều |
| Skip List | O(log n) trung bình | O(log n) trung bình | O(log n) trung bình | O(n) | Cân bằng theo xác suất; hỗ trợ truy vấn khoảng |
| B+ Tree | O(log n) | O(log n) | O(log n) | O(n) | Tối ưu cho đĩa; fanout cao giảm thiểu I/O |
| Merkle Tree | O(log n) | O(log n) | O(log n) | O(n) | Bằng chứng xác minh O(log n) |
| Merge Iterator | — | O(log k) next | — | O(k) | k = số luồng; gộp dựa trên heap |
Concurrency
| Pattern | Thao tác chính | Chi phí | Bộ nhớ | Ghi chú |
|---|---|---|---|---|
| Semaphore | acquire / release | O(1) | O(1) | Dùng bộ đếm; có thể chặn khi tranh chấp |
| Double Buffering | swap | O(1) | O(2n) | Đổi con trỏ; không copy |
| Event Loop | enqueue / dequeue | O(1) | O(queue) | Đơn luồng; ghép kênh I/O |
| Backpressure | signal / check | O(1) | O(1) | Kiểm soát luồng; thường ghép vào channel có sẵn |
| Copy-on-Write | đọc | O(1) | O(n) mỗi snapshot | Ghi kích hoạt clone O(n); đọc không bao giờ chặn |
| Cooperative Scheduling | yield | O(1) | O(số task) | Cần điểm yield tự nguyện |
| MVCC | đọc / ghi | O(1) + GC | O(n × phiên bản) | Đọc không bao giờ chặn; chi phí GC phân bổ |
| Work Stealing | push / steal | O(1) phân bổ | O(số task) | Deque lock-free; theo dõi cache-line |
| Actor Model | gửi thông điệp | O(1) | O(số actor × mailbox) | Trạng thái cô lập; không bộ nhớ chung |
| Logical Clock | tick / merge | O(1) Lamport, O(n) Vector | O(1) / O(n) | Vector clock tăng theo số node |
Hệ thống
| Pattern | Thao tác chính | Chi phí | Bộ nhớ | Ghi chú |
|---|---|---|---|---|
| State Machine | chuyển trạng thái | O(1) | O(số trạng thái) | Dispatch thời gian hằng; trạng thái rõ ràng |
| Circuit Breaker | call / check | O(1) | O(1) | Bộ đếm + timer; 3 trạng thái |
| Rate Limiter | allow? | O(1) | O(1) mỗi limiter | Token bucket hoặc cửa sổ trượt |
| Retry with Backoff | retry | O(số lần thử) tổng | O(1) | Delay theo cấp số nhân + jitter |
| Batch Processing | flush | O(batch) | O(batch) | Phân bổ chi phí trên mỗi item |
| Middleware Chain | execute | O(số middleware) | O(số middleware) | Pipeline tuyến tính; mỗi handler O(1) |
| Registry | register / lookup | O(1) hash | O(n) | Service locator đánh key bằng chuỗi |
| Dirty Flag | check / mark | O(1) | O(1) | Cờ boolean; bỏ qua nếu không đổi |
| Dependency Graph | sắp xếp topo | O(V + E) | O(V + E) | DAG; phát hiện chu trình |
| Consistent Hashing | tra node | O(log n) | O(n × vnode) | Tìm nhị phân trên vòng; xáo trộn tối thiểu |
| Write-Ahead Log | append | O(1) phân bổ | O(log size) | Ghi tuần tự; fsync để bền vững |
| Checkpointing | snapshot | O(kích thước state) | O(kích thước state) | Định kỳ; cắt bớt WAL |
| LSM Tree | write / read | O(1) write, O(L) read | O(n) | Tối ưu cho ghi; compaction ở background |
Bộ nhớ
| Pattern | Cấp phát | Giải phóng | Tra | Bộ nhớ | Ghi chú |
|---|---|---|---|---|---|
| Object Pool | O(1) | O(1) | — | O(kích thước pool) | Cấp phát trước; tránh áp lực GC |
| Flyweight | — | — | O(1) | O(số instance duy nhất) | Chia sẻ các instance giống nhau |
| Arena Allocator | O(1) bump | O(1) hàng loạt | — | O(kích thước arena) | Bump pointer; giải phóng tất cả một lần |
| Free List | O(1) | O(1) | — | O(n) | Linked list của các slot đã giải phóng |
| Copy-on-Write | O(1) chia sẻ | O(n) khi ghi | O(1) | O(n) mỗi snapshot | Hoãn copy |
| Reference Counting | O(1) clone | O(1) drop | — | O(1) mỗi ref | Xác định; không tự xử lý chu trình |
| Tombstone | — | O(1) đánh dấu | O(1) | O(n + đã xoá) | Xoá mềm; dồn nén sau |
| Interning | O(k) lần đầu, O(1) các lần sau | — | O(1) | O(số duy nhất × k) | Khử trùng lặp dựa trên hash; so sánh bằng con trỏ |
Hành vi
| Pattern | Thao tác chính | Chi phí | Bộ nhớ | Ghi chú |
|---|---|---|---|---|
| Observer | notify | O(số subscriber) | O(số subscriber) | Fan-out; thứ tự có thể khác |
| Iterator | next | O(1) mỗi bước | O(1) | Đánh giá lười; kiểu pull |
| Diff / Patch | diff | O(n × m) Myers | O(n + m) | Khoảng cách chỉnh sửa tối thiểu |
| Vtable | dispatch | O(1) | O(số method) | Gián tiếp qua con trỏ; phân giải tĩnh |
| Visitor | visit | O(số node) | O(độ sâu cây) | Double dispatch; duyệt + thao tác |
Tóm tắt đánh đổi chính
| Nếu bạn cần... | Chọn | Đánh đổi |
|---|---|---|
| Tra O(1) + loại bỏ O(1) | LRU Cache | Thêm bộ nhớ cho linked list hai chiều |
| Ghi O(1) ở quy mô lớn | LSM Tree | Read amplification (nhiều tầng) |
| Kiểm tra thành viên O(1) | Bloom Filter | Dương tính giả (không âm tính giả) |
| Cấp phát O(1) | Arena hoặc Free List | Không giải phóng từng phần (arena) hoặc phân mảnh (free list) |
| Truy cập sắp xếp O(log n) | Skip List hoặc B+ Tree | Skip list đơn giản hơn, B+ tree tối ưu cho đĩa |
| Đọc không copy | Copy-on-Write hoặc MVCC | Write amplification khi sửa đổi |
| Rehash tối thiểu khi mở rộng | Consistent Hashing | Virtual node thêm chi phí bộ nhớ |