Đánh Giá Thuật Toán - đo Thời Gian Thực Thi Code Trong C# | Tự Học ICT

Trong bài học này chúng ta xem xét một vấn đề cơ bản khác phục vụ cho việc học các nội dung của phần “thuật toán”: đánh giá hiệu suất thuật toán trên .NET framework. Do tập tài liệu này hướng tới ứng dụng, chúng ta sẽ không áp dụng phân tích Big O như thông thường. Thay vào đó chúng ta sẽ đánh giá thuật toán bằng cách đo đạc thời gian thực hiện thực tế của code. Việc đo thời gian này nếu nghe qua có thể là đơn giản. Tuy nhiên trong đó có nhiều vấn đề cần chú ý để thu được kết quả đánh giá chính xác hiệu suất của thuật toán.

NỘI DUNG CỦA BÀI Ẩn 1. Vấn đề đánh giá và biểu diễn độ phức tạp của thuật toán, Big O 2. Đánh giá thời gian thực thi của thuật toán 2.1. Cách đo thời gian trong C# đơn giản nhất (nhưng không chính xác) 2.2. Vấn đề đo thời gian thực thi của phương thức trong C# .NET 3. Một số đặc điểm trong hoạt động của môi trường .NET 3.1. Garbage Collector 3.2. Finalizer 3.3. Tiến trình (process) và luồng (thread) 4. Xây dựng class C# hỗ trợ đánh giá thời gian thực thi của thuật toán 5. Kết luận

Vấn đề đánh giá và biểu diễn độ phức tạp của thuật toán, Big O

Khi nói về thuật toán, một trong những chủ đề quan trọng nhất là độ phức tạp tính toán (computational complexity), trong đó đặc biệt chú trọng tới độ phức tạp về thời gian (time complexity).

Độ phức tạp của thuật toán được tính cho các trường hợp xấu nhất hoặc mức độ trung bình. Độ phức tạp có thể được hiểu như là số lượng các phép toán cơ sở cần thiết để thực hiện thuật toán theo kích thước dữ liệu đầu vào. Cách biểu diễn độ phức tạp của thuật toán được gọi là Big O notation.

Nếu gọi n là kích thước dữ liệu đầu vào, khi sử dụng biểu diễn Big O, chúng ta có thể gặp các biểu diễn như O(n), O(n2), O(n log(n)). Ví dụ, O(n) có nghĩa là số lượng phép toán tăng tỷ lệ thuận với kích thước dữ liệu đầu vào. O(n2) là độ phức tạp quadratic, nghĩa là số phép toán tăng với tỉ lệ bình phương với kích thước dữ liệu đầu vào. O(n log(n)) được gọi là linearithmic. Đặc biệt nếu gặp O(1) thì đây là độ phức tạp không phụ thuộc vào kích thước dữ liệu đầu vào (nó là hằng số).

Để đưa ra được độ phức tạp Big O của một thuật toán đôi khi phải thực hiện nhiều tính toán phức tạp. Kiểu tính toán này thường gặp trong các nghiên cứu hơn.

Trong thực tế, chúng ta có thể dùng một kiểu đánh giá khác, mặc dù không chính thống lắm, nhưng phù hợp với việc áp dụng thuật toán trong phát triển ứng dụng. Đó là trực tiếp đo thời gian thực hiện của thuật toán đó trong các môi trường cần triển khai. Trong phần còn lại của bài học này chúng ta sẽ tìm hiểu cách thức đo thời gian thực thi của thuật toán khi thực thi trong .NET Framework.

Đánh giá thời gian thực thi của thuật toán

Cách đo thời gian trong C# đơn giản nhất (nhưng không chính xác)

Trước hết hãy cùng thực hiện một ví dụ nhỏ về việc đánh giá thời gian thực thi của code thuật toán trong C#. Lưu ý rằng, đây là một ví dụ LỖI, cho ra kết quả đo thời gian thực thi code không chính xác.

Tạo một project thuộc kiểu Console App (.NET framework). Đặt tên solution là S01_Timing, tên project là P01_SimpleTiming. Viết code cho Program.cs như sau:

using System; namespace P01_SimpleTiming { class Program { static void Main(string[] args) { int size = 9999; int[] data = new int[size]; Build(data, size); var startTime = DateTime.Now; Print(data); var time = DateTime.Now.Subtract(startTime); Console.WriteLine($"\r\nExecution time: {time.Ticks} (ticks) = {time.Milliseconds} (ms)"); Console.ReadKey(); } static void Build(int[] arrary, int size) { for (var i = 0; i < size; i++) { arrary[i] = i; } } static void Print(int[] array) { foreach (var i in array) Console.Write($"{i} "); } } }

Dịch và chạy thử chương trình. Tùy vào hệ thống, kết quả sẽ rất khác nhau. Thậm chí mỗi lần chạy cũng sẽ cho ra kết quả khác nhau.

Nếu bạn vẫn chưa biết/thông thạo cách tạo project và viết code trong Visual Studio, bạn nên quay lại học C# cơ bản.

Trong ví dụ trên chúng ta tạo hai phương thức tĩnh Build và Print. Build có nhiệm vụ khởi tạo giá trị cho một mảng. Print in mảng đó ra console. Chúng ta đo thời gian thực thi của phương thức Print bằng cách sử dụng lớp DateTime để lấy thời điểm ngay trước khi gọi Print. Ngay sau khi Print hoàn thành, chúng ta lại lấy thời điểm lúc đó trừ đi thời điểm bắt đầu để ra thời gian thực thi. Logic này rất đơn giản!

Vấn đề đo thời gian thực thi của phương thức trong C# .NET

Cách đo trên rất đơn giản nhưng lại không phù hợp để đo thời gian thực thi của code trên .NET framework. Có hai vấn đề chính.

Thứ nhất, đoạn code trên đo thời gian trôi qua từ lúc gọi đến lúc kết thúc thực hiện phương thức (trả điều khiển lại cho Main). Có thể có những tiến trình (process) khác cũng đồng thời chạy và ảnh hưởng đến thời gian đo được.

Thứ hai, việc đo thời gian trên đã bỏ qua ảnh hưởng của công cụ thu gom rác (Garbage Collector, GC) của .NET framework. Đối với môi trường .NET, GC có chạy vào bất kỳ lúc nào (không dự đoán được) để thu gom các object không sử dụng. Do đó, GC có thể ảnh hưởng lớn đến thời gian thực thi của phương thức đang cần đo và làm sai lệch kết quả.

Do vậy, cách đo thời gian thực thi của code trên C# .NET phải tính đến hai yếu tố trên.

Một số đặc điểm trong hoạt động của môi trường .NET

Để đưa ra được phương pháp đo thời gian thực thi phù hợp, chúng ta phải tìm hiểu kỹ hơn các đặc điểm hoạt động của môi trường .NET có ảnh hưởng đến việc đo đạc này.

Garbage Collector

Trong C#, khi một phương thức hoạt động sẽ được bố trí một stack để lưu các biến cục bộ. Biến thuộc các kiểu giá trị (như int, double, bool) được bố trí bộ nhớ trong stack. Object thuộc các kiểu tham chiếu (như string, mảng, class) được bố trí bộ nhớ trong vùng heap. Địa chỉ tham chiếu của các object (nằm trong heap) lại được lưu trong stack.

Các biến cục bộ của phương thức nằm trong stack sẽ được giải phóng khi phương thức kết thúc. Tuy nhiên, các object nằm trong heap lại không bị giải phóng mà sẽ vẫn tiếp tục nằm đó cho đến khi Garbage Collector ra tay dọn dẹp.

Garbage Collector là một tiến trình độc lập chuyên làm nhiệm vụ dọn dẹp heap. Nó có thể ra tay vào bất cứ lúc nào nó thấy phù hợp. Khi GC ra tay, nó ảnh hưởng lớn đến thời gian thực thi của phương thức đang chạy lúc đó. Dữ liệu trong heap chỉ bị GC dọn dẹp nếu như không có bất kỳ tham chiếu nào tới dữ liệu đó nữa.

Như vậy, chúng ta cần đảm bảo rằng trong suốt thời gian đo đạc, GC sẽ không làm phiền chương trình. Giải pháp là chúng ta chủ động gọi GC để dọn rác trước khi thực thi phương thức.

GC.Collect();

Khi heap đã sạch sẽ, GC không có lý do để làm phiền khi phương thức đang hoạt động.

Finalizer

Các object nằm trong heap đều có một phương thức gọi là Finalizer. Lời gọi phương thức này được được xem như bước cuối cùng trước khi xóa object. Vấn đề nằm ở chỗ không thể xác định được khi nào thì phương thức này được gọi.

Như vậy, khi chủ động gọi GC, chúng ta cũng cần đảm bảo rằng các object dư thừa trên heap phải hoàn toàn được xóa. Nếu không, Finalizer của các object này có thể chạy khi chúng ta đang đo thời gian và do đó ảnh hưởng đến kết quả.

Giải pháp cho vấn đề này là bắt chương trình chờ cho đến khi nào tất cả các finalizer của các object trên heap được kích hoạt. Điều này tương đương với việc các object này bị xóa bỏ hoàn toàn.

GC.WaitForPendingFinalizers();

Tiến trình (process) và luồng (thread)

Trong .NET, mỗi chương trình chạy trong một không gian độc lập gọi là tiến trình (process) hoặc miền ứng dụng (application domain). Bên trong mỗi process, chương trình hoặc một phần của chương trình được thực thi trong một hoặc nhiều luồng (thread). Thời gian xử lý cho ứng dụng được hệ điều hành phân phối thông qua luồng.

Khi đánh giá thời gian thực thi của thuật toán chúng ta chỉ muốn áp dụng cho đúng phần code thực hiện trong process của chương trình. Để thực hiện, chúng ta sử dụng đoạn code nhỏ sau:

var startingTime = Process.GetCurrentProcess.Threads(0).UserProcessorTime; var duration = Process.GetCurrentProcess.Threads(0).UserProcessorTime.Subtract(startingTime);

Xây dựng class C# hỗ trợ đánh giá thời gian thực thi của thuật toán

Ở phần trên chúng ta đã phân tích các yếu tố ảnh hưởng đến việc đo thời gian thực thi của code trong C#. Tiếp theo đây chúng ta sẽ xây dựng một class hỗ trợ đánh giá hiệu suất của thuật toán để sử dụng về sau.

Trong solution tạo thêm một project mới thuộc kiểu Console App (.NET Framework) với tên là P02_ProperTiming. Viết code cho file Program.cs như sau:

using System; using System.Diagnostics; namespace P2_ProperTiming { class Timing { TimeSpan _start = new TimeSpan(0); TimeSpan _duration = new TimeSpan(0); public TimeSpan Duration => _duration; public void Stop() { _duration = Process.GetCurrentProcess().Threads[0].UserProcessorTime.Subtract(_start); } public void Start() { GC.Collect(); GC.WaitForPendingFinalizers(); _start = Process.GetCurrentProcess().Threads[0].UserProcessorTime; } } class Program { static void Main(string[] args) { int size = 9999; int[] data = new int[size]; Build(data, size); var timing = new Timing(); timing.Start(); Print(data); timing.Stop(); Console.WriteLine($"\r\nExecution time: {timing.Duration.Ticks} (ticks) = {timing.Duration.Milliseconds} (ms)"); Console.ReadKey(); } static void Build(int[] arrary, int size) { for (var i = 0; i < size; i++) { arrary[i] = i; } } static void Print(int[] array) { foreach (var i in array) Console.Write($"{i} "); } } }

Ở đây chúng ta đã xây dựng một class mới Timing sử dụng các đoạn code đã trình bày ở mục trên. Class này có hai phương thức, Start và Stop, để bắt đầu và kết thúc việc đo thời gian trên luồng chính. Trong phương thức Start chứa các lệnh làm việc với Garbage Collector và finalizer như đã phân tích. Kết quả đo sẽ trả về qua thuộc tính chỉ đọc Duration thuộc kiểu TimeSpan.

Trong lớp Program chúng ta lặp lại những gì đã thực hiện ở P01_SimpleTiming nhưng sử dụng lớp Timing để đo thời gian.

Dịch và chạy chương trình để xem kết quả.

Bạn chắc sẽ nhận xét thấy ngay là kết quả mới có giá trị nhỏ hơn nhiều so với kết quả ở ví dụ đầu tiên.

Bạn có thể thiết lập để đồng thời debug cả hai project để so sánh kết quả. Bạn có thể để ý thấy là việc in ra màn hình ở cả hai chương trình chạy với cùng một tốc độ, nhưng thời gian đo được ở P02_ProperTiming lại chỉ bằng khoảng 1/10 so với P01_SimpleTiming.

Kết luận

Trong bài học này chúng ta đã phân tích cách đánh giá thời gian thực thi của thuật toán trong .NET và xây dựng được một class hỗ trợ. Chúng ta sẽ sử dụng class này trong các bài học về thuật toán để đánh giá hiệu quả của chúng thay cho phân tích Big O.

Chúc bạn học tốt!

[wpdm_package id=’10274′]

+ Nếu bạn thấy site hữu ích, trước khi rời đi hãy giúp đỡ site bằng một hành động nhỏ để site có thể phát triển và phục vụ bạn tốt hơn.+ Nếu bạn thấy bài viết hữu ích, hãy giúp chia sẻ tới mọi người.+ Nếu có thắc mắc hoặc cần trao đổi thêm, mời bạn viết trong phần thảo luận cuối trang.Cảm ơn bạn!