Đo lường thời gian thực thi chương trình

Giới thiệu

Trong lập trình thi đấu, việc đánh giá độ phức tạp thuật toán là một kỹ năng quan trọng để lập trình viên đánh giá hiệu quả của phương án dựa trên số phép toán thực thi trong toàn bộ chương trình.

Tuy nhiên, trong một số trường hợp, người lập trình lại muốn đo được thời gian thực thi chương trình thực tế của mã nguồn bằng một số lệnh NGẮN GỌN để nhanh chóng “ước lượng” cũng như so sánh hiệu quả của 2 phương án khác nhau. Nội dung bài viết giúp người đọc có được một số mẫu hàm để thực hiện việc này dựa trên một số lệnh cơ bản, ngắn gọn và dễ dàng sử dụng trong sử dụng thường ngày.

Các mẫu chương trình được lựa chọn giới thiệu ở mức đơn giản nhất và có ví dụ tham khảo ứng dụng trong một số trường hợp.

Nguyên tắc chung

Nguyên lý chung của các phương thức đo thời gian thực thi chương trình là sử dụng các hàm lấy mốc thời gian và tính toán khoảng chênh lệch, từ đó tính toán ra theo các đơn vị mong muốn.

.....
T1 = <Lấy mốc thời gian trước khi thực thi đoạn chương trình A>
<Thực thi đoạn chương trình A>
T2 = <Lấy mốc thời gian sau khi thực thi đoạn chương trình A>
Delta = T2 - T1
<Quy đổi Delta ra đơn vị và xuất ra output>
.....

Áp dụng

Đo thời gian bằng ngôn ngữ lập trình C++

Thư viện <time.h>

#include <iostream>
#include <iomanip> 
#include <vector>
#include <time.h> // Thư viện để sử dụng hàm clock và kiểu dữ liệu clock_t

using namespace std;

int main() {
  // Lấy thời điểm bắt đầu
  clock_t start = clock();

  // Thực thi câu lệnh cần đo thời gian
  int n = 1e8;
  vector<int> arr;
  for(int i=0;i<n;i++)
    arr.push_back(i);
  // Lấy thời điểm kết thúc
  clock_t end = clock();

  // Tính thời gian thực thi
  cout<<"Make vector with "<<n<<" elements."<<endl;
  double elapsed = (double)(end - start) / CLOCKS_PER_SEC;

  // In ra thời gian thực thi
  cout<<setprecision(5)<<fixed;
  cout << "It take: " << elapsed << " second" << endl;

  return 0;
}

Output:

Make vector with 100000000 elements.
It take: 1.81894 seconds

Đo thời gian bằng ngôn ngữ lập trình Python

Thư viện time

import time

def factorial(n):
    if n == 0:
        return 1
    else:
        return n * factorial(n-1)

start_time = time.time()

factorial(100)

end_time = time.time()

delta = end_time - start_time

print(f"Execute time: {delta:.10f} s")

Output:

Calculating 100!= 1*2*3*...*100
Execute time: 0.0000257492 s