Optimierung von Bigint-Aufrufen

Question

Ich verwende derzeit das Buch 'Programmieren in D' zum Lernen von D. Ich habe versucht, ein Problem der Aufsummierung der Quadrate von Zahlen von 1 bis 10000000 zu lösen. Ich habe zuerst einen funktionalen Ansatz zur Lösung des Problems gemacht die Karte und reduzieren, aber wenn die Zahlen größer werden, muss ich die Zahlen in bigint umwandeln, um die richtige Ausgabe zu erhalten.

Die oben genannten dauert 7s zu beenden, wenn mit dmd -O kompiliert. Ich profilierte das Programm und die meiste Zeit wird für BigInt Anrufe verschwendet. Obwohl das Quadrat der Zahl in eine lange passen kann, muss ich sie in bigint umwandeln, so dass Funktionssummen reduziert werden und die entsprechende Summe zurückgegeben wird. Das Python-Programm benötigt nur 3 Sekunden, um es zu beenden. Wenn num = 100000000 D ist, wird das Programm auf 1 Minute und 13 Sekunden beendet. Gibt es eine Möglichkeit, die Aufrufe von bigint zu optimieren? Die Produkte können selbst lang sein, aber sie müssen als Bigint-Objekte typisiert werden, damit sie die richtigen Ergebnisse durch Reduzieren von Operationen erhalten. Ich habe versucht, das Quadrat der Zahlen in ein bigint Array zu schieben, aber es ist auch langsamer. Ich habe versucht, alle Zahlen wie Bigint

auto bigs_map_nums = iota(1,num).map!(a => to!BigInt(a)).array; 
auto bigs_map = sum(bigs_map_nums.map!(a => (a * a)).array); 

Typcasting einzugeben. Aber es ist auch langsamer. Ich habe die Antworten unter How to optimize this short factorial function in scala? (Creating 50000 BigInts) gelesen. Ist es ein Problem mit der Implementierung der Multiplikation für größere ganze Zahlen in D zu? Gibt es eine Möglichkeit, die Funktionsaufrufe für BigInt zu optimieren?

Python Code:

timeit.timeit('print sum(map(lambda num : num * num, range(1,10000000)))',number=1) 
333333283333335000000 
3.58552622795105 

Der Code auf einem Dual-Core 64-Bit-Linux Laptop mit 2 GB RAM durchgeführt wurde. python: 2.7.4 dmd: DMD64 D Compiler v2.066.1

Answer 1

Ohne Bereich Kühle: foreach(x; 0 .. num) result += x * x;

Mit Bereich kühler ness (?):

import std.functional: reverseArgs; 
result = iota(1, num) 
    .map!(a => a * a) 
    .reverseArgs!(reduce!((a, b) => a + b))(BigInt(0) /* seed */); 

Der Schlüssel BigInt zu vermeiden ist, jedes Element natürlich.

Die Bereichsversion ist etwas langsamer als die Nicht-Bereichsversion. Beide sind deutlich schneller als die Python-Version.

Bearbeiten: Oh! Oh!

result = iota(1, num) 
    .map!(a => a * a) 
    .sum(BigInt(0)); 

Answer 2

Das DMD-Backend gibt keinen stark optimierten Code aus. Für schnelle Programme kompilieren Sie mit GDC oder LDC.

Auf meinem Computer, erhalte ich diese Timings:

Python:     3.01 
dmd -O -inline -release: 3.92 
ldmd2 -O -inline -release: 2.14 

Answer 3

Die Python-Code ist nicht gleichbedeutend mit dem D-Code in der Tat macht es viel weniger: Es kann viel angenehmer mit std.algorithm.sum gemacht werden.

Python verwendet ein int, dann fördert es das int zu long(), wenn das Ergebnis größer ist als das, was in einem int() - Typ gespeichert werden kann. Intern verwendet (zumindest CPython) eine lange Zahl, um eine Ganzzahl größer als 256 zu speichern, was mindestens 32 Bit entspricht. Bis zu diesem Überlauf können normale CPU-Befehle für die Multiplikation verwendet werden, die ziemlich schnell sind als die Bigint-Multiplikation.

Die BigInt-Implementierung von D behandelt die Zahlen von Anfang an als BigInt und verwendet die teure Multiplikationsoperation von 1 bis zum Ende. Viel mehr Arbeit ist dort zu erledigen.

Es ist interessant, wie kompliziert die Multiplikation sein kann, wenn wir über BigInts sprechen.

Die D-Implementierung ist

https://github.com/D-Programming-Language/phobos/blob/v2.066.1/std/internal/math/biguintcore.d#L1246

Python beginnt von

tun

static PyObject * 
int_mul(PyObject *v, PyObject *w) 
{ 
    long a, b; 
    long longprod;      /* a*b in native long arithmetic */ 
    double doubled_longprod;   /* (double)longprod */ 
    double doubleprod;     /* (double)a * (double)b */ 

    CONVERT_TO_LONG(v, a); 
    CONVERT_TO_LONG(w, b); 
    /* casts in the next line avoid undefined behaviour on overflow */ 
    longprod = (long)((unsigned long)a * b); 

    ... //check if we have overflowed 


    { 
     const double diff = doubled_longprod - doubleprod; 
     const double absdiff = diff >= 0.0 ? diff : -diff; 
     const double absprod = doubleprod >= 0.0 ? doubleprod : 
           -doubleprod; 
     /* absdiff/absprod <= 1/32 iff 
      32 * absdiff <= absprod -- 5 good bits is "close enough" */ 
     if (32.0 * absdiff <= absprod) 
      return PyInt_FromLong(longprod); 
     else 
      return PyLong_Type.tp_as_number->nb_multiply(v, w); 
    } 
} 

und wenn die Zahl ist größer als das, was eine lange halten kann es eine Karatsuba-Multiplikation der Fall ist. Die Umsetzung in:

http://svn.python.org/projects/python/trunk/Objects/longobject.c (k_mul Funktion)

Der entsprechende Code würde warten BigInts zu verwenden, bis sie keine nativen Datentypen sind, die die Anzahl in Frage halten kann.