Bạn xây một chuỗi lớn bằng cách nối dần trong vòng lặp: s = s + phần, lặp N lần. Nhìn thì vô hại — mỗi lần chỉ thêm một mẩu nhỏ. Nhưng có một chi tiết mà cú pháp giấu đi: chuỗi của bạn biến đổi tại chỗ hay tạo mới mỗi lần? Câu trả lời quyết định vòng lặp đó là O(N) hay O(N²) — và với chuỗi bất biến như trong Java hay Python, câu trả lời là O(N²), một cái bẫy có thể biến vài giây thành hàng chục phút. Tôi đo cả hai cách trong container gcc:13, và con số cho thấy "chỉ là nối chuỗi" có thể là một quả bom bậc hai.
Copy cả chuỗi mỗi lần, hay chỉ thêm vào cuối
Điểm mấu chốt là bất biến (immutable) hay không:
-
Chuỗi bất biến —
Stringtrong Java,strtrong Python. Chúng không thể sửa. Khi bạn viếts = s + c, ngôn ngữ không thêmcvàos— nó tạo một chuỗi hoàn toàn mới, copy toàn bộs(i byte) rồi thêmc. Lần lặp thứ i copy i byte. Tổng qua N lần:1 + 2 + ... + N = N²/2byte phải copy — O(N²). Đây đúng là bài học grow-by-1 của phần 2 và chèn đầu mảng của phần 3: mỗi thao tác copy lại tất cả những gì đã có. -
Buffer động —
std::string +=,StringBuilder(Java), hoặc gom vàolistrồi''.join(Python). Chúng ghi vào cuối vùng bộ nhớ đã cấp; khi đầy thì nhân đôi capacity — nên trung bình mỗi ký tự chỉ O(1) amortize, tổng O(N). Không copy lại chuỗi cũ mỗi lần.
Cùng kết quả — một chuỗi N ký tự — nhưng hai con đường khác nhau cả một bậc độ phức tạp.
Đo: 2151 ns/ký tự so với 2,18 ns/ký tự
Tôi xây chuỗi bằng ba cách. Với cách bất biến (mô phỏng bằng cách tạo std::string mới mỗi lần), tôi phải giảm N vì O(N²):
g++ -O2:
A. IMMUTABLE (s = s + c, tạo chuỗi MỚI mỗi lần):
N = 200.000 ký tự : 0,43 s | tổng byte copy = 20 tỷ (~N²/2) | 2.151 ns/ký tự (O(N²))
B. std::string += (append tại chỗ, amortize):
N = 20.000.000 ký tự : 0,044 s | 2,18 ns/ký tự (O(N))
C. reserve(N) trước rồi += :
N = 20.000.000 ký tự : 0,042 s | 2,10 ns/ký tự (nhanh nhất, 0 mọc lại)
Nhìn khác biệt: cách bất biến chỉ xây được 200 nghìn ký tự mà đã mất 0,43 giây, và tổng số byte phải copy lên tới 20 tỷ — cho một chuỗi chỉ 200 nghìn ký tự! Mỗi ký tự tốn 2.151 ns. Trong khi cách += xây 20 triệu ký tự (nhiều gấp 100 lần) chỉ trong 0,044 giây, mỗi ký tự 2,18 ns. Tức là per-ký-tự, cách bất biến chậm hơn ~1.000 lần. Nếu bạn xây 20 triệu ký tự bằng cách bất biến, nó sẽ mất (20tr/200k)² × 0,43s = 100² × 0,43 ≈ 4.300 giây ≈ 72 phút — so với 0,044 giây của +=. Đó là sự khác biệt giữa "tức thời" và "đi ăn trưa rồi quay lại vẫn chưa xong". Cách reserve còn nhanh hơn chút (2,10 ns) vì không mọc lại lần nào.
Một lần tôi đo hớ: "nối chuỗi thì bình thường" và "String + nhanh như StringBuilder"
Tôi vào đo với niềm tin: "nối chuỗi trong vòng lặp là chuyện thường, chuỗi nào cũng vậy". Đo phá tan: nối kiểu bất biến (tạo chuỗi mới mỗi lần) copy toàn bộ chuỗi mỗi bước, tổng N²/2 byte, O(N² — 200 nghìn ký tự đã copy 20 tỷ byte, và nếu 20 triệu thì mất 72 phút. Còn niềm tin phổ biến hơn, tôi từng có khi viết Java: "String s = s + x cũng nhanh như StringBuilder, trình biên dịch tối ưu giùm". Sai — trong một vòng lặp, String + tạo một chuỗi mới mỗi lần lặp (trình biên dịch chỉ tối ưu được nối trên một biểu thức, không xuyên vòng lặp), nên nó là O(N²). Đây là một trong những lỗi hiệu năng phổ biến nhất mà người mới (và cả người cũ) mắc: xây một chuỗi/báo cáo/JSON lớn bằng += trên String, chạy nhanh với dữ liệu test nhỏ, rồi treo với dữ liệu thật.
Bài học đo lường: nối chuỗi lặp kiểu BẤT BIẾN (s = s + phần tạo chuỗi mới mỗi lần) là O(N²) — mỗi bước copy cả chuỗi hiện có, tổng N²/2 byte (đo: 200k ký tự copy 20 tỷ byte, 2151 ns/ký tự, nếu 20 triệu thì ~72 phút); dùng BUFFER/StringBuilder/join (append tại chỗ, amortize như vector phần 2) cho O(N) (2,18 ns/ký tự), reserve trước thì nhanh nhất. Nếu tôi tin "nối chuỗi thì bình thường" và dùng String += trong vòng lặp xây dữ liệu lớn, tôi tạo ra một O(N²) ẩn — profiler chỉ vào "vòng lặp nối chuỗi" trông vô tội, trong khi thủ phạm là hàng tỷ byte bị copy đi copy lại.
Vì sao điều này quan trọng khi lập trình
Hệ quả đầu tiên: xây chuỗi trong vòng lặp thì dùng buffer, không dùng + trên chuỗi bất biến. Java: StringBuilder. Python: gom vào list rồi ''.join(list) (hoặc io.StringIO). C#: StringBuilder. C++: std::string += (đã là buffer động). Quy tắc: nếu bạn thấy s = s + ... hay s += ... với s là chuỗi bất biến bên trong một vòng lặp, đó là O(N²) — đổi sang buffer ngay. Đây là một trong những tối ưu "một dòng đổi cả bậc" dễ nhất.
Hệ quả thứ hai: biết trước độ dài thì reserve. Giống reserve của vector phần 2, nếu bạn ước lượng được kích thước chuỗi cuối, s.reserve(n) (C++) hay StringBuilder(capacity) (Java) loại bỏ cả các lần mọc lại — nhanh nhất và tránh phân mảnh. Với vòng lặp xây chuỗi rất lớn, đây là tối ưu rẻ thêm vào.
Hệ quả thứ ba là tinh thần đo lường: "tính bất biến" của kiểu dữ liệu là một chi phí ẩn — nó biến thao tác tại-chỗ thành copy-toàn-bộ. Con số mang theo: nối chuỗi lặp: kiểu BẤT BIẾN (String Java, str Python, s = s + x tạo chuỗi MỚI mỗi lần) = O(N²), copy N²/2 byte (đo 200k ký tự = 20 tỷ byte copy, 2151 ns/ký tự, 20 triệu ~72 phút); dùng StringBuilder/list-join/std::string += (append tại chỗ, amortize) = O(N) (2,18 ns/ký tự, nhanh 1000x/ký tự); reserve trước = nhanh nhất. Thấy += trên chuỗi bất biến trong vòng lặp = quả bom O(N²). Cùng một chuỗi kết quả, hai con đường, hai bậc chi phí.
Thử ba mươi giây
Viết một vòng lặp xây chuỗi vài chục nghìn ký tự bằng s = s + 'x' (trong Java, Python, hay C++ với std::string t = s + 'x'; s = t; để buộc tạo mới), và bấm giờ. Rồi tăng số ký tự lên gấp đôi — thời gian gấp bốn, dấu hiệu rõ của O(N²). Giờ đổi sang StringBuilder (Java), list + join (Python), hay s += 'x' (C++ std::string) và xây gấp một trăm lần số ký tự — nó vẫn nhanh hơn. Bạn sẽ thấy khoảng cách không phải vài phần trăm mà hàng trăm tới hàng nghìn lần. Ba mươi giây đó cho bạn thấy điều mà "chỉ là nối chuỗi" giấu đi: khi chuỗi bất biến, mỗi lần + copy lại tất cả, biến một vòng lặp trông tuyến tính thành bậc hai — và một buffer append-tại-chỗ là toàn bộ khác biệt giữa xong-trong-tích-tắc và chờ-cả-tiếng.
