Đoạn mã dưới đây tôi gặp trong dự án thật ít nhất năm lần, ở năm nơi khác nhau:

for (int x : canTim) {
    if (danhSachLon.contains(x)) { ... }
}

Nhìn hoàn toàn bình thường. Nó cũng chạy hoàn toàn bình thường — với dữ liệu thử.

List.contains là O(n): nó quét tuần tự cho tới khi tìm thấy. Đặt trong vòng lặp m lần thì tổng chi phí là O(n × m).

Đo thử với 1000 phần tử cần tìm:

ChonCauTruc.locBangList        1000  avgt   224.393 us/op
ChonCauTruc.locBangList       10000  avgt  2661.355 us/op
ChonCauTruc.locBangSet         1000  avgt     2.562 us/op
ChonCauTruc.locBangSet        10000  avgt     3.042 us/op

Với n = 1000: chậm hơn 88 lần. Với n = 10.000: chậm hơn 875 lần.

Và chú ý xu hướng: tăng n gấp 10 thì bản List chậm đi gần 12 lần, còn bản Set gần như không đổi — 2,56 lên 3,04. Đó là khác biệt giữa O(n×m) và O(m).

Đổi cấu trúc ngay giữa hàm vẫn lời

Phản đối thường gặp: "nhưng dữ liệu của tôi đến dưới dạng List, dựng Set cũng tốn chứ".

Đo luôn cả chi phí dựng:

ChonCauTruc.locBangSetTaoMoi   1000  avgt   11.351 us/op
ChonCauTruc.locBangSetTaoMoi  10000  avgt   85.167 us/op

Kể cả khi dựng một HashSet mới rồi vứt đi ngay sau đó, nó vẫn nhanh hơn:

20 lần ở n = 1000, và 31 lần ở n = 10.000.

Nên đoạn sửa đúng chỉ là một dòng:

Set<Integer> tapTim = new HashSet<>(danhSachLon);   // O(n), một lần
for (int x : canTim) {
    if (tapTim.contains(x)) { ... }                 // O(1) mỗi lần
}

Đây là bài học chung: chi phí chuyển đổi cấu trúc dữ liệu thường rẻ hơn nhiều so với dùng sai cấu trúc trong vòng lặp.

Bảng chi phí

Con số trong bảng là độ phức tạp trung bình. Đây là bảng tôi vẫn tra lại khi phân vân:

thêm cuối thêm đầu tìm theo chỉ số tìm theo giá trị xoá
ArrayList O(1)* O(n) O(1) O(n) O(n)
LinkedList O(1) O(1) O(n) O(n) O(n)**
ArrayDeque O(1)* O(1) — O(n) O(1) ở hai đầu
HashSet / HashMap O(1) — — O(1) O(1)
LinkedHashSet/Map O(1) — — O(1) O(1)
TreeSet / TreeMap O(log n) — — O(log n) O(log n)
PriorityQueue O(log n) — — O(n) O(log n) lấy đầu

* Trung bình khấu hao — thỉnh thoảng phải cấp phát lại mảng. ** Đã tìm được vị trí thì O(1), nhưng tìm vị trí vẫn O(n).

Hai điều bảng này không nói, mà bài ArrayList đã đo được:

Cùng O(n) không có nghĩa là ngang nhau — duyệt LinkedList chậm gấp ba ArrayList vì cục bộ bộ nhớ.

Hằng số ẩn sau big-O có thể lớn: TreeMap O(log n) chậm hơn HashMap O(1) khoảng 14 lần ở 100.000 phần tử, như bài về Set đã đo.

Ba tình huống chọn sai hay gặp

Một: dùng List.contains trong vòng lặp — đã nói ở trên. Dấu hiệu nhận biết: hai vòng lặp lồng nhau, hoặc một contains/indexOf/remove(Object) nằm bên trong vòng lặp.

Hai: list.remove(0) để lấy phần tử đầu

while (!hangDoi.isEmpty()) {
    var viec = hangDoi.remove(0);    // O(n) — dịch cả mảng mỗi lần
    xuLy(viec);
}

Mỗi lần xoá phần tử đầu, ArrayList phải dịch toàn bộ phần còn lại sang trái. Vòng lặp thành O(n²).

Đổi sang ArrayDeque với poll() là O(1).

Ba: sắp xếp lại trong vòng lặp

for (var x : dulieu) {
    ds.add(x);
    Collections.sort(ds);     // sắp xếp lại toàn bộ, mỗi lần thêm
}

Sắp xếp n lần, mỗi lần O(n log n), thành O(n² log n). Nếu cần luôn có phần tử nhỏ nhất thì dùng PriorityQueue; nếu cần toàn bộ có thứ tự thì dùng TreeSet; nếu chỉ cần thứ tự ở cuối thì thêm hết rồi sắp một lần.

Câu hỏi để chọn

Tôi chọn theo bốn câu hỏi, theo thứ tự:

Tra cứu theo khoá hay theo vị trí? Theo khoá → Map. Theo vị trí → List.

Có cần thứ tự không, và thứ tự nào? Không cần → HashMap/HashSet. Thứ tự chèn → LinkedHashMap/LinkedHashSet. Thứ tự sắp xếp → TreeMap/TreeSet.

Có trùng lặp không? Không → Set. Có → List.

Thêm/xoá ở đâu? Hai đầu → ArrayDeque. Cuối → ArrayList. Theo mức ưu tiên → PriorityQueue.

Bốn câu này giải quyết được gần hết. Còn lại là những trường hợp đặc biệt: EnumMap cho khoá enum, BitSet cho tập số nguyên dày đặc, ConcurrentHashMap cho nhiều luồng.

Khi nào big-O không quan trọng

Một cảnh báo để cân bằng, vì tối ưu sớm cũng có hại.

Với n nhỏ — dưới vài chục phần tử — mọi thứ đều đủ nhanh, và ArrayList thường thắng nhờ cục bộ bộ nhớ. Dựng một HashSet cho danh sách 5 phần tử là tốn hơn, không phải tiết kiệm.

Với n không đổi — một cấu hình 20 mục đọc lúc khởi động — thì chọn cái nào cũng vậy.

Điều đáng quan tâm là n có lớn lên không. Danh sách 50 phần tử hôm nay có thể là 50.000 sau một năm, và O(n²) sẽ chuyển từ "không thấy gì" sang "hệ thống treo" mà không có giai đoạn cảnh báo ở giữa.

Nên câu hỏi đúng không phải "chỗ này có chậm không" mà là "chỗ này có chậm đi theo bình phương không".

Vài mẹo đo

Đừng đoán, hãy đo — nhưng đo cho đúng:

Dùng JMH, đừng dùng System.currentTimeMillis() quanh một vòng lặp. JIT cần làm nóng, và trình tối ưu có thể xoá hẳn mã không dùng kết quả.

Đo ở nhiều kích thước n. Một điểm dữ liệu không cho biết xu hướng. Chính việc chạy ở cả 1000 và 10.000 mới làm lộ ra khác biệt O(n×m) và O(m) trong bài này.

Đo trên dữ liệu giống thật. Một HashMap với khoá phân bố đều rất khác một HashMap mà mọi khoá va chạm.

Thử ba mươi giây

Tìm trong dự án của bạn một chỗ có contains hoặc indexOf nằm bên trong vòng lặp.

Đó là ứng viên số một cho một dòng sửa đổi làm nhanh lên hàng chục lần. Và nếu danh sách hiện tại chỉ có vài chục phần tử, hãy hỏi: một năm nữa nó có bao nhiêu?

Ngày mai ta khép lại chặng Collections bằng việc tự viết một Collection — cài đặt AbstractList, và những hợp đồng bắt buộc phải giữ.