Domanda Perché questo codice Ruby è molto più veloce del codice C ++ equivalente?


Recentemente ho affrontato alcuni semplici problemi del progetto Euler e li ho risolti in Ruby e C ++. Ma per Problema 14 riguardo alla congettura di Collatz, il mio codice C ++ è andato avanti per circa mezz'ora prima che lo interrompessi, anche se quando ho tradotto il codice in Ruby, l'ho risolto in nove secondi.

Questa differenza mi sembra incredibile: sono sempre stato portato a credere che il C ++ fosse quasi sempre più veloce di Ruby, specialmente per i processi matematici.

Il mio codice è il seguente.

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;
}

Tempo di esecuzione - sinceramente non lo so, ma è davvero molto lungo.

e 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

Tempo di esecuzione - circa 9 secondi.

Qualche idea su cosa sta succedendo qui?

Post scriptum il codice C ++ è molto più veloce del codice Ruby finché non raggiunge 100.000.


20
2018-05-08 19:25


origine


risposte:


Stai traboccando int, quindi non sta terminando. Uso int64_t invece di int nel tuo codice c ++. Probabilmente dovrai includere stdint.h per quello..


33
2018-05-08 19:30



Nel tuo caso il problema era un bug nell'implementazione C ++ (overflow numerico).

Nota comunque che il trading in qualche memoria puoi ottenere il risultato molto più velocemente di quello che stai facendo ...

Suggerimento: supponiamo di scoprire che dal numero 231 hai bisogno di 127 passaggi per terminare il calcolo, e supponi che partendo da un altro numero arrivi a 231 dopo 22 passaggi ... quanti altri passi devi fare?


3
2018-05-08 21:05



Con l'aritmetica a 32 bit, il codice C ++ si riempie a = 3*a + 1. Con l'aritmetica a 32 bit con segno, il problema è aggravato, perché il a /= 2 la linea conserverà il bit del segno.

Questo rende molto più difficile a mai uguale a 4, e in effetti quando b raggiunge 113383, a trabocca e il ciclo non finisce mai.

Con l'aritmetica a 64 bit non c'è overflow, perché a al massimo a 56991483520, quando b è 704511.

Senza guardare la matematica, suppongo che l'aritmetica a 32 bit senza segno "funzionerà" probabilmente, perché la moltiplicazione e la divisione senza segno funzioneranno entrambi modulo 2 ^ 32. E dato il breve tempo di esecuzione del programma, i valori non copriranno troppo lo spettro a 64 bit, quindi se un valore è uguale a 4 modulo 2 ^ 32, è "probabilmente" effettivamente uguale a 4.


3
2018-05-08 23:45