Obsługa bardzo dużych liczb w Pythonie

140

Rozważałem szybką ocenę rąk pokerowych w Pythonie. Przyszło mi do głowy, że jednym ze sposobów na przyspieszenie tego procesu byłoby przedstawienie wszystkich twarzy i kolorów kart jako liczb pierwszych i pomnożenie ich razem, aby przedstawić ręce. Odrobina:

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]

I

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

To dałoby każdemu rozdaniu wartość liczbową, która dzięki modulo mogłaby mi powiedzieć, ilu królów jest w rozdaniu lub ile kier. Na przykład dowolne rozdanie zawierające pięć lub więcej trefli podzieliłoby się równo przez 2 ^ 5; każda ręka z czterema królami podzieliłaby się równo przez 59 ^ 4 itd.

Problem polega na tym, że układ z siedmioma kartami, taki jak AcAdAhAsKdKhKs, ma wartość skrótu wynoszącą około 62,7 biliardów, co wymagałoby znacznie więcej niż 32 bity do wewnętrznej reprezentacji. Czy jest sposób na przechowywanie tak dużych liczb w Pythonie, które pozwolą mi wykonywać na nim operacje arytmetyczne?

Tak - ten Jake.
źródło
13
Czy jesteś pewien, że gdy zaczniesz przedstawiać swoje dane w ten sposób, nadal zauważysz znaczną poprawę szybkości? Zdaję sobie sprawę, że to nie odpowiada na Twoje pytania, ale nadal…
Thomi,
3
Mam sugestię: zamiast używać oddzielnych zmiennych dla wartości kart i reprezentacji, sugeruję użycie słowników. (Więc twarze = {'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} i garnitury = {'c': 2, 'd': 3, ' h ': 5,' s ': 7}.)
JAB

Odpowiedzi:

177

Python obsługuje typ liczby całkowitej „bignum”, który może pracować z dowolnie dużymi liczbami. W Pythonie 2.5+ ten typ jest wywoływany longi jest niezależny od inttypu, ale interpreter automatycznie użyje tego, który jest bardziej odpowiedni. W Pythonie 3.0+ inttyp został całkowicie usunięty.

To tylko szczegół implementacji - o ile masz wersję 2.5 lub lepszą, po prostu wykonaj standardowe operacje matematyczne, a każda liczba, która przekracza granice matematyki 32-bitowej, zostanie automatycznie (i przejrzyście) przekonwertowana na bignum.

Wszystkie krwawe szczegóły znajdziesz w PEP 0237 .

Ben Blank
źródło
2
Pytanie brzmi, czy wydajność wynikająca z używania bignum zamiast 32-bitowych liczb całkowitych przewyższa korzyści płynące z zastosowania sprytnej metody oceny rąk, której używa.
Chris Upchurch,
3
W rzeczywistości bariera między int i long została przełamana w 2.5. 3.0 całkowicie usuwa int, czyniąc long jedynym typem całkowitoliczbowym.
Ignacio Vazquez-Abrams
1
Jak duża jest duża liczba? Czy może to być PHI ^ 4000000?
Mike Caron
9
@Mike Caron - Jeśli struktura wymieniona w PEP 0237 jest dokładna, longdługości s (w cyfrach) są przechowywane jako 32-bitowe liczby całkowite bez znaku, do 4294967295 cyfr, co oznacza, że ​​mogą z łatwością przechowywać φ ** (4 * 10 ** 6 ), czyli „tylko” 832 951 cyfr. Jednak φ nie jest liczbą całkowitą, więc aby obliczyć tę liczbę, musisz użyć Decimal (zmiennoprzecinkowego bignum Pythona). Możesz longjednak później zapisać wynik .
Ben Blank,
17
@ IgnacioVazquez-Abrams Jeszcze tylko kwestia wyjaśnienia, longjest to jedyny typ liczb całkowitych w wersji 3.0, ale jest nazwany int. (A starego intjuż nie ma.)
Michael Mior
70

python obsługuje oczywiście dowolnie duże liczby całkowite :

przykład:

>>>10 ** 1000 100000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000 0000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000000 00000000000000000000000000000000000000000000000000000000

Możesz nawet otrzymać, na przykład, dużą liczbę całkowitą, fib (4000000).

Ale nadal to robi nie (na razie) obsługuje dowolnie dużą pływak !!

Jeśli potrzebujesz jednego dużego, dużego, zmiennoprzecinkowego, sprawdź moduł dziesiętny. Istnieją przykłady użycia w tych forunach: OverflowError: (34, 'Wynik jest za duży')

Inne źródło: http://docs.python.org/2/library/decimal.html

Możesz nawet użyć modułu gmpy, jeśli potrzebujesz przyspieszenia (które prawdopodobnie Cię zainteresuje): Obsługa dużych liczb w kodzie

Kolejny odnośnik: https://code.google.com/p/gmpy/

Nuno Aniceto
źródło
33

Mógłbyś to zrobić dla zabawy, ale poza tym to nie jest dobry pomysł. Nie przyspieszyłoby to niczego, co przychodzi mi do głowy.

  • Dostanie kart do ręki będzie operacją faktorowania liczb całkowitych, która jest znacznie droższa niż zwykły dostęp do tablicy.

  • Dodawanie kart polegałoby na mnożeniu i usuwaniu dzielenia kart, zarówno dużych liczb wielowyrazowych, które są operacjami droższymi niż dodawanie lub usuwanie elementów z list.

  • Rzeczywista wartość liczbowa rozdania nic ci nie powie. Aby porównać dwie ręce, musisz wziąć pod uwagę liczby pierwsze i przestrzegać zasad pokera. h1 <h2 dla takich rąk nic nie znaczy.


źródło
25

python obsługuje naturalnie dowolnie duże liczby całkowite:

In [1]: 59**3*61**4*2*3*5*7*3*5*7
Out[1]: 62702371781194950
In [2]: _ % 61**4
Out[2]: 0
Autoplektyczne
źródło
3

Interpreter Pythona zajmie się tym za Ciebie, wystarczy wykonać operacje (+, -, *, /) i będzie działać normalnie.

intWartość jest nieograniczona.

Ostrożnie podczas dzielenia, domyślnie iloraz jest zamieniany na float, ale floatnie obsługuje tak dużych liczb. Jeśli pojawi się komunikat o błędzie z informacją, że floatnie obsługuje tak dużych liczb, oznacza to, że iloraz jest zbyt duży, aby można go było zapisać float, musisz użyć podziału piętra ( //).

Ignoruje wszelkie intliczby dziesiętne występujące po przecinku, w ten sposób wynik będzie , więc możesz uzyskać wynik dużej liczby.

10//3 Wyjścia 3

10//4 wyjścia 2

Hedy
źródło
1
Jak Twoja odpowiedź odnosi się do problemu z dużymi liczbami w pytaniu?
StupidWolf
Oznacza to, że możesz po prostu wykonywać normalne operacje z dużymi liczbami, ale uważaj na podział
Hedy