So sánh tốc độ List collection và HashSet collection trong C#

So sánh tốc độ List collection và HashSet collection trong C#
5 (100%) 2 votes

Mở đầu

Lâu nay khi lập trình chúng ta chủ yếu sử dụng kiểu dữ liệu List để thao tác với các collection, mặc dù đây không phải là kiểu collection duy nhất trong .NET nhưng các lập trình viên đã quá quen thuộc với việc sử dụng kiểu List nên thói quen này không phải dễ thay đổi.

Trong bài viết này chúng ta sẽ cùng so sánh tốc độ của kiểu ListHashSet (một kiểu collection xuất hiện bắt đầu từ .NET 3.5) để biết được khi nào thì nên sử dụng List và khi nào thì nên dùng kiểu HashSet.

ListToSet

Kiểu List<T>

Kiểu List<T> chứa một danh sách item, truy cập qua chỉ số. Không giống như kiểu mảng là một kiểu cố định kích thước, list tự động tăng kích thước khi cần. Đây chính là lý do tại sao List đôi khi còn được gọi là kiểu mảng động.

Cấu trúc bên trong của List thực chất là một mảng, nếu mảng này hết chỗ nó sẽ tạo ra một mảng mới lớn hơn và copy toàn bộ item từ mảng cũ sang mảng mới. Ngày nay thì chúng ta thấy hầu hết lập trình viên đều dùng kiểu List thay vì kiểu mảng. Tuy nhiên trong một số trường hợp nếu item là cố định thì bạn nên dùng kiểu mảng để có performance tốt hơn.

Một số phép toán trên kiểu List

Thêm/Xóa phần tử ở đầu hoặc giữa List

Nếu bạn cần thêm/xóa một phần tử ở đầu hoặc giữa List thì nó sẽ cần dịch chuyển một hoặc nhiều item. Trường hợp xấu nhất, nếu bạn thêm/xóa một phần tử ở đầu List nó sẽ phải dịch tất cả item còn lại trong List. Nếu List càng lớn thì sẽ càng mất thời gian và resource để thực hiện.

Thêm/Xóa phần tử ở cuối List

Thêm/Xóa một phần tử ở cuối List ngược lại rất nhanh và không phụ thuộc vào kích thước của List vì không item nào cần phải dịch chuyển.

Tìm kiếm một phần tử

Khi tìm kiếm một phần tử bằng một số hàm như IndexOf, Contains, Find thì kiểu List sẽ thực hiện duyệt qua tất cả các item để tìm ra phần tử đó. Trong trường hợp xấu nhất, nếu phần tử nằm ở cuối List thì tất cả các item cần được duyệt qua.

Truy cập một phần tử bởi chỉ số

Là phép toán thực hiện rất nhanh vì bản chất bên trong List là một mảng. Tốc độ truy cập không bị ảnh hưởng bởi độ lớn của List.

Kiểu HashSet<T>

HashSet là kiểu xuất hiện từ .NET 3.5, nó chứa các item duy nhất, nghĩa là nó không thể chứa các item trùng lặp và thứ tự của item cũng không quan trọng. VD: {a,b,c} tương đương {c,b,a}

Sử dụng HashSet khi bạn cần tìm kiếm nhanh trên một tập các item không lặp. VD trong bài toán thực tế mình đang phải làm là kiểm tra một danh sách Order có nằm trong một danh sách Order khác không?

Kiểu HashSet dựa trên hàm hash để tính toán ra chỉ số của item vì vậy phép tìm kiếm có tốc độ rất nhanh. Dưới đây là một số phép toán trên kiểu HashSet

So sánh tốc độ List<T> và HashSet<T>

Mặc dù trong các tài liệu đều chỉ ra kiểu HashSet nhanh hơn List nhưng thực tế có phải luôn luôn như vậy? Chúng ta sẽ cùng kiểm nghiệm qua một ví dụ benchmark đơn giản: Kiểm tra một danh sách có nằm trong một danh sách khác hay không:

Kết quả thực hiện cho thấy sự khác nhau rõ rệt về performance:

  • 50 item List.Contains mất 0.000018s, HashSet.Contains mất 0.000023s
  • 50000 item List.Contains mất 9.38s, HashSet.Contains mất 0.002s

BenchmarkResult

Từ kết quả trên có thể thấy rằng không phải lúc nào performance của HashSet cũng nhanh hơn List. Với số lượng item nhỏ (<50 item) thì tốc độ của List còn nhanh hơn so với HashSet nhưng khi số lượng item lớn thì lúc đó HashSet mới phát huy tác dụng, tốc độ của HashSet rất nhanh và không phụ thuộc vào số lượng item.

Kết luận

Kiểu List tương đối nhanh khi bạn truy cập item bằng index nhưng khi tìm kiếm một item trong List lớn (50 item trở lên) thì nó sẽ chậm dần. Ngược lại kiểu HashSet lại rất nhanh khi tìm kiếm trên một tập item lớn. Vì vậy mà tùy từng trường hợp cụ thể bạn cần lựa chọn kiểu collection cho phù hợp với bài toán của mình.

Nếu bạn có bất kì câu hỏi hay kinh nghiệm nào liên quan đến bài viết này xin hãy để lại comment bên dưới và đừng quên chia sẻ cho bạn bè nếu thấy hữu ích.

Happy coding. Stay tuned.

P/s: Source code example trong bài các bạn có thể download tại đây: ListAndHashSetBenchmark

Leave a Reply

Your email address will not be published. Required fields are marked *