Tại sao mã Ruby này nhanh hơn mã C++ tương đương?

Question

Gần đây tôi đã đi qua một số dự án Euler dễ dàng và giải quyết chúng trong Ruby và C++. Nhưng đối với Problem 14 liên quan đến giả thuyết Collatz, mã C++ của tôi tiếp tục trong khoảng nửa giờ trước khi tôi chấm dứt nó, mặc dù khi tôi dịch mã thành Ruby, nó đã giải quyết nó trong chín giây.

Sự khác biệt đó là điều không thể tin được đối với tôi - tôi luôn được tin rằng C++ gần như luôn nhanh hơn Ruby, đặc biệt đối với quy trình toán học.

Mã của tôi như sau.

C++:

#include <iostream> 

using namespace std; 

int main() 
{ 
    int a = 2; 
    int b = 2; 
    int c = 0; 
    while (b < 1000000) 
    { 

     a = b; 
     int d = 2; 
     while (a != 4) 
     { 
      if (a % 2 == 0) 
       a /= 2; 
      else 
       a = 3*a + 1; 
      d++; 
     } 
     if (d > c) 
     { 
      cout << b << ' ' << d << endl; 
      c=d; 
     } 
     b++; 
    } 
    cout << c; 
    return 0; 
} 

Run thời gian - Thực sự tôi không biết, nhưng đây là thời điểm thực sự REALLY dài.

và Ruby:

#!/usr/bin/ruby -w 

    a = 0 
    b = 2 
    c = 0 
    while b < 1000000 
     a = b; 
     d = 2 
     while a != 4 
      if a % 2 == 0 
       a /= 2 
      else 
       a = 3*a + 1 
      end 
      d+=1 
     end 
     if d > c 
      p b,d 
      c=d 
     end 
     b+=1 
    end 
    p c 

Run thời gian - khoảng 9 giây.

Bất kỳ ý tưởng gì đang xảy ra ở đây?

P.S. mã C++ chạy một giao dịch tốt hơn mã Ruby cho đến khi nó đạt đến 100.000.

Answer 1

Bạn đang quá tải int, vì vậy nó không bị chấm dứt. Sử dụng int64_t thay vì int trong mã C++ của bạn. Có thể bạn sẽ cần phải bao gồm stdint.h cho điều đó ..

Answer 2

Trong trường hợp của bạn, sự cố là lỗi trong triển khai C++ (tràn số).

Lưu ý tuy nhiên đó giao dịch ở một số bộ nhớ bạn có thể nhận được kết quả nhanh hơn nhiều hơn bạn đang làm ...

Gợi ý: giả sử bạn thấy rằng từ số 231 bạn cần 127 bước để kết thúc việc tính toán, và giả sử bắt đầu từ một số khác bạn nhận được 231 sau 22 bước ... bạn cần phải thực hiện bao nhiêu bước nữa?

Answer 3

Với số học 32 bit, mã C++ tràn trên a = 3*a + 1. Với số học 32 bit đã ký, vấn đề là phức tạp, vì đường dây a /= 2 sẽ giữ lại bit dấu.

Điều này làm cho khó hơn nhiều đối với a đến 4 bằng và thực sự khi b đạt tới 113383, a tràn và vòng lặp không bao giờ kết thúc.

Với 64-bit số học không có tràn, vì a maxes out at 56991483520, khi b là 704511.

Nếu không nhìn vào toán học, tôi suy đoán rằng unsigned 32-bit số học sẽ "có thể" làm việc, bởi vì phép nhân và unsigned phân chia cả hai sẽ làm việc modulo 2^32. Và với thời gian chạy ngắn của chương trình, các giá trị sẽ không bao quát quá nhiều quang phổ 64 bit, vì vậy nếu giá trị bằng 4 modulo 2^32, thì "có thể" thực sự bằng 4.