Python-lang-Multiplikation

Ich bin in der Notwendigkeit eines Algorithmus, der schneller als die aktuelle normale Python-lang-Multiplikation.

Versuchte ich zu finden, eine anständige Karatsuba Umsetzung, aber ich kann nicht.

def main():
    a=long(raw_input())
    if(a<0):
        a=a*-1
        a=((a*(a+1)/2)-1)
        print(-a)
    else:
        a=(a*(a+1))/2
        print(a)
main()

Wie Sie sehen, es ist nichts kompliziertes, nur ein paar Multiplikationen. Aber Sie verarbeitet werden zahlen mit bis zu 100000 Ziffern in unter 2,5 sec.

Möchte ich einige Schnipsel aus einer Funktion oder einfach nur ein link zu irgendeiner Umsetzung einer schnelleren Vermehrung Funktion, oder alles, was hilft.

Ich denke, dass Python bereits verwendet karatsuba unter der Motorhaube (ausgelöst durch eine Reihe von Ziffern)...
Python macht bereits Gebrauch karatsuba für die lange Multiplikation. Das drucken dauert wesentlich länger als die Multiplikation
Ist es ok, um print(hex(a))? Es wird viel schneller als print(a)
Haben Sie profiliert Ihre Anwendung? Sind Sie sicher, dass die Multiplikation ist der Engpass?
Ja , ich bin mir sicher, dass die Multiplikation ist das Nadelöhr, da muss ich drucken Sie es aus dem Dezimalsystem , das einzige, was noch zu verbessern Multiplikation der Geschwindigkeit.

InformationsquelleAutor Nedim | 2009-12-02

2

Haben, könnten Sie einen Blick auf die Umsetzung der DecInt Modul (Reine Python-version verfügbar ist (Toom-Cook), obwohl die am schnellsten wird es wohl sein, wenn mit gmpy).

Thans , kopierte ich die gesamte Bibliothek in meinem code , Zwickte es ein bisschen um die Größe zu reduzieren, so passt er in 64 kB und viola es funktioniert 😀
Wenn diese algorithmen sind schneller, warum sind Sie nicht in python implementiert?
die ganze Bibliothek in meinem code ein"? "reduzieren Sie die Größe, damit es [was?] passt in 64 kB"? "Bratsche"? Sie sind in der Tat sui generis": -)

InformationsquelleAutor ChristopheD
24

Ich bin der Autor des DecInt (Dezimal Integer) library, so dass ich ' ll machen ein paar Kommentare.

Den DecInt Bibliothek wurde speziell entwickelt, um die Arbeit mit sehr großen Ganzzahlen, die benötigt werden, um konvertiert zu dezimal-format. Das problem mit der Umwandlung von dezimal-format ist, dass die meisten eine beliebige Präzision Bibliotheken zum speichern von Werten im binären. Dies ist am schnellsten und effizientesten für die Nutzung von Speicher, aber die Umwandlung von Binär zu dezimal ist in der Regel langsam. Python-Binär-zu-dezimal-Konvertierung verwendet einen O(n^2) Algorithmus und wird langsam sehr schnell.

DecInt verwendet eine große radix dezimal (in der Regel 10^250) und speichert die sehr große Anzahl in Blöcken von 250 Ziffern. Die Umwandlung einer sehr großen Zahl-zu-dezimal-format läuft jetzt in O(n).

Naiv, oder der Grundschule, die Vermehrung hat eine Laufzeit von O(n^2). Python verwendet Karatsuba-Multiplikation, die hat Laufzeit O(n^1.585). DecInt verwendet eine Kombination von Karatsuba, Toom-Cook, und Nussbaumer Faltung um eine Laufzeit von O(n*ln(n)).

Obwohl DecInt hat viel höhere Aufwand, der Kombination von O(n*ln(n)) Multiplikationen und O(n) Wandlung werden schließlich schneller als Python ist O(n^1.585) Multiplikationen und O(n^2) - Konvertierung.

Da die meisten Berechnungen nicht verlangen, dass jedes Ergebnis im Dezimalformat angezeigt, fast jede beliebige Präzision Bibliothek nutzt binäre seit, dass macht die Berechnungen einfacher. DecInt Ziele eine sehr kleine Nische. Für groß genug zahlen, DecInt schneller sein wird, die für die Multiplikation und division als native Python. Wenn Sie aber nach der reinen Leistung, eine Bibliothek, wie GMPY der Schnellste ist.

Ich bin froh, Sie gefunden DecInt hilfreich.

InformationsquelleAutor casevh
9

15.9 ms auf meinem langsamen notebook. Es ist der print, die ihn verlangsamen. Umwandlung in Binär-zahlen um Dezimalzahl ist ziemlich langsam, was ein erforderlicher Schritt drucken Sie es aus. Wenn Sie brauchen, um die Ausgabe der Zahl, die Sie sollten versuchen, die DecInt ChristopheD bereits erwähnt.

DecInt langsamer tun, die vermehren sich doch machen die drucken viel schneller
```
In [34]: a=2**333000

In [35]: len(str(a))
Out[35]: 100243

In [36]: b=2**333001

In [37]: len(str(b))
Out[37]: 100244

In [38]: timeit c=a*b
10 loops, best of 3: 15.9 ms per loop
```
Hier ist ein Beispiel mit einer leicht modifizierten version des Codes. Beachten Sie, dass die Konvertierung von einer 100000-stellige Zeichenfolge zu lange schon dauert ~1sec auf diesem computer
```
In [1]: def f(a):
   ...:     if(a<0):
   ...:         a=a*-1
   ...:         a=((a*(a+1)/2)-1)
   ...:     else:
   ...:         a=(a*(a+1))/2
   ...:     return a
   ...: 

In [2]: a=3**200000

In [3]: len(str(a))
Out[3]: 95425

In [4]: timeit f(a)
10 loops, best of 3: 417 ms per loop
```
Kennen Sie einen schnelleren Weg, der Druck, die Ergebnisse auf der Konsole ?
+1: für die Messung der Leistung, bevor versuchen zu optimieren
Computer sprechen binäre. Sie können konvertieren Binär zu und von hexadezimal sehr einfach und schnell ( 4 bit gleichzeitig ). Es gibt keine Abkürzung wie die, die für die Konvertierung nach und von dezimalen, so ist es viel langsamer. Wenn Sie können Weg mit der Verwendung von hex für die Eingabe und Ausgabe, Sie brauchen das nicht diese langsamen dezimal-Konvertierungen
Danke , ich weiß, dass ich bin nicht wirklich neu in der Welt der Programmierung, die ich nur nie benutzt Python vor , dies ist das erste mal, dass ich aktiv verwendete Funktionen in python. Und ich bin gezwungen, drucken Sie es aus in dezimal.

InformationsquelleAutor John La Rooy
3

Ich schlage vor, Sie bekommen die Sage-Mathematik-tool, die hat nahezu jedes Python-math-tool immer gemacht, gerollt in einem Paket. Sehen, ob es einen schönen schnellen beliebiger Genauigkeit Mathematik-Werkzeug im Salbei, der Ihren Anforderungen entspricht.

Danke für die Antwort , aber das problem ist, dass ich einige direkte Umsetzung , keine Bibliotheken - das heißt, ich brauche die Funktion, um in der Lage sein zu nehmen 2 longs und zurück, eine Dritte in der Zeit. Ich warf einen Blick auf die Toom-Cook-Algorithmus zur Matrixmultiplikation , aber ich kann nicht finden, eine angemessene Umsetzung.
Ähmm keine Bibliotheken, also, wenn Sie eine "angemessene" Umsetzung eines anderen Algorithmus, sind Sie gehen zu hack Ihre version von Python?? Wie viel Zeit haben Sie sich vorstellen, ein Aufruf einer library routine nehmen würde?
Wenn Sie nicht wissen, dann nicht Käse Menschen aus, durch die Ablehnung Ihrer Vorschläge von Bibliotheken. "So etwas wie eine Funktion in ..." werden müsste, das in Python geschrieben, und Sie sind besorgt über die Geschwindigkeit, mit der built-in eine lange Multiplikation wird in C geschrieben???
Ich Liebe Python, aber es ist in der Tat langsamer als C-code. Es ist einfach nicht möglich zu schreiben, eine Reine Python-Funktion, um eine beliebige Präzision multiplizieren, und haben diese Funktion schneller sein als ein C-version der gleichen Funktion. Der eingebaute arbitrary-precision-integer-code in Python ist wahrscheinlich ungefähr so gut, wie Sie bekommen können schon, aber es gibt eine gewisse chance, dass eine externe Mathe-Modul (in C geschrieben) haben eine Funktion, die besser zu Ihren Bedürfnissen passt. Ich wiederhole, es ist nicht möglich für Sie zu schreiben, eine schnellere Funktion in reinem Python.
nur um klar zu sein: ein reiner Python-Funktion mit einem guten Algorithmus schlagen kann C-code mit einem schlechten Algorithmus. Aber warum gehst du davon aus, dass die built-in beliebiger Genauigkeit Ganzzahl Mathematik in Python geschrieben ist, mit einem schlechten Algorithmus? Und selbst wenn es irgendeinen anderen Algorithmus, der für deine Bedürfnisse besser, Sie werden wahrscheinlich in der Lage sein zu finden, ein ladbares Modul, geschrieben in C, Implementierung des Algorithmus (das ist, warum ich Sie genannt, Salbei). Es sei denn, es ist eine wirklich erstaunliche Algorithmus gibt, dass irgendwie niemand jemals aus einem C-Modul für Python noch, Sie nicht schlagen, C-code mit reinem Python-code.

InformationsquelleAutor steveha

Schreibe einen Kommentar

Du musst angemeldet sein, um einen Kommentar abzugeben.