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:
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
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 =)
Đâ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
nó ghi execution time là 32 giây mà ở trên 0.000 hết?
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 -_-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 =)
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 ?
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
gcc: printf and long double leads to wrong output. [C - Type conversion messes up]