Казалось бы, вы не можете написать статью об обычном целочисленном типе? Тем не менее, здесь все не так просто, и целое число не так очевидно.
Если вам интересно, почему x * 2 быстрее x << 1 Анкет
И как сделать следующий трюк:
>>> 42 == 4 True >>> 42 4 >>> 1 + 41 4
Тогда вы должны прочитать эту статью.
В Python нет примитивных типов – все переменные являются объектами и выделены в куче. В то же время целые числа представлены только одним типом (мы не рассматриваем десятичное значение ) – pylongobject. Он реализован в файлах LongObject.h , LonginTrepr.H и LongObject.c , вы можете увидеть это на Cpython Project Github Page Анкет
struct _longobject {
PyObject_VAR_HEAD // standard header for variable length objects
digit ob_digit [1]; // array of numbers
};
Любой объект в CPYTHON включает в себя два поля: ob_refcnt – счетчик ссылок на объект и ob_type – указатель на тип объекта; к объектам, которые могут изменить их длину, ob_size Поле добавлено – размер выделенного тока (на самом деле используемое пространство может быть меньше).
Таким образом, целочисленный тип представлен массивом переменной длины из отдельных цифр, поэтому Python поддерживает длинную арифметику из коробки, во второй версии языка был отдельный тип «обычных» целых чисел. ” Долгие «целые числа были созданы с использованием буквы L или, если результат операций между« обычными »целыми числами вызвал переполнение, в третьей версии было решено по умолчанию все целочисленное целое.
# python2 num1 = 42 print num1, type (num1) # 42num2 = 42L print num2, type (num2) # 42 num3 = 2 ** 100 print num3, type (num3) # 1267650600228229401496703205376
Целочисленное значение, хранящееся _longobject может быть представлено следующим уравнением:
Цифра-это либо 32-разрядный тип без знака ( uint32_t ) на 64-битных системах или 16-битных без подписи короткой Тип на 32-битных системах.
Алгоритмы, используемые в реализации, налагают строгие ограничения на Сдвиг Параметр из предыдущей формулы, в частности, он должен делиться на 15, поэтому сейчас CPYTHON поддерживает два значения: 30 и 15 соответственно для 64 и 32-битных систем. Для отрицательных значений ob_size Также имеет отрицательное значение, ноль устанавливается по числу.
Арифметические операции
При выполнении арифметических операций интерпретатор проверяет текущую длину операндов, если они оба состоят из одной цифры, то выполняется стандартная арифметика.
static PyObject *
long_add (PyLongObject * a, PyLongObject * b)
{
...
// both operands fit into one bit
if (Py_ABS (Py_SIZE (a)) <= 1 && Py_ABS (Py_SIZE (b)) <= 1) {
// sum them up and return the result
return PyLong_FromLong (MEDIUM_VALUE (a) + MEDIUM_VALUE (b));
}
...
};
Умножение имеет аналогичную структуру, кроме того, интерпретатор реализует алгоритм карацуба и быстрый квадрат, но они не выполняются с каждым «длинным умножением», а только для достаточно больших чисел, количество цифр, в которых установлено два константа: константы: только для достаточных цифр: количество цифр, установленных двумя константами: только для достаточно больших чисел: количество цифр, в которых установлено две константы: только для достаточно больших чисел.
// in case of unequal operands #define KARATSUBA_CUTOFF 70 // in case of squaring #define KARATSUBA_SQUARE_CUTOFF (2 * KARATSUBA_CUTOFF)
static PyObject *
long_mul (PyLongObject * a, PyLongObject * b)
{
...
// both operands fit into one bit
if (Py_ABS (Py_SIZE (a)) <= 1 && Py_ABS (Py_SIZE (b)) <= 1) {
// stwodigits is a signed type that can hold two digits
// int64_t on 64-bit systems and long on 32-bit systems.
stwodigits v = (stwodigits) (MEDIUM_VALUE (a)) * MEDIUM_VALUE (b);
return PyLong_FromLongLong ((long long) v);
}
...
// "School" long multiplication O(N ^ 2) if both operands are small enough.
i = a == b ? KARATSUBA_SQUARE_CUTOFF: KARATSUBA_CUTOFF;
if (asize <= i) {
if (asize == 0)
return (PyLongObject *) PyLong_FromLong (0);
else
return x_mul (a, b);
}
...
};
Логические операции и сравнения
Тем не менее, инструкции по смене не имеют проверки на короткие целые числа, они всегда выполняются как длинные арифметики. Следовательно, умножение на 2 оказывается быстрее, чем смещение. Интересно отметить, что разделение все еще медленнее, чем правильная смена. Правильный сдвиг также не проверяет наличие однозначных целых чисел. Но разделение более сложное: существует только одна функция как для коэффициента, так и для расчета оставшихся. NULL передается в функцию, если вам нужно рассчитать только один, поэтому функция должна проверить этот случай, все это увеличивает накладные расходы.
Функция сравнения также не имеет особого случая для «коротких» целых чисел.
static int
long_compare(PyLongObject *a, PyLongObject *b)
{
Py_ssize_t sign;
// the case, of different size integers
// just define the longest one with regards to the signs
if (Py_SIZE(a) != Py_SIZE(b)) {
sign = Py_SIZE(a) - Py_SIZE(b);
}
else {
Py_ssize_t i = Py_ABS(Py_SIZE(a));
// run cycle for integers of equal length
// for "short" integers the number of iterations will be
// less, no other optimizations are applied
while (--i >= 0 && a->ob_digit[i] == b->ob_digit[i]);
if (i < 0)
sign = 0;
else {
sign = (sdigit)a->ob_digit[i] - (sdigit)b->ob_digit[i];
if (Py_SIZE(a) < 0)
sign = -sign;
}
}
return sign < 0 ? -1 : sign > 0 ? 1 : 0;
}
При создании переменной целочисленного типа интерпретатор должен выделить достаточную область в динамической памяти, а затем установить контрольный счетчик (тип ssize_t ), указатель на Pylongobject Тип, текущий размер битового массива (также ssize_t ) и инициализируйте сам массив. Для 64-битных систем минимальный размер структуры: 2 * ssize_t + pointer + * 8 + 8 + байты Анкет Дополнительные проблемы появляются при создании списков чисел: Поскольку номера не являются примитивным типом, и списки в ссылках на Python Store на объекты, они не хранятся последовательно в куче.
Это размещение замедляется по сравнению с массивом: на самом деле выполняется случайный доступ, что делает невозможным прогнозирование переходов.
Чтобы избежать ненужных распределений динамической памяти, которая замедляет время выполнения и способствует фрагментации памяти, в CPYTHON реализуется оптимизация: на стадии запуска массив небольших целых чисел предварительно: от -5 до 256.
#ifndef NSMALLPOSINTS #define NSMALLPOSINTS 257 // As expected in python, the right border is not included. #endif #ifndef NSMALLNEGINTS #define NSMALLNEGINTS 5 #endif
В результате список чисел в CPYTHON представлен в памяти, как это:
Можно достичь предварительно выбранного списка небольших целых чисел из сценария, вооруженного Эта статья и стандарт ctypes модуль:
Отказ от ответственности. Следующий код предоставляется как есть, автор несет никакой ответственности и не может гарантировать состояние переводчика, а также психическое здоровье вас и ваших коллег, после запуска этого кода.
import ctypes
# PyLongObject structure
class IntStruct (ctypes.Structure):
# declaration of fields
_fields_ = [("ob_refcnt", ctypes.c_long),
("ob_type", ctypes.c_void_p),
("ob_size", ctypes.c_long),
("ob_digit", ctypes.c_int)]
def __repr __ (self):
return (f"IntStruct (ob_digit = {self.ob_digit}, "
f"ob_size = {self.ob_size}, "
f"refcount = {self.ob_refcnt})")
if __name__ == '__main__':
# get the address of number 42
int42 = IntStruct.from_address (id (42))
print (int42)
int_minus_2 = IntStruct.from_address (id (-2))
print (int_minus_2) # ob_digit = 2, ob_size = -1
# change the value in the list of preallocated numbers
int42.ob_digit = 4
print (4 == 42) # True
print (1 + 41) # 4
Этот список содержит честный Pylongobjects Таким образом, у них есть эталонный счетчик, например, вы можете выяснить, сколько нулей использует ваш сценарий и сам переводчик.
Это следует из внутренней реализации целых чисел, что арифметика в CPYTHON не может быть быстрой, в то время как другие языки итерации итерации последовательно над массивом, читать номера в регистры и напрямую вызывает несколько инструкций процессора, CPYTHON бросается вокруг всей памяти, выполняя довольно сложные методы. В простейшем случае с одним битом целых чисел, в котором было бы достаточно, чтобы вызвать одну инструкцию, интерпретатор должен сравнить размеры, затем создать объект в динамической памяти, заполнить все поля службы и вернуть указатель на него, Более того, эти действия требуют блокировки Гила. Теперь вы понимаете, почему была создана библиотека Numpy и почему она так популярна.
Я хотел бы закончить статью о целочисленном типе в CPYTHON, вдруг, с информацией о логическом типе.
Дело в том, что в течение долгого времени в Python не было отдельного типа для логических переменных, все логические функции возвращались 0 и 1. Однако они решили Представьте новый тип Анкет В то же время он был реализован как тип ребенка в целое число.
PyTypeObject PyBool_Type = {
PyVarObject_HEAD_INIT (& PyType_Type, 0) // the length of the boolean type cannot be changed
// however, since it inherits from integer
// there is already an ob_size field
"bool", // type name
sizeof (struct _longobject), // size in memory
...
& PyLong_Type, // base type
...
bool_new, // constructor
};
Более того, каждое из значений логического типа является синглтоном, логическая переменная является указателем на экземпляр TRUE или FALSE (ни один не реализован аналогичным образом).
struct _longobject _Py_FalseStruct = {
PyVarObject_HEAD_INIT (& PyBool_Type, 0)
{0}
};
struct _longobject _Py_TrueStruct = {
PyVarObject_HEAD_INIT (& PyBool_Type, 1)
{ 1 }
};
static PyObject *
bool_new (PyTypeObject * type, PyObject * args, PyObject * kwds)
{
PyObject * x = Py_False;
long ok;
if (! _PyArg_NoKeywords ("bool", kwds))
return NULL;
if (! PyArg_UnpackTuple (args, "bool", 0, 1, & x))
return NULL;
ok = PyObject_IsTrue (x);
if (ok <0)
return NULL;
return PyBool_FromLong (ok);
}
PyObject * PyBool_FromLong (long ok)
{
PyObject * result;
if (ok)
result = Py_True;
else
result = Py_False;
Py_INCREF (result);
return result;
}
Pyobject_istrue (x) это сложный механизм для расчета логического значения, вы можете увидеть его в Документация Анкет
Это наследование приводит к некоторым забавным эффектам, таким как точное равенство истинного и 1, невозможность иметь как истинную, так и 1 в качестве ключей в словаре и наборе, а также допустимость арифметических операций на логическом типе:
>>> True == 1
True
>>> {True: "true", 1: "one"}
{True: 'one'}
>>> True * 2 + False / (5 * True) - (True << 3)
-6.0
>>> False < -1
False
Язык Python отлично подходит для его гибкости и читаемости, однако следует иметь в виду, что все это имеет, например, цену в форме ненужных абстракций и накладных расходов, о которых мы часто не думаем или не догадываемся. Я надеюсь, что эта статья позволила вам немного развеять «туман войны» над исходным кодом интерпретатора, возможно, даже побудит вас изучать ее. Код интерпретатора очень легко читать, почти как код в самом Python, и изучение его позволит вам не только узнать, как реализуется интерпретатор, но и интересные алгоритмические и системные решения, а также, возможно, писать более эффективные кодировать или стать разработчиком самого CPYTHON.
Оригинал: “https://dev.to/artyomkaltovich/how-the-integer-type-is-implemented-in-cpython-8ei”