Giải thuật: nhanh chậm thật sự do đâu

1 Thuật toán 'tệ hơn về big-O' lại chạy nhanh hơn — tôi mở sê-ri bằng cú vấp này O(n log n) tốt hơn O(n²) — nên tôi định dùng merge sort cho mọi trường hợp. Nhưng đo ra ở n=64 insertion sort nhanh hơn (292 so 375 ns) vì hằng số ẩn. Big-O là hình dạng đường cong khi n tiến vô cùng, không phải tốc độ ở n cụ thể; phải đo cả đường cong, không đo một điểm. Tôi đo bằng C. 03/09/2026 · 8 phút đọc

2 Hai vòng lặp giống hệt về số phép — một cái chậm hơn 452 lần Hai vòng lặp làm đúng cùng số phép load và cộng, cùng O(n) — đếm phép thì tưởng cùng tốc độ. Nhưng đo ra duyệt ngẫu nhiên chậm 452 lần duyệt tuần tự trên mảng 256 MB. Chi phí thật không nằm ở phép cộng mà ở truy cập bộ nhớ: cache và prefetch. Big-O mù hoàn toàn trước điều đó. Tôi đo bằng C. 03/09/2026 · 8 phút đọc

3 Danh sách liên kết chèn O(1), mảng chèn O(n) — mà mảng vẫn nhanh hơn 31 lần Sách bảo linked list chèn O(1) thắng mảng O(n), nên tải chèn nhiều thì chọn linked list. Nhưng đo ra list chậm hơn vector 31 lần ngay ở chèn — vì O(1) splice bị nuốt bởi O(n) đi tìm vị trí đầy cache-miss; và duyệt chậm 395 lần. Big-O một thao tác bỏ qua chi phí tìm và locality. Tôi đo bằng C. 03/09/2026 · 8 phút đọc

4 Tìm nhị phân 6 bước thua tìm tuyến tính 64 bước — vì mỗi bước đắt khác nhau O(log n) đánh bại O(n) — nên ai cũng mặc định dùng nhị phân. Nhưng đo ra ở n=64 tìm tuyến tính nhanh hơn (14,5 so 20,2 ns): nhị phân ít bước nhưng mỗi bước là một nhánh 50/50 mà CPU hay đoán sai, còn tuyến tính quét tuần tự CPU đoán trúng suốt. Big-O đếm số bước, bỏ qua giá mỗi bước. Tôi đo bằng C. 03/09/2026 · 8 phút đọc

5 Hash map O(1) — nhưng có một lần chèn chậm hơn 233.000 lần, và nó không báo trước Hash map được hứa O(1), nên tưởng mọi lần tra/chèn nhanh như nhau. Đo latency từng lần chèn: trung vị 42 ns, nhưng có một lần 9,8 mili giây khi bảng rehash cả 2 triệu phần tử — chậm hơn 233.000 lần. Tra cũng chậm dần theo load factor, và hàm băm xấu đẩy probe lên 5707. O(1) là trung bình khấu hao. Tôi đo bằng C. 03/09/2026 · 8 phút đọc

6 Hàm băm 'nhanh nhất' dồn 1 triệu khóa vào 256 ô — và SHA đắt gấp 240 lần vô ích Chọn hàm băm nhanh nhất (identity) tưởng tối ưu, nhưng với khóa có mẫu nó dồn cả triệu khóa vào 256 bucket (max 3907). SHA rải hoàn hảo nhưng tính 184 ns, gấp 240 lần hàm trộn bit cho cùng phân bố. Hàm băm tốt không phải nhanh nhất hay mạnh nhất, mà là cân bằng đúng cho dữ liệu của bạn. Tôi đo. 03/09/2026 · 9 phút đọc

7 Đổ dữ liệu id tăng dần vào cây nhị phân: tra chậm 640 lần mà không một dòng lỗi Cây tìm kiếm nhị phân được dạy là O(log n). Nhưng đổ khóa đã sắp (id tăng, timestamp — rất thường gặp) vào thì nó thoái hóa thành xâu: chiều cao 40000 thay vì 34, tra 32672 ns thay vì 51 ns, chậm 640 lần đúng bằng quét tuyến tính. Và một mảng nhị phân đẹp cache cũng không nhanh hơn cây cân bằng. Tôi đo. 03/09/2026 · 9 phút đọc

8 Cây cân bằng nhanh hơn 151 lần — nhưng trên dữ liệu ngẫu nhiên gần như vô dụng AVL sửa cây tìm kiếm suy biến: cùng khóa đã sắp, chiều cao 40000 xuống 16, tra 32538 ns xuống 215 ns. Nhưng trên khóa ngẫu nhiên AVL hơn không đáng kể mà tốn 27906 phép xoay — cân bằng là bảo hiểm cho ca xấu, không phải quà miễn phí. Và cùng cây cân bằng, bố cục bộ nhớ làm tra chênh 6 lần. Tôi đo. 03/09/2026 · 10 phút đọc

9 B-tree làm 100 phép so sánh, tìm nhị phân làm 20 — mà B-tree vẫn nhanh hơn Đếm số so sánh thì B-tree thua tìm nhị phân (bậc 64 làm 100 so với 20). Đo thời gian thì thắng (70 ns so với 98 ns) vì chỉ 4 lần nạp bộ nhớ thay vì 22 — số so sánh nói dối, đồng hồ nói thật. Và có bậc B tối ưu quanh cỡ dòng cache, không phải càng lớn càng nhanh. Tôi đo. 03/09/2026 · 9 phút đọc

10 Sách nói dựng heap là O(n log n) — đo ra O(n), và tôi hiểu ra mình đọc nhầm dòng nào Chèn từng phần tử để dựng heap 'phải là' O(n log n). Nhưng đo dữ liệu ngẫu nhiên thì nó phẳng 2,3 thao tác/phần tử — cũng O(n). O(n log n) chỉ hiện ở ca xấu (chèn giảm dần): thao tác leo 16→22 theo log n. Heapify thì O(n) bất kể đầu vào. Và heap không sắp xếp — nó chỉ cho min rẻ. Tôi đo. 03/09/2026 · 9 phút đọc

11 Thuật toán 'nhanh nhất' này chậm gấp 3000 lần trên đúng dữ liệu bạn quên test Quicksort là O(n log n) — nên nhiều người vô tư lấy pivot phần tử cuối. Nhưng trên mảng đã sắp (rất thường gặp) nó thành O(n²): thời gian gấp 4 mỗi khi n gấp đôi, ~3000 lần chậm hơn ở 1 triệu, và đệ quy sâu n tầng tràn ngăn xếp. Trung vị-của-3 cứu: về 9 ms. Tôi đo. 03/09/2026 · 9 phút đọc

12 Chậm hơn quicksort 25%, tôi đổ tội cho malloc — đo ra thủ phạm là thứ khác Merge sort cùng O(n log n) với quicksort nhưng đo ra chậm hơn 1,25 lần. Tôi đổ lỗi cho malloc trong bước trộn — đo lại thì malloc chỉ chiếm +6%, thủ phạm thật là chép dữ liệu qua đệm (+23 ms). Giá trị thật của merge không phải tốc độ mà là ổn định (0 vs 488.887 cặp đảo) và không có ca xấu. Tôi đo. 03/09/2026 · 9 phút đọc

13 Thuật toán 'hoàn hảo trên giấy' này lại chậm nhất — và càng dữ liệu lớn càng tệ Heapsort nghe như hoàn hảo: O(n log n) bảo đảm và tại chỗ — hơn quicksort có ca xấu, hơn merge tốn bộ nhớ. Nhưng đo ra nó chậm nhất trong ba (1,43× tới 2,37× quicksort), và tỉ số tăng theo n vì sift-down nhảy khắp mảng phá cache. Vai trò thật của nó là lưới an toàn, không phải tốc độ. Tôi đo. 03/09/2026 · 8 phút đọc

14 Thuật toán O(n²) 'chậm' này nhanh hơn quicksort 19 lần — và nằm trong ruột mọi thư viện sort O(n²) nghe như luôn thua O(n log n), nhưng đo ra sai hai lần: ở mảng nhỏ (tới ~128 phần tử) insertion sort nhanh hơn quicksort, và trên mảng đã sắp nó chỉ O(n) — 0,09 ms so với quicksort 1,7 ms, nhanh hơn 19 lần. Big-O là ca xấu nhất tiệm cận; n nhỏ và dữ liệu có sẵn thứ tự thì khác hẳn. Tôi đo. 03/09/2026 · 9 phút đọc

15 Câu hỏi 'thuật toán sắp xếp nào tốt nhất' có câu trả lời sai — đây là lý do Không thuật toán sắp xếp đơn nào thắng mọi mặt, nên std::sort của C++ ghép quicksort + insertion + heapsort, mỗi cái che điểm yếu cái kia. Ngưỡng insertion chỉ đáng ~14% chứ không nhiều; và cùng mảng đã sắp giết quicksort pivot cuối (331 ms, đệ quy 50000 tầng) thì introsort xong trong 0,27 ms. 'Tốt nhất' là một kiến trúc, không phải một cái tên. Tôi đo. 03/09/2026 · 8 phút đọc

16 Cái trần O(n log n) mà ai cũng tin là tuyệt đối — hóa ra chỉ là luật một trò chơi Mọi sắp xếp dựa trên so sánh bị chặn ở O(n log n). Nhưng radix và counting sort chạy O(n): radix thắng introsort 5–11 lần trên số 32-bit ở mọi cỡ, counting sort nhanh 15,6 lần với khóa nhỏ. Giới hạn thật không ở n nhỏ mà ở bề rộng khóa (32-bit 4 lượt, 64-bit 8 lượt) và scatter phá cache. Tôi đo. 03/09/2026 · 9 phút đọc

17 Hàm đệ quy đúng tuyệt đối vẫn sập ở lần gọi thứ 655.000 — và im lặng Tưởng độ sâu đệ quy tùy ý, nhưng ngăn xếp OS chỉ 8 MB, mỗi khung ~13 byte, nên có trần cứng ~655.000 lần gọi rồi segfault không một lời cảnh báo. Và bất ngờ: đệ quy KHÔNG chậm hơn vòng lặp (22,8 so 22,7 µs) — cái đắt của nó là trần ngăn xếp, không phải tốc độ. Cách chữa: ngăn xếp tường minh trên heap. Tôi đo. 03/09/2026 · 8 phút đọc

18 Một dòng code sạch đẹp gọi hàm 1,4 tỉ lần cho đúng một con số Fibonacci đệ quy khớp y hệt định nghĩa toán học, nhưng đo ra nó nổ theo hàm mũ: fib(43) gọi 1,4 tỉ lần, mất 447 ms, vì tính lại bài con chồng lấn. Quy hoạch động chỉ là 'nhớ để khỏi tính lại': memo đưa về 85 lời gọi, dưới 1 micro giây. Tabulation nhanh hơn memo 28 lần và không tràn ngăn xếp. Tôi đo. 03/09/2026 · 8 phút đọc

19 Cách thối tiền ai cũng dùng: nhanh hơn 100 triệu lần, và sai 40% số tiền Đổi tiền bằng cách chộp đồng xu lớn nhất luôn đúng với hệ {1,5,10,25}. Nhưng đo hệ khác thì nó sai 25-40% số tiền — hệ {1,7,10}, số 14: tham lam 5 xu, tối ưu 2 xu. Tham lam nhanh hơn quy hoạch động 100 triệu lần cho một truy vấn (2,1 ns so 228 ms), nhưng nhanh mà sai thì vô dụng. Tôi đo. 03/09/2026 · 8 phút đọc

20 Lời giải 'thanh lịch' O(n log n) thua một vòng for tầm thường 20 lần Bài mảng con tổng lớn nhất có lời giải chia để trị đẹp như sách giáo khoa, O(n log n). Nhưng đo ra Kadane — một vòng quét O(n) tầm thường — nhanh hơn 20 lần (5,3 so 112 ms ở 10 triệu phần tử) và gọn hơn hẳn. Chia để trị mạnh và tổng quát, nhưng đẹp không đồng nghĩa tối ưu. Tôi đo. 03/09/2026 · 8 phút đọc

21 Cùng O(V+E), nhưng một cái ra đường 1998 bước, cái kia 499.500 bước BFS và DFS được dạy như cặp sinh đôi cùng O(V+E), nên tưởng thay thế được. Nhưng trên lưới 1000×1000 chúng tìm thứ khác hẳn: BFS ra đường ngắn nhất 1998 cạnh, DFS ra đường 499.500 cạnh — dài gấp 250 lần. Bộ nhớ cũng phình theo hai chiều khác nhau. 'Cùng độ phức tạp' không có nghĩa 'cùng việc'. Tôi đo. 03/09/2026 · 8 phút đọc

22 Dijkstra trả về 4 khi đáp án đúng là 2 — chỉ vì một cạnh mang dấu trừ Dijkstra là thuật toán tham lam nhưng đúng — nhờ đúng một điều kiện: trọng số không âm. Cho nó một cạnh âm (2→1 = -3), nó chốt dist[1]=4 sai trong khi đáp án thật là 2, mà không một cảnh báo. Và cấu trúc bên trong quyết định quy mô: heap nhanh hơn mảng 36 lần trên đồ thị thưa. Tôi đo. 03/09/2026 · 8 phút đọc

23 Cấu trúc 'gần như O(1)' này tụt thành O(n) nếu bạn quên đúng hai dòng Union-Find không tự nhiên O(1): bản naive để cây thoái hóa thành chuỗi, đường find trung bình 9999 (=n/2), find hết mất 88 ms. Hai tối ưu vài dòng ép đường find về ~1, nhanh 3000 lần — và đẹp nhất, ở 10 triệu phần tử đường find trung bình vẫn phẳng lì ở 1,01. 'Gần O(1)' là sự thật đo được. Tôi đo. 03/09/2026 · 8 phút đọc

24 Thuật toán 'ngây thơ' O(n·m) hóa ra ngang KMP — trừ đúng một loại văn bản Sách bảo naive O(n·m) chậm, phải dùng KMP. Nhưng trên văn bản ngẫu nhiên naive chỉ 1,04 so sánh mỗi ký tự — gần O(n), còn nhỉnh hơn KMP. O(n·m) là trường hợp xấu nhất, chỉ bật ra trên văn bản lặp (T='aaaa', P='aa..b') nơi KMP nhanh 194 lần. Nhãn xấu nhất không phải bản án cho mọi đầu vào. Tôi đo. 03/09/2026 · 7 phút đọc

25 'Chắc chắn O(n+m)' — bỏ quên một trong hai điều, Rabin-Karp chậm 33 lần Rabin-Karp so khớp chuỗi bằng hash, được ghi là O(n+m). Nhưng con số đó đứng trên hai cái chân dễ quên: bỏ hash cuộn (tính lại mỗi cửa sổ) chậm 26 lần, dùng hash xấu trên văn bản lặp cho 999.001 va chạm giả và chậm 33 lần. Cả hai đều tụt về O(n·m) mà không một dòng lỗi. Tôi đo. 03/09/2026 · 8 phút đọc

26 Cấu trúc nói 'có thể có' này thay 25 MB bằng 1,2 MB — và không bao giờ nói dối một chiều Bloom filter trả lời 'phần tử này có trong tập không' một cách không chính xác: dương tính giả 0,81% ở 10 bit/phần tử, 14,7% ở 4 bit, giảm theo hàm mũ khi thêm bit nhưng không bao giờ về 0. Đổi lại nó không bao giờ báo âm tính giả và chỉ tốn 1,2 MB thay vì 25 MB. Có số hàm băm tối ưu. Tôi đo. 03/09/2026 · 8 phút đọc

27 free hết rồi mà tiến trình vẫn giữ 168 MB — malloc không hề miễn phí Cấp rồi giải 3 triệu object nhỏ tốn 47 ms, còn arena chỉ 6,2 ms (nhanh 8 lần). 1 triệu object 16 byte ngốn 38,6 MB thay vì 16 MB vì metadata và căn lề. Và free sạch rồi RSS vẫn đứng 168 MB. malloc trong vòng nóng là kẻ giết hiệu năng ẩn — gom vào arena chữa cả ba. Tôi đo. 03/09/2026 · 8 phút đọc

28 Cùng dữ liệu, chỉ xếp lại trong bộ nhớ, một vòng lặp nhanh gấp 4,7 lần Gói các trường của một object lại thành struct (AoS) là cách tự nhiên nhất. Nhưng khi chỉ cộng một trường của struct rộng, AoS chậm tới 4,7 lần SoA vì mỗi dòng cache kéo cả struct về mà chỉ dùng một trường. Đọc hết mọi trường thì AoS lại ngang. Mẫu truy cập quyết định bố cục, không phải cái nào nghe tự nhiên hơn. Tôi đo. 03/09/2026 · 8 phút đọc

29 Sắp mảng trước khi chạy, cùng code lại nhanh gấp 1,7 lần — vì sao? Cùng một đoạn code, cùng những con số, chỉ khác mảng được sắp trước hay chưa: bản chưa sắp chạy 660 ms, bản đã sắp 379 ms — chênh 1,7 lần. Không phải ít phép tính hơn, không phải cache. Thủ phạm là dự đoán nhánh của CPU, thứ big-O không hề thấy. Viết không nhánh xóa hẳn (183 ms). Tôi đo. 03/09/2026 · 8 phút đọc

30 Bật -O3 nhanh gấp 4 lần — rồi đổi một dấu, tụt xuống chậm gấp 11 Bật -O3, vòng nhân mảng float nhanh 3,9 lần nhờ NEON làm 4 float mỗi lệnh. Nhưng chỉ thêm một phụ thuộc chuỗi là trình biên dịch lặng lẽ bỏ vector hóa, tụt về scalar chậm 11,6 lần — không một dòng cảnh báo. SIMD không phải phép màu của cờ, mà là phần thưởng cho vòng viết đúng dạng. Tôi đo. 03/09/2026 · 10 phút đọc

31 'Thêm phần tử là O(1)' — vậy sao có một lần nó ngốn 392 micro giây? Thêm vào mảng động là O(1) khấu hao, nhưng đo đường cong từng thao tác thấy gai O(n): lần cấp phát cuối sao chép 2,1 triệu phần tử mất 392µs, gấp 400.000 lần một lần thêm thường. Và tăng dung lượng mỗi lần +1 để 'tiết kiệm bộ nhớ' hóa ra là O(n²), chậm 17.851 lần. Tôi đo cả đường cong. 03/09/2026 · 10 phút đọc

32 Một dòng tung xúc xắc cắt 2 tỉ phép so sánh xuống còn 1,3 triệu Quicksort pivot cố định gặp mảng đã sắp xếp làm 2,05 tỉ so sánh (901 ms); pivot ngẫu nhiên chỉ 1,3 triệu (1,1 ms) — ít hơn 1524 lần. Và skip list cân bằng bằng tung đồng xu, đạt ~log n mà không một phép xoay. Gieo ngẫu nhiên đúng chỗ là tăng an toàn, không phải thêm rủi ro. Tôi đo. 03/09/2026 · 9 phút đọc

33 Cùng một hàm: -O0 tràn ngăn xếp ở 1 triệu, -O2 chạy tới 100 triệu Đệ quy đuôi được đồn là liều thuốc chống tràn ngăn xếp. Nhưng cùng một hàm: gcc -O0 tràn ở 1 triệu tầng, gcc -O2 chạy 100 triệu vì biến thành vòng lặp, còn CPython không bao giờ tối ưu đuôi — vẫn tràn ở 1000 khung. 'Đệ quy đuôi an toàn' chỉ đúng khi trình biên dịch thật sự làm TCO. Tôi đo. 03/09/2026 · 8 phút đọc

34 Đặt một bit khi thì chậm hơn ghi byte, khi thì nhanh gấp 6 — cùng một dòng code Bitset nhỏ hơn mảng bool 8 lần, giao hai tập bằng AND nhanh 12,9 lần (64 phần tử mỗi lệnh). Nhưng đặt một bit lẻ chậm hơn ghi một byte 1,46 lần khi vừa cache — rồi nhanh hơn 6,3 lần khi tràn cache. Lợi thật của bitset là mật độ cache, không phải mẹo bit. Tôi đo cả đường cong. 03/09/2026 · 8 phút đọc

35 Chính sách cache 'tốt nhất' đôi khi trúng đúng 0% — thua cả tung xúc xắc LRU cài đúng đạt O(1) nhờ băm + danh sách liên kết đôi (nhanh 323 lần bản O(n) ở cache 10.000). Nhưng cache to gấp 25 lần chỉ thêm 37 điểm hit, và một lượt quét tuần tự lớn hơn cache khiến LRU trúng 0% — đuổi ngẫu nhiên lại được 41,6%. Hiệu quả cache phụ thuộc hoàn toàn vào mẫu truy cập. Tôi đo. 03/09/2026 · 9 phút đọc

36 Trie thua bảng băm 3,4 lần và tốn RAM gấp 40 — vậy nó sống để làm gì? Tra chuỗi chính xác, bảng băm nhanh hơn trie 3,4 lần và tốn ít bộ nhớ hơn 40 lần — trie nhảy con trỏ từng ký tự, mỗi bước một cache-miss. Nhưng đếm mọi khóa có tiền tố cho trước, trie nhanh hơn 32 lần vì băm phải quét cả bảng. Lợi thật của trie là tiền tố, không phải tốc độ tra. Tôi đo. 03/09/2026 · 8 phút đọc

37 Tra nhanh hơn 18.554 lần mà vẫn thua, tới khi bạn tìm lần thứ 93 Mỗi truy vấn suffix array nhanh hơn KMP 18.554 lần (0,21 µs so 3.869 µs) — nhưng phải dựng mảng trước, tốn 358 ms cho văn bản 2 triệu ký tự. Cho một lần tìm, KMP thắng đậm; suffix array chỉ có lãi sau ~93 truy vấn trên cùng văn bản. 'Nhanh nhất' vô nghĩa nếu chưa hỏi tìm bao nhiêu lần. Tôi đo. 03/09/2026 · 8 phút đọc

38 10 lõi mà chỉ nhanh 7 lần, rồi 4 lần, rồi 3 lần — vì đâu? Chia việc cho 10 lõi tưởng nhanh gấp 10, nhưng đo ra: việc song song thuần nhất chỉ đạt 7,38x, thêm 10% việc tuần tự tụt còn 4,53x (khớp luật Amdahl), và việc nghẽn băng thông bộ nhớ chỉ 3,28x vì mọi lõi tranh một bus. Phần tuần tự nhỏ bé mới là thứ đặt trần. Tôi đo. 03/09/2026 · 8 phút đọc

39 Lock-free nhanh hơn mutex 2,8 lần — rồi thêm luồng lại chậm gấp mười Atomic fetch_add đúng là nhanh hơn mutex 2,8 lần khi một luồng. Nhưng một biến atomic chung scale ÂM: 627 tụt xuống 34 triệu/giây ở 10 luồng vì cache-line ping-pong, gần bằng mutex. Cách nhanh thật không phải khóa xịn hơn mà là không chia sẻ — đếm riêng nhanh gấp ~180 lần. Tôi đo. 03/09/2026 · 8 phút đọc

40 Thuật toán 'thông minh' của Karatsuba thua nhân tay tới tận 9.800 chữ số Nhân học sinh O(n²) đáng ra phải thua Karatsuba O(n^1,585) — nhưng đo ra nó thắng tới tận ~1024 hạn (~9.800 chữ số). Ở 64 hạn Karatsuba còn chậm hơn 2,8 lần vì hằng số ẩn của đệ quy. Và mọi phép số lớn chậm hơn nhân 64-bit gốc hàng trăm nghìn lần. Bậc tốt hơn không tự động nhanh hơn. Tôi đo. 03/09/2026 · 7 phút đọc

41 rand() % n làm nửa số ra gấp đôi nửa kia, và bit cuối chỉ đảo 0,1,0,1 rand() % 20000 đo ra lệch đúng 2 lần giữa hai vùng giá trị vì 32768 không chia hết cho 20000. Bit thấp nhất của LCG chỉ đảo 0,1,0,1 — chu kỳ 2, tất định hoàn toàn. Còn xorshift chạy 717 triệu số/giây, nhanh hơn rand() 2,8 lần nhưng tuyệt đối không dùng được cho mật mã. 'Ngẫu nhiên' là tính chất phải đo. Tôi đo. 03/09/2026 · 8 phút đọc

42 Nén xong lại phình thêm 316 byte, và mức 9 y hệt mức 6 Cùng zlib, tỉ lệ nén nhảy từ 514 lần (dữ liệu lặp) xuống 2,66 lần (văn bản) xuống dưới 1 với byte ngẫu nhiên — 8 MB phình thành 8.000.316 byte vì không gì nén được hỗn loạn. Mức 9 cho tỉ lệ đúng bằng mức 6, còn lzma chặt hơn nhưng chậm 23 lần. Nén là thuộc tính của dữ liệu, không phải công cụ. Tôi đo. 03/09/2026 · 8 phút đọc

43 Cùng chữ O, một bên chạy chậm một bên bị hệ điều hành giết Ma trận kề ngốn 1.527 MB ở V=40.000 và OOM quanh V~90.000, còn danh sách kề chỉ 2,6 MB. Bảng DP đầy đủ dùng 382 MB, bản cuộn hai biến dùng 1 MB cùng thời gian. Merge sort tốn gấp đôi RAM nhưng nhanh hơn heapsort 3,7 lần. Không gian là bức tường cứng, không phải tài nguyên miễn phí — tôi đọc VmHWM để đo. 03/09/2026 · 9 phút đọc

44 Benchmark của tôi đo ra 0 nano giây, rồi 4,62 ms, rồi vọt 2,7 lần — bốn cách cái đồng hồ nói dối Kẹp đồng hồ hai đầu vòng lặp rồi đọc số nghe đơn giản, nhưng con số ấy nói dối bốn kiểu: bỏ sink thì compiler xóa vòng và đo ra 0 ns cho việc chưa chạy; lần đầu chậm 27% vì cache lạnh; trên VM một lần vọt 2,7 lần median; và clock_gettime tốn 16 ns nên đo việc vài ns ra rác. Cách đo cho đáng tin. 03/09/2026 · 8 phút đọc

45 Tra thành viên: quét tuyến tính thắng ở n=8, còn nhị phân O(log n) không bao giờ nhanh nhất Bài kết sê-ri: cùng một bài toán 'x có trong tập không', kẻ thắng đổi theo quy mô — quét tuyến tính nhanh nhất ở n=8, hash ở n lớn, bitset đè bẹp cả nếu biết miền khóa; và nhị phân O(log n) luôn kẹt giữa, không bao giờ nhanh nhất. Không có cấu trúc tốt nhất phổ quát — đo, đừng đoán. 03/09/2026 · 8 phút đọc