In C-Sprache C #, Java8, Golang, Python3, Ich habe die Verarbeitungszeit verglichen, als die Werte im Bereich von int64 faktorisiert wurden.
Wenn Sie das Ergebnis zuerst sehen möchten, klicken Sie hier. Verarbeitungszeitliste
Für C #, Java, Golang habe ich auch mit bigint gerechnet.
Für den Primfaktorisierungsalgorithmus haben wir die einfachste Versuchsaufteilungsmethode verwendet. Ich werde versuchen zu sehen, ob es um 2,3,5,7,11,13,17, ... bricht (im Folgenden werden +2, +4 abwechselnd wiederholt).
Um den Prozess zu beschleunigen, gibt es eine Methode, um eine Tabelle mit Primzahlen zu erstellen, um zu prüfen, ob sie defekt ist oder nicht, aber im Voraus (Da die Schleifenverarbeitung von ca. 63 Bit in ca. 10 Sekunden abgeschlossen war) habe ich diesmal nicht vorbereitet.
Das folgende Beispiel zeigt die Test-Split-Verarbeitung in Java.
PrimeFactorization.java
private long[] trial_division(long n) {
List<Long> prime_list = new ArrayList<>();
long max = (long)(Math.sqrt(n)) + 1;
//Teilen Sie durch 2
while (n % 2 == 0) {
prime_list.add((long)2);
n /= 2;
}
//Teilen Sie durch 3
while (n % 3 == 0) {
prime_list.add((long)3);
n /= 3;
}
// 5 ～ Math.sqrt(n)Teilen Sie durch die Anzahl von
boolean flag = true;
for (long i = 5; i < max; ) {
while (n % i == 0) {
prime_list.add(i);
n /= i;
if (n == 1)
i = max;
}
if (flag)
i += 2;
else
i += 4;
flag = !flag;
}
if (n != 1) {
prime_list.add(n);
}
//(Im Folgenden weggelassen)
}
Für Java und Golang zusätzlich zum Typ int64 (long) Ich habe die gleiche Berechnung für den Bigint-Typ (BigInteger) versucht.
Für Python3 gibt es übrigens keine Obergrenze für Ganzzahltypen.
Die Quelle des Programms befindet sich unten. https://github.com/NobuyukiInoue/PrimeFactorization
Für die Messung der Verarbeitungszeit wurde in den folgenden Spezifikationen auch ein PC verwendet.
CPU: Intel Core-i7 8559U 2,7 GHz (4,5 GHz) 4 Kerne / 8 Threads Memory: 16GB(LPDDR3 2,133MHz) OS: Windows 10 Professional
Sogenanntes Macbook Pro 13 Zoll 2018 Modell.
Der Zielwert ist der Wert, den Sie berücksichtigen möchten. ("111 ..." ist in einer Reihe, aber es ist eine Dezimalzahl, keine Binärzahl.)
Im Fall der Versuchsaufteilungsmethode wird die Gesamtzahl der Schleifen reduziert, wenn sie durch eine kleine Primzahl wie 2,3,5, .. gebrochen wird Die Verarbeitungszeit ist nicht proportional zur Größe des Wertes.
Im Fall von int64 kann selbst bei einem Wert von ungefähr 64 Bit, wenn es sich um einen modernen PC handelt, die Primfaktorisierung innerhalb von 10 Sekunden erfolgen.
| Zielwert (Dezimalzahl) |
C Sprache long long int (Optimierungsoptionen-O3) |
C# long |
C# BigInteger |
Java long |
Java BigInteger |
Golang int64 |
Golang BigInt |
Python3 int |
|---|---|---|---|---|---|---|---|---|
| 11111111111111 (44 Bit) |
0.000[S] | 0.004[S] | 0.013[S] | 0.000[S] | 0.047[S] | 0.003[S] | 0.056[S] | 0.030[S] |
| 111111111111111 47 Bit) |
0.006[S] | 0.008[S] | 0.038[S] | 0.016[S] | 0.109[S] | 0.007[S] | 0.169[S] | 0.088[S] |
| 1111111111111111 (50 Bits) |
0.012[S] | 0.015[S] | 0.067[S] | 0.031[S] | 0.141[S] | 0.015[S] | 0.343[S] | 0.176[S] |
| 11111111111111111 (54 Bit) |
0.204[S] | 0.257[S] | 1.540[S] | 0.250[S] | 1.859[S] | 0.271[S] | Messung abbrechen (180 Sekunden oder mehr) |
5.021[S] |
| 111111111111111111 (57 Bit) |
0.001[S] | 0.002[S] | 0.007[S] | 0.000[S] | 0.031[S] | 0.001[S] | 0.022[S] | 0.016[S] |
| 1111111111111111111 (60 Bit) |
2.122[S] | 2.300[S] | 15.025[S] | 2.422[S] | 15.688[S] | 2.519[S] | Messung abbrechen (180 Sekunden oder mehr) |
48.322[S] |
| 6111111111111111111 (63 Bit) |
4.884[S] | 5.396[S] | 41.263[S] | 5.703[S] | 38.781[S] | 5.937[S] | Messung abbrechen (180 Sekunden oder mehr |
243.715[S] |
Golangs Bigint hat eine große Anzahl von Schleifen (da die Instanz während des Zuweisungsprozesses in der Schleife erstellt wird). Es dauert enorm viel Zeit.
In einigen Sprachen ist die 57-Bit-Verarbeitungszeit kürzer als die 44-Bit-Verarbeitung
Die Summe der Primfaktoren [11, 239, 4649, 909091] von 11111111111111 (44 Bit) beträgt 913990, Die Summe der Primfaktoren [3, 3, 7, 11, 13, 19, 37, 52579, 333667] von 111111111111111111 (57 Bit) beträgt 386339, Dies liegt daran, dass die Anzahl der Schleifen gering ist.
Ist es im Vergleich der Verarbeitungsgeschwindigkeit mit bigint die Reihenfolge von C #> Java> Golang?