Cấu trúc dữ liệu: đo thật

Đo chi phí thật của các cấu trúc dữ liệu bằng C/C++ trong container Linux: cache locality, hằng số ẩn sau Big-O, va chạm băm, mọc lại vector, con trỏ nhảy vs mảng liền. Mỗi phần một phép đo thật, một lần đo hớ, một sơ đồ.

13/45 phần đã đăng Giải thuật
1 Mảng vs danh sách liên kết: duyệt Tưởng duyệt mảng và danh sách liên kết tốn như nhau vì cùng O(n). Đo ra: duyệt 20 triệu phần tử, mảng 0,24ns/phần tử còn linked list 104ns — chậm 442 lần, vì mỗi con trỏ next là một cache miss còn mảng thì prefetch. Big-O giấu hằng số. Đo thật. 03/09/2026 · 7 phút đọc 2 Mảng động (vector): chi phí mọc lại Tưởng mỗi push_back copy cả mảng nên vector chậm, hoặc grow-by-1 tiết kiệm RAM nên tốt. Đo ra: nhân đôi amortize xuống 2,57ns/push (O(1)) xây 20 triệu phần tử, còn grow-by-1 là O(N²) — chỉ 50 nghìn phần tử đã 1,25 tỷ copy, 3213ns/push. Đo thật. 03/09/2026 · 7 phút đọc 3 Chèn/xóa: mảng vs linked list Ai cũng thuộc 'linked list chèn/xóa O(1), mảng O(N)'. Đo ra: chèn ở đầu list nhanh hơn mảng 70.000 lần — nhưng chèn giữa THỰC TẾ (phải tìm vị trí trước) thì list chậm hơn mảng 16 lần, vì duyệt để tìm là cache miss mỗi bước. O(1) chỉ đúng khi đã cầm sẵn con trỏ. Đo thật. 03/09/2026 · 8 phút đọc 4 Bảng băm: hệ số tải và va chạm Ai cũng nói hash table là O(1). Đo ra: tra cứu O(1) chỉ đúng khi hệ số tải thấp — tải 0,25 tốn 1,17 probe (3,2ns), nhưng đẩy tải lên 0,99 thì probe trung bình nổ lên 43 và tra cứu chậm 10 lần. O(1) là trung bình có điều kiện, không phải bảo đảm. Đo thật. 03/09/2026 · 8 phút đọc 5 Bảng băm: hàm băm tốt vs xấu Phần 4 cho thấy tải cao giết hash table. Nhưng ngay ở CÙNG tải 0,70, đổi hàm băm tốt sang xấu làm probe trung bình nhảy từ 2,17 lên 358,9 — tra cứu chậm 23 lần. Băm hằng số thì thoái hóa hoàn toàn về O(n). Tải thấp là điều kiện cần, không đủ. Đo thật. 03/09/2026 · 8 phút đọc 6 Cây tìm kiếm nhị phân vs bảng băm O(1) < O(log n), nên hash luôn hơn cây? Đo ra: tra cứu điểm hash nhanh hơn cây đỏ-đen 32 lần (16ns vs 518ns). Nhưng range query — tìm mọi phần tử >= x theo thứ tự — cây làm trong 7,8µs còn hash phải sort lại toàn bộ, 54,2ms. Chọn theo loại truy vấn, không theo Big-O. Đo thật. 03/09/2026 · 8 phút đọc 7 Cây cân bằng vs suy biến BST tra cứu O(log n)? Chỉ khi cây cân bằng. Đo ra: chèn dữ liệu ĐÃ sắp xếp vào một BST thường làm cây lệch thành chuỗi cao đúng bằng N (50.000), tra cứu chậm hơn std::map 461 lần và xây cây chậm 594 lần. Dữ liệu sắp xếp là worst case, không phải best. Đo thật. 03/09/2026 · 8 phút đọc 8 B-tree: vì sao CSDL dùng Cây nhị phân và B-tree đều O(log n) — vậy sao mọi cơ sở dữ liệu dùng B-tree? Đo ra: tra cứu 4 triệu khóa, cây nhị phân đi 22 tầng (887ns), B-tree fanout 64 chỉ 4 tầng (153ns) — nhanh 5,8 lần. Mỗi tầng là một lần chạm bộ nhớ (hay một lần đọc đĩa), nên ít tầng thắng. Cùng O(log n), khác cơ số log. Đo thật. 03/09/2026 · 8 phút đọc 9 Heap (hàng đợi ưu tiên): chi phí thao tác Xây một heap từ n phần tử — push từng cái cũng như make_heap chứ gì? Đo ra: n lần push là O(n log n), còn heapify bottom-up là O(n); với dữ liệu xấu nhất heapify nhanh hơn 6,3 lần. Và heap không cần cây con trỏ — nó là một mảng liền mạch. Đo thật. 03/09/2026 · 8 phút đọc 10 Ngăn xếp vs hàng đợi: mảng vs con trỏ Stack và queue đều O(1) push/pop dù cài bằng mảng hay linked list — chọn cách nào cũng vậy? Đo ra: stack bằng mảng 0,3ns/thao tác, bằng linked list 4,0ns — chậm 13 lần, vì linked list trả malloc+free (5,5ns) mỗi thao tác. Cùng O(1), khác hằng số chục lần. Đo thật. 03/09/2026 · 7 phút đọc 11 Tìm kiếm nhị phân vs tuyến tính O(log n) < O(n), nên tìm nhị phân luôn thắng tuyến tính? Đo ra: với mảng nhỏ, tuyến tính NHANH HƠN — điểm giao ở N≈32; dưới đó quét tuần tự thắng nhờ cache và không branch misprediction. Big-O là hành vi tiệm cận (N lớn); N nhỏ thì hằng số và phần cứng quyết định. Đo thật. 03/09/2026 · 7 phút đọc 12 Structure-of-arrays vs array-of-structures Bố cục struct chỉ là cách tổ chức, không đổi tốc độ? Đo ra: duyệt một trường trên 15 triệu phần tử, SoA nhanh hơn AoS 3,6 lần vì cache line không bị lãng phí. Nhưng truy cập ngẫu nhiên mọi trường thì AoS nhanh gấp đôi. Bố cục dữ liệu đổi tốc độ nhiều lần — chọn theo mẫu truy cập. Đo thật. 03/09/2026 · 8 phút đọc 13 Cache line và false sharing Hai luồng, mỗi luồng tăng bộ đếm riêng — độc lập hoàn toàn, phải chạy song song? Đo ra: nếu hai bộ đếm nằm cùng một cache line, chúng chậm hơn 3,8–4,9 lần vì dòng cache ping-pong giữa hai lõi (false sharing). Tách sang cache line riêng (padding) khắc phục. Không chia sẻ dữ liệu vẫn bị phạt vì chung dòng. Đo thật. 03/09/2026 · 8 phút đọc

Còn 32 phần nữa sẽ lần lượt được đăng.