Vòng lặp lồng nhau là gì? Tại sao phải để ý đến nó?

Khái niệm vòng lặp lồng nhau.

Vòng lặp lồng nhau là trường hợp dùng một vòng lặp bên trong một vòng lặp khác để giải quyết vấn đề. Vòng lặp bên trong sẽ phải chạy nhiều lần cho đến khi vòng lặp bên ngoài kết thúc.

for (let i = 0; i < 10; i++){
    for (let j = 1; j < 10; j++){
        // do something
    }
}

Ta thấy vòng lặp bên trong sẽ phải chạy mỗi khi vòng lặp bên ngoài duyệt qua một phần tử. Nếu chỉ duyệt qua một số ít phần tử thì ta có thể dùng cách này, nhưng mọi thứ sẽ trở nên tồi tệ hơn nếu dùng cách này để duyệt qua một số lượng lớn phần tử. Trong thuật toán gọi là cấp độ tăng trưởng của hàm nó sẽ quyết định tới thời gian chạy cũng như độ phức tạp của thuật toán – ước lượng số câu lệnh sẽ phải thực thi với đầu vào cho trước.

:::info Ví dụ : Ở trên vòng for ngoài phải duyệt qua 10 phần tử i ( 0 – 9), với mỗi phần tử i ta phải duyệt qua 10 j phần tử (0 – 9) vậy ta sẽ phải thực thi 100 câu lệnh tất cả. Nếu thay 10 bằng một số chưa biết là n thì số câu lệnh phải thực hiện là n². Vậy ta nói thuật toán này có độ phức tạp là O(n²).

:::

Tại sao lại phải để ý đến vòng lặp lồng nhau?

Ở hình trên ta thấy tốc độ tăng trưởng của O(n²), chỉ với đầu vào 1000 phần tử thì số câu lệnh sẽ phải thực thi là 1,000,000 câu lệnh. Trên thực tế ta thường không áp dụng những thuật toán có độ phức tạp O(n²) để xử lý do lượng dữ liệu thường rất lớn dẫn đến việc xử lý trở nên chậm chạp. Nhưng tại sao vẫn nhiều người bị dính lỗi sử dụng 2 vòng lặp lồng nhau. Đơn giản thì cách sử dụng vòng lặp lồng nhau cách ta có thể hình dùng ra ngay khi giải quyết vấn đề.

Ví dụ : Giả sử bạn có một mảng tên các sản phẩm (productNames) gồm tên của hơn 500 sản phẩm và bạn có một mảng object nữa là chứa các thuộc tính của 1000 sản phẩm. Bài toán bây giờ là tính tổng giá tiền của tất cả sản phẩm có tên trong productNames.

let productNames = ['cá', 'bánh', 'táo', ...497 more...];
    
let products = [
    {name: 'cá', price: 10000},
    {name: 'chuối', price : 1200},
    {name: 'táo', price : 1000},
    {name: 'bánh', price : 200},
    ...996 more...
];

Navie method.

Cách đơn giản nhất có thể hình dung ra ngay trong đầu :

• Một vòng lặp duyệt qua từng phần tử trong productNames
  • Với một phần tử trong productNames ta tìm giá của sản phẩm trong mảng products bằng vòng lặp.
• Cộng dồn tổng lại

function calcSum(){
     let sum = 0;
     for(let name of productNames){
         for(let item of products){
             if(name == item.name) sum += item.name;
         }
     }
     return sum
}

:::warning

• Độ phức tạp thuật toán là O(n²)
• Với 500 phần tử productNames và 1000 phần tử trong products, vậy số câu lệnh phải thực thi ở đây là 500,000 câu lệnh.

:::

Đây chỉ là 500 phần tử trên thực tế số lượng phần tử có thể lớn hàng nghìn hoặc chục nghìn khi đó khối lượng tính toán sẽ tăng lên gấp bội sử dụng cách này không chỉ gây chậm chạp đôi khi có thể dẫn đến treo máy. Vậy làm sao để khắc phục vấn đề này?

Optimization Method

Để tránh khỏi vòng lặp ta cùng nhìn lại Naive Method.

• Một vòng lặp duyệt qua từng phần tử trong productNames (Cái này là điều không thể tránh được)
  • Để tránh vòng lặp lồng nhau (nested loops) thì ta phải tìm giá của mỗi phần tử ở đây mà không được dùng vòng lặp (*).
• Cộng dồn tổng lại

:::info (*) Vậy vấn đề ở đây là ta phải tìm giá cho sản phẩm cho trước mà không phải duyệt qua tất cả sản phẩm trong mảng product. But how?

May mắn ta có HashTable sinh ra để làm việc này

:::

:::tip HashTable – Bảng Băm (hoặc một phiên bản khác là HashMap) a.k.a Dictionary trong Python và một số ngôn ngữ lập trình khác – là một cấu trúc dữ liệu sinh ra để lưu trữ và tìm kiếm dữ liệu một cách nhanh chóng sử dụng Hash function (hàm băm) . Với những thuật toán Hash tốt thì tốc độ tìm kiếm phần tử trong HashTable có thể so sánh với cả mảng là O(1).

Xem thêm về HashTable : https://vi.wikipedia.org/wiki/Bảng_băm

:::

Áp dụng HashTable vào bài toán ở trên, ta cần biến đổi mảng products thành một HashTable, sau đó việc lấy giá sản phẩm trong products chỉ có độ phức tạp là O(1) tương đương với một câu lệnh.

function calcSumOptimized(productNames, products){
    // Biến đối products thành một HashTable
    let priceMap = products.reduce((map, product) => {
        map[product.name] = product.price
        return map
    }, {});

    let sum = 0;
    for(let name in productNames){
        sum += priceMap[name] // O(1)
    }
    return sum
}

:::info

• Độ phức tạp thuật toán trên là O(n)
• Với 500 phần tử productNames và 1000 phần tử products thì số câu lệnh phải thực thi là 1500. Trong thuật toán O(n+1000), O(2n), O(n/2) cũng được coi là O(n).

:::

![Biểu đồ tăng trưởng của O(n) – Linear (tuyến tính)](https://chuyenmucit.code.blog/wp-content/uploads/2021/01/image2.png

:::tip So sánh với cách thuật toán về performance

:::

Một số hàm bản chất là vòng lặp trong Javascript.

:::info

• map()
• filter()
• reduce()
• …

Tránh sử dụng các vòng lặp khác khi đang xử lý dữ liệu trong các hàm trên.

:::