Giới thiệu
Trong một số trường hợp chúng ta cần đo thời gian thực thi của một function hay một thuật toán nào đó. Điển hình nhất là các thuật toán tìm kiếm và thuật toán sắp xếp.
Hoặc khi xử lý hình ảnh hay 1 frame trong video thì số lượng pixel là rất lớn và làm sao chúng ta biết được thời gian chúng ta xử lý chúng là bao nhiêu và hiệu quả hay không. Thì việc đó thời gian thực thì là rất cần thiết. Thư viện time.h trong C/C++ có hổ trợ cho chúng làm việc đó. Cách sử dụng thư viện này được giới thiệu ngay dưới đây.
Thư viện sử dụng
Thư viện time.h là một thư viện được xây dựng sẵn trong C. Và nó thường sử dụng để tính toán về thời gian.
Trong C/C++ để sử dụng thư viện này đơn giản chúng ta chỉ cần include thư viện này vào những file nào chúng ta cần dùng
|
1 |
#include <time.h> |
Cấu trúc dữ liệu và function trong time.h
clock(): Hàm này trả về số tick từ khi chương trình được chạy ()
clock_t: Là kiểu mà hàm clock trả về. Thực chất clock_t là kiểu unsinged long và được define như sau:
|
1 2 3 4 |
#ifndef _CLOCK_T #define _CLOCK_T typedef __darwin_clock_t clock_t; #endif /* _CLOCK_T */ |
Và
|
1 |
typedef unsigned long __darwin_clock_t; /* clock() */ |
Marco CLOCKS_PER_SEC là giá trị tick tắc đồng hồ trên 1 giây (number of clock ticks per second). Trong hệ thống 32 bit được define như sau:
|
1 |
#define CLOCKS_PER_SEC 1000000 /* [XSI] */ |
Cách sử dụng thư viện time.h để đo thời gian thực thi của function
Mô hình làm việc của chúng ta như sau:
|
1 2 3 4 5 6 7 8 9 |
#include <time.h> clock_t start, end; double cpu_time_used; start = clock(); … /* Do the work. */ end = clock(); cpu_time_used = ((double) (end - start)) / CLOCKS_PER_SEC; |
Trước function chúng ta cần đó thực thi chúng ta gọi lệnh clock() để lấy về thời gian start, và sau function chúng ta cần đo thời gian end. Sau đó chúng ta lấy hai thời gian đó trừ cho nhau mà chia cho macro CLOCKS_PER_SEC.
Dưới đây mình sẽ do thời gian thực thi của hai thuật toán đó làm interchangeSort và selectionSort.
Interchange Sort
|
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 |
// // main.c // time // // Created by NguyenNghia on 10/25/16. // Copyright © 2016 nguyennghia. All rights reserved. // #include <stdio.h> #include <time.h> #include <stdlib.h> void swap(int *num1, int *num2) { int temp; temp = *num1; *num1 = *num2; *num2 = temp; } int random_element_in_array(int a, int b){ return a + rand()%(b-a+1); } void interchangeSort(int *arr, int n){ for (int i = 0; i < n; i++) { for (int j = 1; j < n; j++) { if(arr[j] > arr[i]){ swap(&arr[j], &arr[i]); } } } } void print_array(int* arr, int n){ for (int i = 0; i < n; i++) { printf("%d\t", arr[i]); } printf("\n"); } int main(int argc, const char * argv[]) { clock_t start, end; double time_use; int n = 9999; //init data int *arr = (int*)malloc(n); for (int i = 0; i < n; i++) { arr[i] = random_element_in_array(0, n); } start = clock(); interchangeSort(arr, n); end = clock(); time_use = (double)(end - start) / CLOCKS_PER_SEC; printf("interchangeSort take %f seconds", time_use); print_array(arr, n); return 0; } |
Kết luận
Thông thường chúng ta thường rất ít khi đo thời gian thực thi của một function như thế nào. Nhưng cách này lại là một cách thực tế để đo độ phức tạp của thuật toán. Xem thuật toán của chúng ta chạy nhanh hay chậm.