🤹🏻 💸 🍡 Wie werden sehr lange Ganzzahltypen in Python implementiert? 💇🏽 👵🏽 🙎🏼

Eine Übersetzung des Artikels wurde speziell für Studenten des Python Developer- Kurses erstellt .

Wenn Sie in einer einfachen Sprache wie C schreiben, müssen Sie den richtigen Datentyp und die richtigen Qualifikationsmerkmale für Ihre Ganzzahlen auswählen. Bei jedem Schritt analysieren Sie, ob es ausreicht, sie einfach zu verwenden, intoder ob Sie sie hinzufügen longoder sogar hinzufügen müssen long double. Wenn Sie Code in Python schreiben, müssen Sie sich jedoch nicht um diese „kleinen“ Dinge kümmern, da Python mit Zahlen integerjeder Größe arbeiten kann.

Wenn Sie in C versuchen, 2 ²⁰⁰⁰⁰ mit der integrierten Funktion zu berechnen powl, erhalten Sie die Ausgabe inf.

#include <stdio.h>
#include <math.h>

int main(void) {
  printf("%Lf\n", powl(2, 20000));
  return 0;
}

$ ./a.out
inf

In Python ist es jedoch einfach, dies einfacher als je zuvor zu machen:

>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
... 6021 digits long ...
...
6309376

Es muss unter der Haube sein, dass Python etwas sehr Schönes tut, und heute werden wir herausfinden, was es tut, um mit ganzen Zahlen beliebiger Größe zu arbeiten!

Präsentation und Definition

Integer In Python ist dies eine C-Struktur, die wie folgt definiert ist:

struct _longobject {
    PyObject_VAR_HEAD
    digit ob_digit[1];
};

PyObject_VAR_HEADIst ein Makro, zu dem es erweitert PyVarObjectwird und das folgende Struktur hat:

typedef struct {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;

Andere Typen, die haben PyObject_VAR_HEAD:

PyBytesObject
PyTupleObject
PyListObject

Dies bedeutet, dass eine Ganzzahl wie ein Tupel oder eine Liste eine variable Länge hat. Dies ist der erste Schritt, um zu verstehen, wie Python die Arbeit mit riesigen Zahlen unterstützen kann. Nach der Erweiterung kann das Makro _longobjectwie folgt betrachtet werden:

struct _longobject {
    PyObject ob_base;
    Py_ssize_t ob_size; /* Number of items in variable part */
    digit ob_digit[1];
};

Es PyObjectgibt einige Metafelder in der Struktur , die für die Referenzzählung (Garbage Collection) verwendet werden. Um darüber zu sprechen, benötigen wir jedoch einen separaten Artikel. Das Feld , auf das wir diese konzentrieren ob_digitund in einem wenig ob_size.

Entschlüsselung `ob_digit`

ob_digitIst ein statisch zugewiesenes Array mit einer Einheitslänge vom Typ digit (typedef uint32_t). Da es sich um ein Array handelt, handelt es ob_digitsich in erster Linie um einen Zeiger auf eine Zahl. Daher kann es bei Bedarf mithilfe der Malloc-Funktion auf eine beliebige Länge erhöht werden. Auf diese Weise kann Python sehr lange Zahlen darstellen und verarbeiten.

In einfachen Sprachen wie C ist die Genauigkeit von Ganzzahlen normalerweise auf 64 Bit begrenzt. Python unterstützt jedoch Ganzzahlen mit beliebiger Genauigkeit . Ab Python 3 werden alle Nummern in der Form dargestellt bignumund sind nur durch den verfügbaren Systemspeicher begrenzt.

Entschlüsselung `ob_size`

ob_sizespeichert die Anzahl der Artikel in ob_digit. Python überschreibt und verwendet den Wert ob_size, um die tatsächliche Anzahl der im Array enthaltenen Elemente zu bestimmen und die Effizienz beim Zuweisen von Speicher zum Array zu erhöhen ob_digit.

Lager

Der naivste Weg, Ganzzahlen zu speichern, besteht darin, eine Dezimalstelle in einem Element des Arrays zu speichern. Dann können Operationen wie Addition und Subtraktion gemäß den Regeln der Mathematik der Grundschule ausgeführt werden.

Bei diesem Ansatz wird die Nummer 5238 folgendermaßen gespeichert:

Dieser Ansatz ist ineffizient, da bis zu 32-Bit-Ziffern (uint32_t) zum Speichern einer Dezimalstelle verwendet werden, die tatsächlich zwischen 0 und 9 liegt und mit nur 4 Bit leicht dargestellt werden kann. Wenn Sie etwas so Vielseitiges wie Python schreiben, sollte der Kernel-Entwickler noch erfinderischer sein.

Können wir es also besser machen? Natürlich hätte ich diesen Artikel sonst nicht gepostet. Schauen wir uns genauer an, wie Python eine extra lange Ganzzahl speichert.

Python-Pfad

Anstatt nur eine Dezimalstelle in jedem Element des Arrays zu speichern ob_digit, konvertiert Python Zahlen aus dem Zahlensystem mit einer Basis von 10 in Zahlen in einem System mit einer Basis von 2 ³⁰ und ruft jedes Element als Ziffer auf, deren Wert zwischen 0 und 2 ^{30-1 liegt} .

Im Hexadezimalzahlensystem bedeutet die Basis 16 ~ 2 ⁴ , dass jede "Ziffer" der Hexadezimalzahl im Dezimalzahlensystem von 0 bis 15 reicht. In Python ebenfalls eine „Zahl“ mit einer Basis von 2 ³⁰ , was bedeutet, dass die Zahl von 0 bis 2 ³⁰ - 1 = 1073741823 in Dezimalzahl variiert.

Auf diese Weise nutzt Python effizient fast den gesamten zugewiesenen Speicherplatz von 32 Bit pro Ziffer, spart Ressourcen und führt dennoch einfache Operationen aus, z. B. das Addieren und Subtrahieren auf der mathematischen Ebene der Grundschule.

Je nach Plattform verwendet Python entweder vorzeichenlose 32-Bit-Ganzzahl-Arrays oder vorzeichenlose 16-Bit-Ganzzahl-Arrays mit 15-Bit-Ziffern. Um die Operationen auszuführen, die später erläutert werden, benötigen Sie nur wenige Bits.

Beispiel: 1152921504606846976

Wie bereits erwähnt, werden für Python Zahlen in einem Basis-2 ^{30-System dargestellt} . Wenn Sie also 1152921504606846976 in eine Basisnummer mit 2 ^30- Basis konvertieren , erhalten Sie 100.

1152921504606846976 = 1 * (2 ³⁰⁾) ² + 0 * (2 ³⁰ ) ¹ + 0 * (2 ³⁰ ) ⁰

Da die ob_digitniedrigstwertige Ziffer zuerst gespeichert wird, wird sie als 001 als drei Ziffern gespeichert.

Die Struktur _longobjectfür diesen Wert enthält:

ob_size wie 3
ob_digit wie [0, 0, 1]

Ich habe eine Demo REPL die zeigen, wie Python eine ganze Zahl in sich speichert, und bezieht sich auch auf Strukturelemente , wie beispielsweise ob_size, ob_refcountusw.

Ganzzahlige lange Operationen

Nachdem wir eine klare Vorstellung davon haben, wie Python Ganzzahlen mit beliebiger Genauigkeit implementiert, ist es an der Zeit zu verstehen, wie verschiedene mathematische Operationen mit ihnen ausgeführt werden.

Zusatz

Ganzzahlen werden "in Zahlen" gespeichert, was bedeutet, dass das Hinzufügen so einfach ist wie in der Grundschule, und der Python-Quellcode zeigt uns, dass das Hinzufügen auf diese Weise implementiert wird. Eine Funktion mit einem Namen x_addin einer Datei longobject.cfügt zwei Zahlen hinzu.

...
    for (i = 0; i < size_b; ++i) {
        carry += a->ob_digit[i] + b->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    for (; i < size_a; ++i) {
        carry += a->ob_digit[i];
        z->ob_digit[i] = carry & PyLong_MASK;
        carry >>= PyLong_SHIFT;
    }
    z->ob_digit[i] = carry;
...

Das obige Code-Snippet stammt aus einer Funktion x_add. Wie Sie sehen können, durchläuft es eine Zahl nach Zahlen und fügt Zahlen hinzu, berechnet das Ergebnis und fügt einen Bindestrich hinzu.

Interessanter wird es, wenn das Ergebnis der Addition eine negative Zahl ist. Das Vorzeichen ob_sizeist ein ganzzahliges Vorzeichen. Wenn Sie also eine negative Zahl haben, ist es ob_sizeein Minus. Der Wert ob_sizemodulo bestimmt die Anzahl der Stellen in ob_digit.

Subtraktion

So wie die Addition stattfindet, findet auch die Subtraktion statt. Eine Funktion mit einem Namen x_subin der Datei longobject.csubtrahiert eine Zahl von einer anderen.

...
    for (i = 0; i < size_b; ++i) {
        borrow = a->ob_digit[i] - b->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
    for (; i < size_a; ++i) {
        borrow = a->ob_digit[i] - borrow;
        z->ob_digit[i] = borrow & PyLong_MASK;
        borrow >>= PyLong_SHIFT;
        borrow &= 1; /* Keep only one sign bit */
    }
...

Das obige Code-Snippet stammt aus einer Funktion x_sub. Darin sehen Sie, wie die Zahlen aufgezählt und die Subtraktion durchgeführt, das Ergebnis berechnet und die Übertragung verteilt wird. In der Tat ist es der Addition sehr ähnlich.

Multiplikation

Und wieder wird die Multiplikation auf die gleiche naive Weise implementiert, die wir aus den Lektionen der Mathematik in der Grundschule gelernt haben, aber sie ist nicht sehr effizient. Um die Effizienz aufrechtzuerhalten, implementiert Python den Karatsuba-Algorithmus , der zwei n-stellige Zahlen in einfachen Schritten von O (n ^log₂³ ) multipliziert .

Der Algorithmus ist nicht einfach und seine Implementierung geht über den Rahmen dieses Artikels hinaus. Sie finden seine Implementierung jedoch in Funktionen k_mul und k_lopsided_mulin der Datei longobject.c.

Abteilung und andere Operationen

Alle Operationen für Ganzzahlen sind in der Datei definiert longobject.c. Sie sind sehr einfach zu finden und zu verfolgen. Achtung: Ein detailliertes Verständnis der Arbeit jedes einzelnen von ihnen wird einige Zeit in Anspruch nehmen .

Python ordnet eine kleine Anzahl von Ganzzahlen im Speicher zwischen -5 und 256 vor. Diese Zuordnung erfolgt während der Initialisierung. Da wir die Ganzzahlen nicht ändern können (Unveränderlichkeit), sind diese vorab zugewiesenen Zahlen Singleton und werden direkt referenziert, anstatt zugewiesen zu werden. Dies bedeutet, dass Python jedes Mal, wenn wir eine kleine Nummer verwenden / erstellen, anstelle eines Verkaufs einfach einen Verweis auf die zuvor zugewiesene Nummer zurückgibt.

Eine solche Optimierung kann im Makro IS_SMALL_INTund in der Funktion get_small_intc verfolgt werden longobject.c. Python spart also viel Platz und Zeit bei der Berechnung häufig verwendeter Ganzzahlen.

Dies ist der zweite Artikel in der Python Internals-Reihe. Der erste Artikel befasste sich damit, wie ich meine Version von Python geändert habe, um sie zu erstellenmehrdeutig . Es wird Ihnen helfen, die ersten Schritte zum Verständnis des Python-Quellcodes zu unternehmen und den Weg zum Python-Kernel-Entwickler fortzusetzen.

Wenn Sie weitere ähnliche Artikel sehen möchten, abonnieren Sie meinen Newsletter und erhalten Sie diese direkt in Ihrem Posteingang. Ich schreibe jeden Freitag über Engineering, Systems Engineering und ein wenig über Programmierung. Schicken Sie mir eine E-Mail an @arpit_bhayani . Sie finden meine vorherigen Artikel auf @ arpitbhayani.me / Blogs .

Das ist alles. Wir sehen uns auf dem Kurs !

Wie werden sehr lange Ganzzahltypen in Python implementiert?