Umgang mit sehr großen Zahlen in Python

139

Ich habe über eine schnelle Bewertung der Pokerhand in Python nachgedacht. Mir kam der Gedanke, dass eine Möglichkeit, den Prozess zu beschleunigen, darin besteht, alle Kartenflächen und Farben als Primzahlen darzustellen und sie zu multiplizieren, um die Hände darzustellen. Zu wissen:

class PokerCard:
    faces = '23456789TJQKA'
    suits = 'cdhs'
    facePrimes = [11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 53, 59, 61]
    suitPrimes = [2, 3, 5, 7]

UND

    def HashVal(self):
      return PokerCard.facePrimes[self.cardFace] * PokerCard.suitPrimes[self.cardSuit]

Dies würde jeder Hand einen numerischen Wert geben, der mir durch Modulo sagen könnte, wie viele Könige in der Hand sind oder wie viele Herzen. Zum Beispiel würde jede Hand mit fünf oder mehr Schlägern gleichmäßig durch 2 ^ 5 teilen; Jede Hand mit vier Königen würde sich gleichmäßig durch 59 ^ 4 usw. teilen.

Das Problem ist, dass eine Hand mit sieben Karten wie AcAdAhAsKdKhKs einen Hash-Wert von ungefähr 62,7 Billiarden hat, was eine interne Darstellung erheblich mehr als 32 Bit erfordern würde. Gibt es eine Möglichkeit, so große Zahlen in Python zu speichern, dass ich arithmetische Operationen ausführen kann?

Ja - dieser Jake.
quelle
13
Sind Sie sicher, dass Sie, sobald Sie Ihre Daten auf diese Weise darstellen, immer noch eine signifikante Geschwindigkeitsverbesserung feststellen werden? Mir ist klar, dass dies Ihre Fragen nicht beantwortet, aber dennoch ..
Thomi
3
Ich habe einen Vorschlag: Anstatt separate Variablen für die Kartenwerte und die Darstellungen zu verwenden, schlage ich vor, Wörterbücher zu verwenden. (Also Gesichter = {'2': 11, '3': 13, '4': 17, '5': 19, '6': 23, '7': 29, '8': 31, '9' : 37, 'T': 41, 'J': 43, 'Q': 53, 'K': 59, 'A': 61} und Anzüge = {'c': 2, 'd': 3, ' h ': 5,' s ': 7}.)
JAB

Antworten:

176

Python unterstützt einen Integer-Typ "bignum", der mit beliebig großen Zahlen arbeiten kann. In Python 2.5+ wird dieser Typ aufgerufen longund ist vom intTyp getrennt, aber der Interpreter verwendet automatisch den geeigneten Typ. In Python 3.0+ wurde der intTyp vollständig gelöscht.

Dies ist jedoch nur ein Implementierungsdetail. Solange Sie Version 2.5 oder besser haben, führen Sie einfach Standard-Mathematikoperationen aus, und jede Zahl, die die Grenzen der 32-Bit-Mathematik überschreitet, wird automatisch (und transparent) in ein Bignum konvertiert.

Sie finden alle wichtigen Details in PEP 0237 .

Ben Blank
quelle
2
Die Frage ist, ob der Leistungsverlust durch die Verwendung von Bignum anstelle von 32-Bit-Ganzzahlen den Leistungsvorteil der von ihm verwendeten cleveren Methode der Handbewertung übersteigt.
Chris Upchurch
3
Tatsächlich wurde die Barriere zwischen int und long in 2.5 durchbrochen. 3.0 entfernt int insgesamt und macht long zum einzigen Integer-Typ.
Ignacio Vazquez-Abrams
1
Wie groß ist eine große Zahl? Kann es PHI ^ 4000000 sein?
Mike Caron
9
@Mike Caron - Wenn die in PEP 0237 aufgeführte Struktur korrekt ist, werden longdie Längen von s (in Ziffern) als vorzeichenlose 32-Bit-Ganzzahlen mit bis zu 4.294.967.295 Ziffern gespeichert, was bedeutet, dass sie leicht φ ** (4 * 10 ** 6) enthalten können ), was "nur" 832.951 Stellen ist. Da φ jedoch keine Ganzzahl ist, müssen Sie zur Berechnung der Zahl eine Dezimalzahl (Pythons Gleitkomma-Bignum) verwenden. Sie können das Ergebnis longjedoch später speichern .
Ben Blank
17
@ IgnacioVazquez-Abrams Nur ein Punkt der Klarstellung, longist der einzige ganzzahlige Typ in 3.0, aber er heißt int. (Und der alte intist weg.)
Michael Mior
70

Python unterstützt natürlich beliebig große ganze Zahlen :

Beispiel:

>>>10 ** 1000 100000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000

Sie könnten sogar beispielsweise einen riesigen ganzzahligen Wert erhalten, fib (4000000).

Aber immer noch tut es nicht (bis jetzt) unterstützt eine beliebig große Schwimmer !!

Wenn Sie einen großen, großen Float benötigen, überprüfen Sie das Dezimalmodul. Es gibt Beispiele für die Verwendung in diesen Foren: OverflowError: (34, 'Ergebnis zu groß')

Eine weitere Referenz: http://docs.python.org/2/library/decimal.html

Sie können das gmpy-Modul sogar verwenden, wenn Sie eine Beschleunigung benötigen (was wahrscheinlich von Interesse ist): Umgang mit großen Zahlen im Code

Eine weitere Referenz: https://code.google.com/p/gmpy/

Nuno Aniceto
quelle
32

Sie könnten dies zum Spaß tun, aber ansonsten ist es keine gute Idee. Es würde nichts beschleunigen, was mir einfällt.

  • Das Erhalten der Karten in der Hand ist eine ganzzahlige Faktorisierungsoperation, die viel teurer ist als nur der Zugriff auf ein Array.

  • Das Hinzufügen von Karten wäre eine Multiplikation und das Entfernen der Kartenteilung, beides großer Mehrwortnummern, die teurer sind als das Hinzufügen oder Entfernen von Elementen aus Listen.

  • Der tatsächliche numerische Wert einer Hand sagt nichts aus. Sie müssen die Primzahlen berücksichtigen und die Pokerregeln befolgen, um zwei Hände zu vergleichen. h1 <h2 bedeutet für solche Hände nichts.


quelle
25

Python unterstützt natürlich beliebig große ganze Zahlen:

In [1]: 59**3*61**4*2*3*5*7*3*5*7
Out[1]: 62702371781194950
In [2]: _ % 61**4
Out[2]: 0
Autoplektisch
quelle
3

Der Python-Interpreter erledigt das für Sie, Sie müssen nur Ihre Operationen ausführen (+, -, *, /) und es funktioniert wie gewohnt.

Der intWert ist unbegrenzt.

Vorsicht bei der Division. Standardmäßig wird der Quotient in "Quotient" umgewandelt float, unterstützt jedoch floatkeine so großen Zahlen. Wenn Sie eine Fehlermeldung erhalten, die besagt, floatdass so große Zahlen nicht unterstützt werden, bedeutet dies, dass der Quotient zu groß ist, um darin gespeichert zu werden. floatSie müssen die Etagenunterteilung ( //) verwenden.

Auf diese Weise wird jede Dezimalstelle ignoriert, die nach dem Dezimalpunkt steht. Auf diese Weise wird das Ergebnis angezeigt int, sodass Sie ein Ergebnis mit einer großen Anzahl erhalten können.

10//3 Ausgänge 3

10//4 Ausgänge 2

Hedy
quelle
1
Wie geht Ihre Antwort auf das Problem mit großen Zahlen in der Frage ein?
StupidWolf
Es bedeutet, dass Sie nur die normalen Operationen mit großen Zahlen ausführen können, aber vorsichtig mit der Teilung sein müssen
Hedy