VS và Codeblocks cho ra kết quả khác nhau khi đo thời gian chạy của đệ quy

tcm · November 17, 2016, 7:38am

Hi mọi người,

Mình có làm bài tập tính tổng các số tự nhiên tự 1 đến n bằng đệ quy, đệ quy đuôi và khử đệ quy, sau đó đo xem thằng nào có thời gian chạy nhanh hơn.
Thì mọi người cũng biết là khử đệ quy chạy nhanh nhất, tiếp đó là đệ quy đuôi rồi mới tới đệ quy, nhưng trong CodeBlocks thì thời gian chạy luôn là … 0 !

Đây là source code: http://codepad.org/YLzRqShX

// Tính tổng 1 + 2 + 3 + ... + n
int Sum_Recursion(int n)
{
	if (n == 1)
		return 1;
	return n + Sum_Recursion(n - 1);
}
int Sum_TailRecursion(int n, int x)
{
	if (n == 1)
		return x;
	return Sum_TailRecursion(n - 1, n + x);
}
int Sum_NoRecursion(int n)
{
	int sum = 1;
	for (int i = 2; i <= n; ++i)
		sum += i;
	return sum;
}
int main()
{
	int n = 50;

	printf("Sum_Recursion(%d) = %d\n", n, Sum_Recursion(n));
	printf("Sum_TailRecursion(%d) = %d\n", n, Sum_TailRecursion(n, 1));
	printf("Sum_NoRecursion(%d) = %d\n", n, Sum_NoRecursion(n));

	clock_t start1 = clock();
	for (int i = 0; i < 10000; ++i)
		Sum_Recursion(n);
	clock_t end1 = clock();

	clock_t start2 = clock();
	for (int i = 0; i < 10000; ++i)
		Sum_TailRecursion(n, 1);
	clock_t end2 = clock();

	clock_t start3 = clock();
	for (int i = 0; i < 10000; ++i)
		Sum_NoRecursion(n);
	clock_t end3 = clock();

	double time1 = (double)(end1 - start1) / CLOCKS_PER_SEC;
	double time2 = (double)(end2 - start2) / CLOCKS_PER_SEC;
	double time3 = (double)(end3 - start3) / CLOCKS_PER_SEC;

	printf("Sum_Recursion(%d) runs %lf seconds\n", n, time1);
	printf("Sum_TailRecursion(%d) runs %lf seconds\n", n, time2);
	printf("Sum_NoRecursion(%d) runs %lf seconds\n", n, time3);

	getch();
	return 0;
}

Đoạn code trên:

Microsoft Visual Studio 2015 (Community) cho kết quả:

Code::Blocks 16.01 cho kết quả:

Nhưng hình như Code::Blocks luôn luôn cho kết quả là 0.00000... chứ không phải giờ nhích lên nổi số 1.
Cho mình hỏi vì sao lại như thế ?

Cảm ơn mọi người

tntxtnt · November 17, 2016, 2:08pm

tăng n lên 1000 là được?

10000 lần chạy, 50 lần cộng ~500k phép cộng ~ 500k clock cycles, máy có CPU 1GHz tương đương 1 tỷ clock cycles mỗi giây, 500k / 1 tỷ ~ 0.0005 giây, cho thêm cái i++ nữa là 0.001 giây đi, thêm luôn cái so sánh là 0.002 giây nữa, vậy mà chạy lên tới 0.044 giây thì chắc VS có vấn đề rồi =)

tcm · November 17, 2016, 2:14pm

Đây là thông số CPU em nà anh

Em thử tăng n lên 1k, vòng lặp trên 1 củ, thì kết quả nó vẫn chạy 0.0000 giây anh ơi

Uhm … kì nhỉ, vậy trước giờ thằng VS compile & run code của em lâu hơn CB rồi

tntxtnt · November 17, 2016, 2:23pm

nó ghi execution time là 32 giây mà ở trên 0.000 hết?

tcm · November 17, 2016, 2:26pm

Vậy nó mới bựa ấy chứ, chiều giờ mày mò mãi chả biết lỗi cho nào mà cứ 0.000... quài -_-

tntxtnt · November 17, 2016, 2:34pm

thử in %f thay vì %lf coi được ko

với lại chạy 10000 lần thôi, 1 triệu lần chờ lâu lắm =)

tcm · November 17, 2016, 2:36pm

Ok, đã sửa thành 100000 lần

Unbelievable, nó đã ra được rồi anh ơi

Ủa mà lí do vì sao thế nhỉ ? Em tưởng biến kiểu double phải dùng %lf ?

tntxtnt · November 17, 2016, 2:43pm

ko, %f xài cho float (32-bit) hay double (64-bit) cũng được. %lf là long double, có khi nó dịch là 64-bit double, có khi nó dịch là 80-bit long double, như trong trường hợp này có thể nó hiểu time1, time2… là 80-bit long double nên nó in sai kết quả rồi

The other part of this problem you’re running into is that long double in GCC is a different type than long double in MSVC. GCC uses a 96-bit or 128-bit type for long double on x86 or x64 targets (see http://gcc.gnu.org/onlinedocs/gcc/i386-and-x86_002d64-Options.html). However, MSVC uses a 64-bit type - basically long double is exactly the same as double for msvcrt.dll (http://msdn.microsoft.com/en-us/library/9cx8xs15.aspx):