1.11 — Ví dụ thực tế nhanh
Một đoạn code 6 dòng, hoàn toàn đúng về logic, làm màn hình báo cáo treo 40 giây. Nó chạy tốt suốt một năm với 500 khách hàng, rồi hệ thống lên 5.000 khách và thời gian chạy tăng 100 lần chứ không phải 10 lần. Nguyên nhân là vòng lặp lồng nhau — mỗi khách hàng lại duyệt toàn bộ danh sách đơn hàng. Cách sửa chỉ là đổi cách tra cứu sang Dictionary, và thời gian xuống 0,4 giây. Điều đáng nhớ nhất: bug này không bao giờ lộ ra ở môi trường phát triển, vì với vài chục bản ghi thì cả hai cách đều chạy tức thì.
Mục tiêu bài học
Sau bài này bạn có thể:
- Nhận ra vòng lặp lồng nhau trên hai tập dữ liệu lớn.
- Chuyển tra cứu tuyến tính sang
Dictionary. - Giải thích vì sao O(n²) không lộ ra khi dữ liệu nhỏ.
- Tự rà dự án tìm lỗi tương tự.
Nội dung bài học
1.11.1 — Code gây ra sự cố
// Tính tổng giá trị đơn hàng cho mỗi khách — LOGIC ĐÚNG, hiệu năng thảm hoạ
var report = new List<CustomerReport>();
foreach (var customer in customers) // 5.000 khách
{
decimal total = 0;
foreach (var order in orders) // 200.000 đơn
{
if (order.CustomerId == customer.Id)
total += order.Total;
}
report.Add(new CustomerReport(customer.Name, total));
}
Đếm số phép so sánh:
5.000 khách x 200.000 đơn = 1.000.000.000 phép so sánh
Một tỷ phép so sánh — đó là 40 giây.
Điều nguy hiểm: ở môi trường phát triển với 50 khách và 200 đơn, con số là 10.000 phép so sánh, chạy trong vài mili giây. Không ai thấy vấn đề gì.
1.11.2 — Vì sao tăng 10 lần dữ liệu lại chậm 100 lần
500 khách x 20.000 đơn = 10.000.000 -> 0,4 giây
5.000 khách x 200.000 đơn = 1.000.000.000 -> 40 giây
Dữ liệu tăng 10 lần ở cả hai chiều, nhưng số phép so sánh tăng 100 lần — vì 10 × 10 = 100. Đây là đặc trưng của độ phức tạp O(n²) (bài 1.8).
Hệ quả thực tế: hệ thống trông ổn cho tới một ngưỡng nào đó rồi đổ sập rất nhanh. Không có giai đoạn "hơi chậm" để bạn kịp nhận ra và xử lý.
1.11.3 — Sửa bằng Dictionary
// Bước 1: gom đơn hàng theo mã khách — duyệt danh sách đơn ĐÚNG MỘT LẦN
var totalByCustomer = new Dictionary<int, decimal>();
foreach (var order in orders) // 200.000 lần
{
if (totalByCustomer.ContainsKey(order.CustomerId))
totalByCustomer[order.CustomerId] += order.Total;
else
totalByCustomer[order.CustomerId] = order.Total;
}
// Bước 2: duyệt khách, tra cứu TỨC THÌ
var report = new List<CustomerReport>();
foreach (var customer in customers) // 5.000 lần
{
decimal total = totalByCustomer.GetValueOrDefault(customer.Id, 0m);
report.Add(new CustomerReport(customer.Name, total));
}
200.000 + 5.000 = 205.000 thao tác -> 0,4 giây
(trước: 1.000.000.000 -> 40 giây)
Nhanh hơn gần 5.000 lần, và code cũng không dài hơn bao nhiêu.
Lý do Dictionary nhanh: nó dùng bảng băm, nên tra cứu theo khoá mất thời gian không đổi bất kể có 10 hay 10 triệu phần tử. Duyệt List để tìm thì phải xem từng phần tử (bài 1.8).
Viết gọn hơn với LINQ:
var totalByCustomer = orders
.GroupBy(o => o.CustomerId)
.ToDictionary(g => g.Key, g => g.Sum(o => o.Total));
var report = customers
.Select(c => new CustomerReport(c.Name, totalByCustomer.GetValueOrDefault(c.Id, 0m)))
.ToList();
Hai cách cho hiệu năng tương đương. Chọn cách nào là tuỳ đội — nhưng cả hai đều nhanh hơn hẳn vòng lặp lồng nhau, và đó mới là điều quan trọng.
1.11.4 — Cái bẫy tinh vi hơn
// Nhìn KHÔNG thấy vòng lặp lồng — nhưng vẫn là O(n²)
foreach (var customer in customers)
{
var customerOrders = orders.Where(o => o.CustomerId == customer.Id); // duyệt HẾT
report.Add(new CustomerReport(customer.Name, customerOrders.Sum(o => o.Total)));
}
Where là một vòng lặp, chỉ là nó không được viết ra. Mỗi lần gọi nó duyệt toàn bộ danhSachDon.
Dấu hiệu nhận biết: một lời gọi Where, First, Any, Contains hoặc Sum trên một tập lớn nằm bên trong vòng lặp chạy trên một tập lớn khác. Nhìn thì ngắn gọn, nhưng chi phí giống hệt vòng lặp lồng nhau.
Cùng một lỗi xuất hiện với List.Contains:
// Cham — Contains tren List duyet tuyen tinh
var processedIds = new List<int>();
foreach (var order in orders)
{
if (processedIds.Contains(order.Id)) continue; // O(n) mỗi lần gọi
processedIds.Add(order.Id);
}
// Nhanh — HashSet tra cứu tức thì
var processedIds = new HashSet<int>();
foreach (var order in orders)
{
if (!processedIds.Add(order.Id)) continue; // Add trả về false nếu đã có
}
HashSet.Add vừa thêm vừa cho biết phần tử đã tồn tại chưa — gọn hơn và nhanh hơn cặp Contains + Add.
1.11.5 — Tự rà dự án
1. Tìm vòng lặp lồng nhau:
grep -rn -A 5 "foreach" --include=*.cs src/ | grep -B 2 "foreach"
Với mỗi kết quả, hỏi: hai tập này có thể lớn tới mức nào? Vòng lặp lồng trên 10 phần tử không sao; trên 10.000 thì có.
2. Tìm truy vấn LINQ trong vòng lặp:
grep -rn -A 3 "foreach" --include=*.cs src/ | grep -E "\.Where\(|\.First|\.Any\(|\.Contains\("
3. Tìm Contains trên List:
grep -rn "List<.*>.*\.Contains(" --include=*.cs src/
Mỗi kết quả là một ứng viên chuyển sang HashSet.
Cách kiểm chứng nhanh nhất: đo với dữ liệu gấp 10 lần. Nếu thời gian tăng khoảng 10 lần thì code là O(n) — bình thường. Nếu tăng khoảng 100 lần thì là O(n²) — cần sửa.
1.11.6 — Rà lại code của bạn
Danh sách rà soát vòng lặp lồng nhau
- •Không có vòng lặp lồng nhau trên hai tập dữ liệu có thể lớn.
- •Không gọi Where, First hay Any trên tập lớn bên trong vòng lặp.
- •Tra cứu theo khoá dùng Dictionary, không duyệt List.
- •Kiểm tra tồn tại dùng HashSet, không dùng List.Contains.
- •Đã đo với lượng dữ liệu tương đương production, không chỉ dữ liệu mẫu.
- •Đã kiểm chứng bằng cách tăng dữ liệu 10 lần và xem thời gian tăng bao nhiêu.
- •Biết ước lượng tập dữ liệu lớn nhất có thể gặp.
Bài tập áp dụng
Bài 1 — Đo hai cách
Tạo 5.000 khách và 200.000 đơn, chạy cả hai phiên bản và so sánh thời gian.
Tiêu chí hoàn thành: bạn có số đo của chính mình, và đối chiếu được nó với con số trong bài — kể cả khi hai con số không khớp.
Gợi ý và lời giải — Bài 1
Gợi ý. Kiểm tra hai phiên bản cho cùng kết quả trước khi so sánh thời gian. Nếu kết quả khác nhau thì so sánh tốc độ là vô nghĩa.
Lời giải:
static (double lap, double tuDien) Do(int soKhach, int soDon)
{
var rnd = new Random(42); // hạt cố định -> lặp lại được
var khach = Enumerable.Range(1, soKhach)
.Select(i => new KhachHang(i, $"Khách {i}")).ToList();
var don = Enumerable.Range(1, soDon)
.Select(i => new DonHang(i, rnd.Next(1, soKhach + 1), rnd.Next(100, 10_000))).ToList();
// Cách 1: vòng lặp lồng nhau
var sw = Stopwatch.StartNew();
var bc1 = new List<BaoCao>(soKhach);
foreach (var k in khach)
{
decimal t = 0;
foreach (var d in don)
if (d.KhachHangId == k.Id) t += d.TongTien;
bc1.Add(new BaoCao(k.HoTen, t));
}
var lap = sw.Elapsed.TotalMilliseconds;
// Cách 2: Dictionary
sw.Restart();
var tong = new Dictionary<int, decimal>();
foreach (var d in don)
tong[d.KhachHangId] = tong.GetValueOrDefault(d.KhachHangId) + d.TongTien;
var bc2 = khach.Select(k => new BaoCao(k.HoTen, tong.GetValueOrDefault(k.Id))).ToList();
var tuDien = sw.Elapsed.TotalMilliseconds;
// KIỂM TRA hai cách cho cùng kết quả — làm trước khi so sánh tốc độ
if (bc1.Sum(b => b.Tong) != bc2.Sum(b => b.Tong))
throw new Exception("Hai cách cho kết quả khác nhau!");
return (lap, tuDien);
}
Kết quả đo trên .NET 9.0.203, Intel Xeon 8272CL 2,60 GHz:
500 khách × 20.000 đơn = 10.000.000 so sánh | vòng lặp 32 ms | từ điển 2,6 ms | 12×
1.000 khách × 40.000 đơn = 40.000.000 so sánh | vòng lặp 122 ms | từ điển 6,3 ms | 19×
2.500 khách × 100.000 đơn = 250.000.000 so sánh | vòng lặp 742 ms | từ điển 4,3 ms | 173×
5.000 khách × 200.000 đơn = 1.000.000.000 so sánh | vòng lặp 3.728 ms | từ điển 8,9 ms | 419×
Và đây là điều đáng nói: bài học ở mục 1.11.1 nói một tỷ phép so sánh là 40 giây. Đo thật trên máy này chỉ 3,7 giây.
Vì sao chênh 10 lần:
- CPU hiện đại chạy khoảng một tỷ phép so sánh số nguyên đơn giản mỗi giây
trở lên, nếu dữ liệu nằm gọn trong bộ nhớ đệm
- con số 40 giây phù hợp hơn với trường hợp mỗi lần so sánh còn kèm
việc khác: so chuỗi, gọi phương thức, hoặc dữ liệu quá lớn cho cache
Nhưng kết luận của bài học KHÔNG đổi, và đó mới là điều quan trọng:
Vòng lặp lồng: 32 ms -> 3.728 ms khi dữ liệu tăng 10 lần = 116 lần chậm hơn
Từ điển: 2,6 ms -> 8,9 ms = 3,4 lần chậm hơn
Hình dạng O(n²) được xác nhận đúng. Chỉ có hằng số nhân là khác máy.
Ba điều rút ra về việc đọc số liệu hiệu năng:
1. Luôn tự đo lại trên máy của mình.
Con số trong tài liệu phụ thuộc: CPU, bộ nhớ đệm, phiên bản runtime,
và kiểu dữ liệu được so sánh
-> dùng nó để hiểu HÌNH DẠNG, đừng dùng làm mục tiêu tuyệt đối
2. Tỉ lệ đáng tin hơn con số tuyệt đối.
"3,7 giây" -> đổi theo máy
"116 lần chậm hơn khi dữ liệu tăng 10 lần" -> đúng trên MỌI máy
3. Và 3,7 giây vẫn là một sự cố thật.
Một endpoint mất 3,7 giây:
- vượt xa ngưỡng chấp nhận được của người dùng
- chiếm một luồng suốt thời gian đó
- với 10 request đồng thời -> 37 giây CPU -> máy chủ bão hoà
Nên dù con số nhỏ hơn 10 lần so với bài học, kết luận vẫn giữ nguyên: đây là code phải sửa.
Và một chi tiết nhỏ trong số đo đáng chú ý:
Từ điển ở 2.500 khách: 4,3 ms
Từ điển ở 5.000 khách: 8,9 ms
Từ điển ở 1.000 khách: 6,3 ms <- CAO HƠN mốc 2.500 khách
Con số 6,3 ms cao hơn mốc liền sau nó là nhiễu đo — lần chạy đó gặp một đợt thu gom rác, hoặc hệ điều hành xen việc khác vào. Với những phép đo dưới 10 ms, nhiễu chiếm tỉ trọng lớn.
Cách xử lý: chạy mỗi mốc nhiều lần và lấy trung vị,
hoặc dùng BenchmarkDotNet cho những phép đo nhỏ như vậy.
Nhận ra một con số không hợp quy luật và gọi tên nó là nhiễu — thay vì cố giải thích nó — là một kỹ năng đọc số liệu quan trọng.
Bài 2 — Kiểm chứng O(n²)
Chạy phiên bản vòng lặp lồng với 500 rồi 5.000 khách, xác nhận thời gian tăng khoảng 100 lần.
Tiêu chí hoàn thành: bạn xác nhận được tỉ lệ, và giải thích được vì sao nó không chính xác bằng đúng 100.
Gợi ý và lời giải — Bài 2
Gợi ý. Đo ít nhất bốn mốc, không phải hai. Hai điểm thì đường nào cũng vẽ qua được.
Lời giải — lập tỉ lệ giữa các mốc liên tiếp:
Từ số đo ở bài 1:
| Khách | Đơn | Phép so sánh | Vòng lặp | Tỉ lệ so với mốc trước |
|---|---|---|---|---|
| 500 | 20.000 | 10 triệu | 32 ms | — |
| 1.000 | 40.000 | 40 triệu | 122 ms | 3,8× |
| 2.500 | 100.000 | 250 triệu | 742 ms | 6,1× |
| 5.000 | 200.000 | 1 tỷ | 3.728 ms | 5,0× |
Từ mốc đầu tới mốc cuối:
dữ liệu tăng 10 lần ở cả hai chiều
phép so sánh tăng 100 lần (10 × 10)
thời gian tăng 116 lần (32 -> 3.728 ms)
Vì sao 116 chứ không phải đúng 100 — ba lý do:
1. Chi phí cố định ở mốc nhỏ làm tỉ lệ lệch.
32 ms ở mốc 500 khách gồm cả:
- tạo danh sách 20.000 đơn
- cấp phát bộ nhớ
- JIT biên dịch lần đầu (nếu chưa làm nóng)
Phần cố định đó chiếm tỉ trọng LỚN ở mốc nhỏ, NHỎ ở mốc lớn
-> làm mốc nhỏ trông chậm hơn thực tế -> tỉ lệ tính ra thấp hơn
Trong số đo này, hiệu ứng ngược lại chiếm ưu thế — xem lý do 2.
2. Bộ nhớ đệm của CPU.
20.000 đơn × khoảng 24 byte ≈ 480 KB -> vừa trong bộ nhớ đệm L2
200.000 đơn ≈ 4,8 MB -> KHÔNG vừa, phải đọc từ RAM
-> mỗi phép so sánh ở mốc lớn TỐN HƠN mỗi phép so sánh ở mốc nhỏ
-> thời gian tăng NHANH HƠN 100 lần
Đây là lý do chính khiến con số là 116 chứ không phải 100. Và nó là một hiệu ứng thật, không phải sai số đo: dữ liệu lớn thật sự chậm hơn trên mỗi phần tử.
3. Nhiễu từ hệ điều hành và bộ thu gom rác.
Cột "tỉ lệ so với mốc trước": 3,8× rồi 6,1× rồi 5,0×
Lý thuyết cho tỉ lệ đều: (1000/500)² = 4, (2500/1000)² = 6,25, (5000/2500)² = 4
Đo được: 3,8 / 6,1 / 5,0
Lý thuyết: 4,0 / 6,25 / 4,0
Hai mốc giữa khớp rất sát. Mốc cuối lệch (5,0 so với 4,0) — đúng là chỗ dữ liệu vượt khỏi bộ nhớ đệm.
Cách xác nhận O(n²) chắc chắn hơn: vẽ tỉ lệ, không vẽ thời gian.
Nếu là O(n): n tăng 2 lần -> thời gian tăng 2 lần
Nếu là O(n²): n tăng 2 lần -> thời gian tăng 4 lần
Nếu là O(n log n): n tăng 2 lần -> thời gian tăng khoảng 2,2 lần
// Đo với n tăng gấp đôi mỗi lần — dễ nhận dạng nhất
foreach (var n in new[] { 500, 1000, 2000, 4000, 8000 })
{
var t = DoVongLap(n, n * 40);
Console.WriteLine($"n={n,5} | {t,8:F0} ms");
}
Tỉ lệ ~4 giữa các mốc liên tiếp -> O(n²), rất rõ
Tỉ lệ ~2 -> O(n)
Tỉ lệ ~2,2 -> O(n log n)
Và một cách kiểm chứng không cần đo thời gian chút nào: đếm.
long soPhepSoSanh = 0;
foreach (var k in khach)
foreach (var d in don)
{
soPhepSoSanh++;
if (d.KhachHangId == k.Id) t += d.TongTien;
}
Console.WriteLine($"Số phép so sánh: {soPhepSoSanh:N0}");
500 khách × 20.000 đơn -> 10.000.000
5.000 khách × 200.000 đơn -> 1.000.000.000
Đúng 100 lần, không sai một chút nào — vì đây là ĐẾM, không phải ĐO.
Cách đếm này ổn định tuyệt đối: không phụ thuộc máy, không phụ thuộc bộ nhớ đệm, không có nhiễu. Khi cần chứng minh độ phức tạp cho người khác, nó thuyết phục hơn một biểu đồ thời gian — cùng lý do mà logical reads được ưa dùng hơn thời gian khi phân tích truy vấn database.
Bài 3 — Rà dự án
Chạy ba lệnh ở mục 1.11.5 trên dự án thật và đếm số vị trí cần xem lại.
Tiêu chí hoàn thành: bạn có con số, đã phân loại, và phân biệt được kết quả đáng lo với kết quả vô hại.
Gợi ý và lời giải — Bài 3
Gợi ý. Vòng lặp lồng nhau trên hai tập nhỏ là hoàn toàn bình thường. Vấn đề chỉ xuất hiện khi cả hai tập đều lớn.
Lời giải — chạy và phân loại:
#!/usr/bin/env bash
echo "=== 1. Vòng lặp lồng nhau ==="
grep -rn -A5 "foreach" --include=*.cs src/ | grep -c "foreach.*foreach"
echo "=== 2. LINQ bên trong vòng lặp ==="
grep -rn -A3 "foreach" --include=*.cs src/ \
| grep -E "\.(Where|First|Any|Contains|Sum|Count)\(" | wc -l
echo "=== 3. Contains trên List ==="
grep -rn "List<.*>.*\.Contains(" --include=*.cs src/ | wc -l
=== 1. Vòng lặp lồng nhau ===
18
=== 2. LINQ bên trong vòng lặp ===
31
=== 3. Contains trên List ===
7
Phân loại 18 vòng lặp lồng nhau:
| Nhóm | Số | Đánh giá |
|---|---|---|
| Tập trong có tối đa vài chục phần tử | 11 | Vô hại |
| Tập ngoài nhỏ, tập trong lớn | 3 | Cần xem |
| Cả hai tập đều lớn | 4 | Nguy hiểm |
// VÔ HẠI — tập trong luôn là 12 tháng
foreach (var nhanVien in danhSachNhanVien) // vài trăm
foreach (var thang in muoiHaiThang) // 12
BaoCao(nhanVien, thang);
// NGUY HIỂM — cả hai đều theo dữ liệu người dùng
foreach (var khach in danhSachKhach) // 5.000
foreach (var don in danhSachDon) // 200.000
if (don.KhachHangId == khach.Id) ...
Câu hỏi phân loại, gói trong một dòng:
"Cả HAI tập có tăng theo dữ liệu người dùng không?"
Một tập cố định (12 tháng, 7 ngày, 5 trạng thái) -> vô hại
Cả hai đều tăng -> cần sửa
Phân loại 31 lời gọi LINQ bên trong vòng lặp — nhóm này hay bị bỏ sót hơn:
// NGUY HIỂM — Where duyệt toàn bộ danhSachDon cho MỖI khách
foreach (var khach in danhSachKhach)
{
var donCuaKhach = danhSachDon.Where(d => d.KhachHangId == khach.Id);
baoCao.Add(new BaoCao(khach.HoTen, donCuaKhach.Sum(d => d.TongTien)));
}
Không có từ khoá foreach lồng nhau -> lệnh grep thứ nhất KHÔNG tìm ra
Nhưng chi phí giống hệt: 5.000 × 200.000
// SỬA — gom trước một lần
var theoKhach = danhSachDon.ToLookup(d => d.KhachHangId);
foreach (var khach in danhSachKhach)
baoCao.Add(new BaoCao(khach.HoTen, theoKhach[khach.Id].Sum(d => d.TongTien)));
ToLookup là công cụ đúng cho việc này: nó giống GroupBy nhưng trả về một cấu trúc tra cứu, và khoá không tồn tại trả về dãy rỗng thay vì ném lỗi.
Và 7 lời gọi Contains trên List:
// Chậm — Contains trên List duyệt tuyến tính
var daXuLy = new List<int>();
foreach (var don in danhSachDon) // 200.000
{
if (daXuLy.Contains(don.Id)) continue; // duyệt tới 200.000 phần tử
daXuLy.Add(don.Id);
}
Tổng chi phí: 200.000 × (trung bình 100.000) = 20 tỷ phép so sánh
// Nhanh — HashSet.Add vừa thêm vừa cho biết đã tồn tại chưa
var daXuLy = new HashSet<int>();
foreach (var don in danhSachDon)
if (!daXuLy.Add(don.Id)) continue;
Tổng chi phí: 200.000 thao tác
Thứ tự nên sửa — theo số phần tử, không theo số lượng kết quả grep:
1. 4 vòng lặp lồng "cả hai tập lớn" — ảnh hưởng lớn nhất
2. 7 chỗ Contains trên List — s ửa rất nhanh, đổi một từ
3. Các lời gọi LINQ trong vòng lặp trên tập lớn
4. Phần còn lại — ghi lại, không cần sửa ngay
Và một cách kiểm tra rẻ hơn cả việc đọc code: thêm một dòng đo.
var sw = Stopwatch.StartNew();
var baoCao = TaoBaoCao(khach, don);
_log.LogInformation("Tạo báo cáo cho {SoKhach} khách, {SoDon} đơn: {Ms} ms",
khach.Count, don.Count, sw.ElapsedMilliseconds);
Log này cho bạn số liệu THẬT theo thời gian:
hôm nay: 1.200 khách, 45.000 đơn, 180 ms
ba tháng sau: 3.400 khách, 140.000 đơn, 1.650 ms
-> thấy được xu hướng TRƯỚC khi nó thành sự cố
-> và nó chỉ ra đúng chỗ nào đang tăng nhanh hơn dữ liệu
Đây là cách phòng ngừa hiệu quả nhất cho loại lỗi này: không phải tìm ra mọi vòng lặp lồng nhau trong dự án, mà là biết được chỗ nào đang chậm dần trước khi người dùng phát hiện ra.
Tự kiểm tra
Frequently asked questions
Vì sao tăng dữ liệu 10 lần lại chậm 100 lần?
Vì vòng lặp lồng nhau có độ phức tạp O bình phương. Khi cả hai tập cùng tăng 10 lần, số phép so sánh tăng 10 nhân 10 tức 100 lần.
Vì sao lỗi này không lộ ra ở môi trường phát triển?
Vì với vài chục bản ghi, số phép so sánh chỉ vài nghìn và chạy trong vài mili giây. Vấn đề chỉ xuất hiện khi dữ liệu thật đủ lớn, và khi đó nó đổ sập rất nhanh chứ không có giai đoạn hơi chậm.
Vì sao Dictionary nhanh hơn duyệt List?
Vì Dictionary dùng bảng băm nên tra cứu theo khoá mất thời gian không đổi bất kể có mười hay mười triệu phần tử. Duyệt List để tìm thì phải xem từng phần tử.
Dấu hiệu nhận biết cái bẫy LINQ trong vòng lặp là gì?
Một lời gọi Where, First, Any, Contains hay Sum trên tập lớn nằm bên trong vòng lặp chạy trên tập lớn khác. Nhìn ngắn gọn nhưng chi phí giống hệt vòng lặp lồng nhau, vì bản thân Where cũng là một vòng lặp.
Vì sao nên dùng HashSet.Add thay cho cặp Contains và Add?
Vì Add trên HashSet vừa thêm vừa trả về false nếu phần tử đã tồn tại, nên gọn hơn. Và tra cứu trên HashSet mất thời gian không đổi, còn Contains trên List phải duyệt tuyến tính.
Cách kiểm chứng nhanh nhất một đoạn code có phải O bình phương không?
Đo với dữ liệu gấp mười lần. Nếu thời gian tăng khoảng mười lần thì là O tuyến tính, bình thường. Nếu tăng khoảng một trăm lần thì là O bình phương và cần sửa.
Kết luận
Ba điều đáng nhớ nhất:
- Code đúng logic vẫn có thể không dùng được khi dữ liệu đủ lớn.
Wherebên trongforeachlà vòng lặp lồng nhau, chỉ là không nhìn thấy.- Đo với dữ liệu gấp 10 lần là cách rẻ nhất để phát hiện O(n²).
Tham khảo
Điều hướng
- Bài trước: 1.9 — Mini case study
- Bài tiếp theo: 1.11 — Review and Assessment
- Về module: Trang mục lục