Ktl-icon-tai-lieu

Hàm thời gian và hàm ngẫu nhiên

Được đăng lên bởi Mỹ Xuân
Số trang: 3 trang   |   Lượt xem: 167 lần   |   Lượt tải: 0 lần
Cấu Trúc Dữ Liệu
Đại Học Khoa Học Tự Nhiên Tp.HCM
227 Nguyễn Văn Cừ, Q5

GV Soạn: Lê Ngọc Thành
E-mail: lnthanh@fit.hcmuns.edu.vn


ĐO THỜI GIAN THỰC THI
VÀ TẠO DỮ LIỆU NGẪU NHIÊN
1. Đo thời gian thực thi
Một trong số các hàm của Visual C++ dùng để đo thời gian thực thi của chương trình là
hàm GetTickCount(). Hàm này trả về thời gian từ khi hệ thống được bắt đầu theo đơn vị
phần triệu giây (millisecond). Một cách hiểu đơn giản là mỗi lần gọi hàm này ta sẽ có được
thời gian hệ thống chính xác đến phần triệu giây. Do đó, để đo thời gian thực thi thuật toán
người ta thường đặt hàm này ở hai vị trí; một là tại nơi trước khi thuật toán bắt đầu chạy,
hai là tại nơi thuật toán hoàn thành. Khoảng cách giữa hai thời điểm đó cho ta thời gian
chạy.
GetTickCount()

t1

∆t = t2 – t1

Thuật toán ….

GetTickCount()

Thư viện: Windows.h
Hàm: DWORD GetTickCount(VOID);
Ví dụ:
#include "windows.h"
..............
//Lấy thời điểm bắt đầu
unsigned long t1= GetTickCount();
//Đoạn chương trình cần đo
int sum = 0;
for (int i = 0; i < 100*100; i++)
sum += i;
//Lấy thời điểm kết thúc
unsigned long t2 = GetTickCount();
-1-

t2

//Thời gian là hiệu của hai thời điểm
unsigned long t = t2 - t1;
Lưu ý:

-

Thời gian lúc chạy debug từng bước sẽ khác với lúc thực thi chương trình (lí do?).

-

Ngoài ra còn có nhiều hàm khác để đo thời gian, tham khảo thêm trong MSDN

2. Tạo dữ liệu ngẫu nhiên
Hiện tại máy tính chưa thể tạo ra một số ngẫu nhiên thực sự mà chỉ tạo ra một số giả ngẫu
nhiên (pseudo-random number). Điều kiện cần để tạo ra số ngẫu nhiên là cung cấp một
trạng thái bắt đầu hay hạt giống (seed). Hạt giống không tốt (quá đơn giản, hay y hệt nhau
của hai quá trình phát sinh số ngẫu nhiên, …) có thể gây ra sự giống nhau ở kết quả (tùy
thuộc vào thuật toán và phạm vi ngẫu nhiên). Để tạo một hạt giống tốt người ta thường lấy
thời gian của hệ thống. Tham khảo thêm trong Wikipedia (Pseudorandom number
generator)
Tạo hạt giống
Khởi tạo hàm phát sinh
ngẫu nhiên từ hạt giống
Phát sinh số ngẫu
nhiên thứ i
i = 1, 2, …, 100

Tiến trình phát sinh 100 số ngẫu nhiên

Thư viện : time.h
Hàm lấy thời gian hệ thống (giây): time_t time ( time_t * timer );
Thư viện: stdlib.h
Hàm khởi tạo: void srand ( unsigned int seed );
Hàm phát sinh số nguyên trong khoảng từ 0 đến RAND_MAX: int rand ( void );
(RAND_MAX phụ thuộc vào thư viện cstdlib, mặc định là 32767)
Ví dụ:
#include <stdlib.h>
#include <time.h>
……..
-2-

//Khởi tạo hạt giống ngẫu nhiên
srand ( time(NULL) );
//Phát s...
- 1 -
Cấu Trúc Dữ Liệu
Đi Học Khoa Học Tự Nhiên Tp.HCM
227 Nguyễn Văn Cừ, Q5
GV Soạn: Lê Ngọc Thành
E-mail: lnthanh@fit.hcmuns.edu.vn
http://courses.cs.hcmuns.edu.vn
ĐO THỜI GIAN THỰC THI
TẠO DỮ LIỆU NGẪU NHIÊN
1. Đo thời gian thực thi
Một trong số các m của Visual C++ dùng để đo thời gian thực thi của chương trình
hàm GetTickCount(). m này trả vthời gian từ khi hệ thống được bắt đầu theo đơn vị
phần triệu giây (millisecond). Một cách hiểu đơn giản là mỗi lần gọi hàm này ta sẽ có được
thời gian hệ thống chính xác đến phần triệu giây. Do đó, để đo thời gian thực thi thuật toán
người ta thường đặt m này hai vị trí; một tại nơi trước khi thuật toán bắt đầu chạy,
hai tại nơi thuật toán hoàn thành. Khoảng cách giữa hai thời điểm đó cho ta thời gian
chạy.
Thư viện: Windows.h
Hàm: DWORD GetTickCount(VOID);
dụ:
#include "windows.h"
..............
//Lấy thời điểm bắt đầu
unsigned long t1= GetTickCount();
//Đoạn chương trình cần đo
int sum = 0;
for (int i = 0; i < 100*100; i++)
sum += i;
//Lấy thời điểm kết thúc
unsigned long t2 = GetTickCount();
GetTickCount()
GetTickCount()
Thuật toán ….
t
1
t
2
∆t = t
2
t
1
Hàm thời gian và hàm ngẫu nhiên - Trang 2
Hàm thời gian và hàm ngẫu nhiên - Người đăng: Mỹ Xuân
5 Tài liệu rất hay! Được đăng lên bởi - 1 giờ trước Đúng là cái mình đang tìm. Rất hay và bổ ích. Cảm ơn bạn!
3 Vietnamese
Hàm thời gian và hàm ngẫu nhiên 9 10 459