Mảng động — std::vector, ArrayList, list của Python — là cấu trúc dữ liệu bạn dùng nhiều nhất, và nó có một bí mật: mảng bên dưới cố định kích thước, nên khi bạn push_back mà nó đầy, nó phải cấp một buffer lớn hơn rồi copy toàn bộ dữ liệu cũ sang. Nghe như mỗi lần thêm phần tử phải copy cả mảng — chậm khủng khiếp? Hay nếu chỉ cấp thêm đúng một ô mỗi lần thì tiết kiệm bộ nhớ hơn? Cả hai suy nghĩ đều dẫn tới kết luận sai, và khác biệt là cả một bậc độ phức tạp. Tôi đo ba chiến lược mọc lại trong container gcc:13, và con số phân tách O(1) khỏi thảm họa O(N²).

Mảng động (vector): chi phí mọc lại

Ba cách mọc, và phép màu amortize

Khi mảng động đầy, nó cấp buffer mới, copy dữ liệu cũ sang, giải phóng buffer cũ. (Với std::vector, đây là copy thật — gọi copy/move constructor cho từng phần tử — không dùng được realloc mở rộng tại chỗ.) Buffer này nằm trên heap, và mỗi lần cấp lớn dần chính là kiểu heap mọc dần mà sê-ri hệ điều hành đã đo. Câu hỏi là: buffer mới lớn hơn bao nhiêu?

  • Nhân đôi (×2) — như std::vector: khi đầy, tăng capacity gấp đôi. Copy chỉ xảy ra khi đầy (log N lần cho N phần tử). Chìa khóa: tổng công của tất cả các lần copy là 1 + 2 + 4 + ... + N, một chuỗi hình học bằng khoảng 2N — không phải N mỗi lần. Nên dù có những lần copy lớn, trung bình mỗi push_back chỉ tốn O(1). Đây gọi là amortize (khấu hao): chi phí đắt của vài lần copy được chia đều cho tất cả các lần push.

  • Grow-by-1 (+1): khi đầy, chỉ cấp thêm đúng một ô. Nghe "tiết kiệm bộ nhớ" (không dự phòng thừa), nhưng: mỗi push đều làm mảng đầy, nên mỗi push copy cả mảng. Tổng công là 1 + 2 + 3 + ... + N = N²/2 — O(N²), thảm họa bậc hai.

  • Reserve: nếu biết trước N, cấp đủ ngay một lần — 0 lần mọc lại, nhanh nhất.

Tôi tự cài mảng động bằng malloc/memcpy để kiểm soát chiến lược, và đếm cả tổng số phần tử phải copy.

Đo: O(1) so với O(N²)

Xây mảng động bằng push (malloc buffer mới + memcpy khi mọc):
  NHÂN ĐÔI (×2)  N = 20.000.000 : 0,051 s | copy ~1,7N (33,5 triệu) | 2,57 ns/push (amortize O(1))
  RESERVE trước  N = 20.000.000 : 0,007 s | copy 0                  | 0,33 ns/push (0 mọc lại)
  GROW-BY-1 (+1) N =     50.000 : 0,161 s | copy ~N²/2 (1,25 TỶ!)  | 3.213 ns/push (O(N²))

Nhân đôi xây 20 triệu phần tử trong 0,051 giây — chỉ 2,57 ns mỗi push. Tổng số phần tử phải copy qua tất cả các lần mọc chỉ là ~33,5 triệu (~1,7N), bị chặn tuyến tính dù có lần copy 10 triệu phần tử. Đó là amortize làm việc: một vài lần copy lớn, nhưng chia cho 20 triệu push thì trung bình vẫn O(1). Reserve còn nhanh hơn (0,33 ns/push) vì không mọc lại lần nào.

Giờ nhìn grow-by-1: nó chỉ xây được 50 nghìn phần tử (ít hơn 400 lần) mà mất 0,161 giây — lâu gấp 3 lần thời gian nhân đôi xây 20 triệu. Mỗi push tốn 3.213 ns, chậm hơn nhân đôi ~1.250 lần. Vì tổng số phần tử phải copy là ~N²/2 = 1,25 tỷ — chỉ cho 50 nghìn phần tử! Nếu grow-by-1 xây 20 triệu như nhân đôi, nó sẽ mất (20M/50k)² × 0,161s ≈ 400² × 0,161 ≈ 25.760 giây ≈ 7 tiếng. Đó là O(N²): tăng dữ liệu 100 lần, chậm 10.000 lần.

Một lần tôi đo hớ: hai lầm tưởng ngược chiều

Tôi vào đo với hai niềm tin trái nhau mà cùng lệch. Thứ nhất: "mỗi push_back phải copy cả mảng, nên vector chậm". Sai — nhân đôi amortize: copy chỉ xảy ra khi đầy (log N lần), và tổng công mọi lần copy là ~2N, nên trung bình mỗi push chỉ 2,57 ns = O(1). Vector không chậm; nó nhanh chính vì chiến lược mọc thông minh. Thứ hai: "grow-by-1 tiết kiệm bộ nhớ (không dự phòng thừa) nên tốt hơn". Cũng sai — nó biến việc xây mảng thành O(N²), chậm thảm họa; "tiết kiệm" vài phần trăm RAM để trả giá gấp hàng nghìn lần thời gian.

Sự thật, và là bài học đo lường: nhân đôi khi mọc là điều làm mảng động nhanh — nó đổi một chút RAM dự phòng (tối đa ~2× lúc copy, trung bình lãng phí ~50% capacity) lấy chi phí push amortize O(1); cấp lại từng-chút-một biến O(1) thành O(N²). Chuỗi hình học 1+2+4+...+N ≈ 2N là toán học đằng sau — tăng theo cấp số nhân thì tổng công tuyến tính, tăng theo cấp số cộng thì tổng công bậc hai. Nếu tôi tin "vector chậm vì copy" và tránh nó, tôi bỏ lỡ một cấu trúc O(1); nếu tôi tin "grow-by-1 tiết kiệm" và tự cài, tôi tạo ra một O(N²) ẩn giết chương trình khi dữ liệu lớn.

Vì sao điều này quan trọng khi lập trình

Hệ quả đầu tiên: tin tưởng push_back/append của vector — nó là O(1) amortize. Đừng tránh vector vì sợ "copy khi mọc"; chiến lược nhân đôi làm nó nhanh, và bố cục liền mạch của mảng còn cho bạn cache locality miễn phí khi duyệt. Nhưng đừng bao giờ tự cài mảng động mà cấp lại từng chút — đó là O(N²) ẩn. Nếu bạn thấy code realloc(p, n+1) trong một vòng lặp thêm phần tử, đó là quả bom bậc hai.

Hệ quả thứ hai: nếu biết trước kích thước, reserve / cấp đủ ngay. Đo cho thấy reserve (0,33 ns/push) nhanh hơn cả nhân đôi (2,57 ns) — vì tránh được mọi lần copy và cấp lại. Khi bạn biết (hoặc đoán được) mình sẽ thêm bao nhiêu phần tử, vec.reserve(n) một lần loại bỏ toàn bộ chi phí mọc và cả phân mảnh. Đây là tối ưu rẻ nhất, dễ nhất cho vòng lặp xây dữ liệu lớn.

Hệ quả thứ ba là tinh thần đo lường: hiểu tổng chi phí của một chuỗi thao tác, không chỉ chi phí một lần. Con số mang theo: mảng động mọc lại bằng NHÂN ĐÔI (×2) thì amortize O(1) — tổng công mọi lần copy = 1+2+4+...+N ≈ 2N, đo được 2,57 ns/push xây 20 triệu phần tử (0,051s); cấp lại GROW-BY-1 (+1 mỗi lần) thì mỗi push copy cả mảng -> tổng N²/2 copy = O(N²), chỉ 50 nghìn phần tử đã 1,25 tỷ copy và 3.213 ns/push (chậm 1.250 lần, nếu 20 triệu thì ~7 giờ); RESERVE (biết trước N) = 0,33 ns/push, nhanh nhất. Nhân đôi đổi ít RAM dự phòng lấy O(1); growth factor 2 (nhanh) vs 1,5 (ít RAM). Chi phí một push_back nhỏ, nhưng chiến lược mọc quyết định cả chương trình là O(N) hay O(N²).

Thử ba mươi giây

Tự cài một mảng động đơn giản bằng malloc/realloc, thêm vài triệu phần tử, và bấm giờ hai phiên bản: một cái nhân đôi capacity khi đầy, một cái chỉ tăng +1 mỗi lần đầy. Phiên bản +1 sẽ chậm đến mức bạn phải giảm N xuống hàng chục nghìn mới chạy xong trong vài giây — trong khi phiên bản nhân đôi xử lý hàng triệu trong tích tắc. Rồi thêm một phiên bản reserve trước và đo: nó nhanh nhất. Ba mươi giây đó cho bạn thấy phép màu amortize mà std::vector làm giùm bạn mỗi ngày: chuỗi hình học biến những lần copy lớn thành chi phí push trung bình O(1) — và vì sao cấp lại "từng chút một" là một trong những sai lầm hiệu năng âm thầm mà tai hại nhất.