Umgang mit großen Zahlen mit GMP-Stil Leistung in Go

Ich lerne Go und ich begann mit dem math/big-Paket, um mit arbitrary-length Integer umzugehen.Umgang mit großen Zahlen mit GMP-Stil Leistung in Go

Ich schrieb dieses Programm, das die n-te Fibonacci-Zahl berechnet: (entfernt die import e):

func main() { 
    imax, _ := strconv.Atoi(os.Args[1]) 
    var a, b, c big.Int 
    a.SetUint64(0) 
    b.SetUint64(1) 
    for i := 0; i < imax; i++ { 
     c.Set(&b) 
     b.Add(&b, &a) 
     a.Set(&c) 
    } 
    fmt.Println(a.String()) 
}

Hier ist der Code für das C-Programm:

int main(int argc, char** argv) 
{ 
    int imax = atoi(argv[1]); 

    mpz_t a, b, c; 
    mpz_inits(a, b, c, NULL); 
    mpz_set_ui(a, 0); 
    mpz_set_ui(b, 1); 

    int i = 0; 
    for (i = 0; i < imax; i++) { 
     mpz_swap(a, b); 
     mpz_add(b, a, b); 
    } 

    char* astr = NULL; 
    astr = mpz_get_str(NULL, 10, a); 
    printf("%s\n", astr); 

    return EXIT_SUCCESS; 
}

Das Programm Go berechnet der Ausdruck 100.000 in 0,1 Sekunden (Durchschnitt), während das C-Äquivalent unter Verwendung der GMP-Bibliothek nur in 0,04 Sekunden läuft. Das ist zweimal langsamer.

Gibt es eine Möglichkeit, die gleiche Leistung in meinem Go-Programm zu erhalten?

Quelle

2016-03-25 Arno

Ich stimme für das Schließen dieser Frage als Off-Topic, da dies eine Anforderung für eine Codeüberprüfung ist. – Olaf

Wie ist es eine Anfrage für Code Review? Ich möchte dieses * Programm nicht speziell optimieren, sondern einen Weg finden, die gleichen Fähigkeiten in den beiden Sprachen zu erhalten. Ich habe versucht, die beiden Programme so ähnlich wie möglich zu machen, um eine nicht voreingenommene Benchmark zu erhalten. Eine Antwort könnte beispielsweise eine andere arithmetische Go-Bibliothek mit beliebiger Genauigkeit sein. – Arno

Wenn Sie Operationen vergleichen möchten, müssen Sie einen reproduzierbaren Benchmark einrichten. Wir wissen nicht, wie Sie Ihren Code kompilieren und ausführen. Auf meinem System berechnet der Go-Code 10000 in ~ 55ms. – JimB

Nicht auf stdout drucken, es ist langsam. Welches Ergebnis erhalten Sie für diesen Code?

package main 

import (
    "math/big" 
    "os" 
    "strconv" 
) 

func main() { 
    max, err := strconv.Atoi(os.Args[1]) 
    if err != nil { 
     panic(err) 
    } 
    a, b := big.NewInt(0), big.NewInt(1) 
    for i := 0; i < max; i++ { 
     a.Add(a, b) 
     a, b = b, a 
    } 
}

Go ist kein handgefertigter Assemblercode.

Ihr Wert von 100.000 ist zu klein für einen zuverlässigen Benchmark. Verwenden Sie 1.000.000 oder einen anderen Wert, der für mindestens zehn Sekunden ausgeführt wird.

Quelle

2016-03-25 18:24:10 peterSO

Ich versuchte mit Imax = 1.000.000, umleiten Ausgabe nach/dev/null, und es dauerte 9 Sekunden für Go, 3,6 Sekunden für C. Der Vorteil ist ziemlich klar. Ich werde später deinen Code ausprobieren. – Arno

OK, die Ergebnisse mit Ihrem Code sind interessant. Er berechnet den 1.000.000sten Term in 4,5 Sekunden, während der C-Code (ohne Druck) 3,5 Sekunden dauert. Ich denke, die Leistung hängt von der Bibliothek ab und wird ähnlich sein, wenn ich die Go-GMP-Bindung verwende. Vielen Dank ! – Arno

Das Umleiten der Ausgabe nach '/ dev/null' hilft nicht: Das Programm muss immer noch einen Syscall machen, wenn etwas ausgegeben wird. Bitte beachten Sie die Verwendung von Benchmarking-Möglichkeiten des Standardpakets 'testing'. Und drucken Sie nichts in Ihrem Code, der bewertet wird - zumindest, wenn Sie nicht ausdrücklich I/O benchmarken – kostix

Im Allgemeinen ist GMP schneller, weil es auf Leistung ausgelegt ist. Unter der Haube, können Sie feststellen, dass es teilweise in Assembly geschrieben wird, die Funktionen Anruf Overhead reduziert, kann einige CPU-Anweisungen wie ADX und so weiter verwenden.

Wenn Sie sich um Leistung kümmern, dann könnten Sie mpz_fib_ui Routine verwenden, das wäre noch schneller, wie es von einigen Mathe Tricks gewinnt.

Die direkte Antwort auf Ihre Frage ist wahrscheinlich, einige Go-Bindung für GMP zu verwenden.

Quelle

2016-03-25 18:22:09

Umgang mit großen Zahlen mit GMP-Stil Leistung in Go

Antwort

Verwandte Themen