01/10/2018, 00:47

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

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, Sum_Recursion(n));
	printf("Sum_TailRecursion(%d) = %d
", n, Sum_TailRecursion(n, 1));
	printf("Sum_NoRecursion(%d) = %d
", 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, time1);
	printf("Sum_TailRecursion(%d) runs %lf seconds
", n, time2);
	printf("Sum_NoRecursion(%d) runs %lf seconds
", 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

    viết 02:57 ngày 01/10/2018

    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 =)

    Người bí ẩn viết 02:58 ngày 01/10/2018

    Đâ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

    chắc VS có vấn đề rồ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

    viết 02:53 ngày 01/10/2018

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

    Người bí ẩn viết 02:51 ngày 01/10/2018

    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 -_-

    viết 03:02 ngày 01/10/2018

    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 =)

    Người bí ẩn viết 02:53 ngày 01/10/2018

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

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

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

    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 ?

    viết 02:58 ngày 01/10/2018

    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

    stackoverflow.com
    Niklas R

    gcc: printf and long double leads to wrong output. [C - Type conversion messes up]

    c, gcc
    asked by Niklas R on 08:38PM - 20 Aug 11

    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):

    Bài liên quan
    0