LinQ Peformance - Làm việc với các List có chung nhiều phần tử

Trong công việc hàng ngày, chúng ta thường tiếp xúc với các bài toán có dạng cơ bản chung như sau: từ các tập hợp cho trước, thực hiện tìm ra các phần tử giống nhau của các tập hợp (dựa vào 1 điều kiện nghiệp vụ), hoặc cập nhật thông tin của các phần tử giống nhau này. Dạng cơ bản này có thể thấy được qua các bài toán như: tổng hợp dữ liệu hàng hóa từ các kho (trong bài toán quản lý kho), tìm dữ liệu giống nhau theo dòng trong các file và lưu vào cơ sở dữ liệu (bài toán import data), loại bỏ các dữ liệu trùng lặp (trong bài toán đồng bộ dữ liệu),...

Dạng bài toán này nếu thực hiện bằng mã lệnh chương trình, ta thường thấy các lập trình viên sử dụng các vòng lặp (for, foreach,...) để giải quyết. Tuy nhiên, việc sử dụng các vòng lặp không khéo léo sẽ dẫn đến độ phức tạp O(n*m*...), và tất nhiên là thời gian xử lý đoạn mã lệnh sẽ dài và làm giảm hiệu năng của chương trình. Đơn cử bài toán yêu cầu tổng hợp số lượng sản phẩm từ 2 kho, chúng ta thường sẽ thấy cách làm như thế này:
 

public IEnumerable<Item> ConsolidateStockUsingJoin(List<Item> stock1, List<Item> stock2)
{
    var consolidatedItems = from s1 in stock1
                            join s2 in stock2
                            on s1.Sku equals s2.Sku
                            select new Item
                            {
                                Sku = s1.Sku,
                                Quantity = s1.Quantity + s2.Quantity
                            };

    return consolidatedItems;
}

(dùng linQ join để tìm các Item có chung mã sku và cập nhật số lượng Quantity của từng Item, sau đó trả về dữ liệu đã tổng hợp và tất nhiên cách làm này dẫn đến độ phức tạp O(n*m)).


Vậy có cách làm nào khác (vẫn dùng linQ) tốt hơn cách trên không? Tất nhiên là có, và cách mới này sẽ làm độ phức tạp giảm xuống còn O(n), tức là thời gian thực hiện mã lệnh sẽ giảm xuống. Ở đây, chúng ta tinh chỉnh như sau:
 

public IEnumerable<Item> ConsolidateStockUsingDictionary(List<Item> stock1, List<Item> stock2)
{
    var stock2Dict = stock2.ToDictionary(x => x.Sku, x => x.Quantity);

    foreach (var item in stock1)
    {
        var quantityOfItemInStock2 = stock2Dict[item.Sku];
        yield return new Item
        {
            Sku = item.Sku,
            Quantity = item.Quantity + quantityOfItemInStock2
        };
    }
}

(Việc chuyển 1 List<T> thành 1 Dictionary chính là magic trong đoạn mã lệnh trên. Và để làm được điều magic này, các bạn nên xem lại kiến thức về Dictionary Data Structure nhé.

Tổng hợp lại, ta có đoạn mã lệnh so sánh hiệu năng như sau:

 

public class Item
{
    public string Sku { get; set; }
    public int Quantity { get; set; }
}

public static IEnumerable<Item> GetItemsStock()
{
    for (var i = 1; i < 1000; i++)
    {
        yield return new Item
        {
            Sku = $"Sku-{i}",
            Quantity = i
        };
    }
}

public IEnumerable<Item> ConsolidateStockUsingJoin(List<Item> stock1, List<Item> stock2)
{
    var consolidatedItems = from s1 in stock1
                            join s2 in stock2
                            on s1.Sku equals s2.Sku
                            select new Item
                            {
                                Sku = s1.Sku,
                                Quantity = s1.Quantity + s2.Quantity
                            };

    return consolidatedItems;
}

public IEnumerable<Item> ConsolidateStockUsingDictionary(List<Item> stock1, List<Item> stock2)
{
    var stock2Dict = stock2.ToDictionary(x => x.Sku, x => x.Quantity);

    foreach (var item in stock1)
    {
        var quantityOfItemInStock2 = stock2Dict[item.Sku];
        yield return new Item
        {
            Sku = item.Sku,
            Quantity = item.Quantity + quantityOfItemInStock2
        };
    }
}

private void Test_ConsolidateStockUsingJoin()
{
    var stock1 = GetItemsStock().ToList();
    var stock2 = GetItemsStock().ToList();

    var watch = new Stopwatch();
    watch.Start();
    var items = ConsolidateStockUsingJoin(stock1, stock2);
    watch.Stop();

    Console.WriteLine($"time eplased - ConsolidateStockUsingJoin - {watch.Elapsed}");

}


private void Test_ConsolidateStockUsingDictionary()
{
    var stock1 = GetItemsStock().ToList();
    var stock2 = GetItemsStock().ToList();

    var watch = new Stopwatch();
    watch.Start();
    var items = ConsolidateStockUsingDictionary(stock1, stock2);
    watch.Stop();

    Console.WriteLine($"time eplased - ConsolidateItemsUsingDictionary - {watch.Elapsed}");

}

Test_ConsolidateStockUsingJoin();
Test_ConsolidateStockUsingDictionary();

​​
Và kết quả chạy thử nhiều lần, thật sự ấn tượng:

time eplased - ConsolidateStockUsingJoin - 00:00:00.0004734
time eplased - ConsolidateItemsUsingDictionary - 00:00:00.0001997