تم إعداد ترجمة للمقال خصيصًا لطلاب دورة مطوري Python .
عندما تكتب بلغة منخفضة المستوى مثل C ، فأنت قلق من اختيار نوع البيانات والمؤهلات الصحيحة لأعدادك الصحيحة ، وفي كل خطوة تقوم بتحليل ما إذا كان سيكون كافياً لاستخدامها ببساطة intأو ما إذا كنت بحاجة إلى الإضافة longأو حتى long double. ومع ذلك ، عند كتابة التعليمات البرمجية في Python ، لا داعي للقلق بشأن هذه الأشياء "البسيطة" ، لأن Python يمكن أن تعمل مع أرقام من integerأي نوع .في C ، إذا حاولت حساب 2 20000 باستخدام الوظيفة المضمنة powl، فستحصل على الإخراج inf.
int main(void) {
printf("%Lf\n", powl(2, 20000));
return 0;
}
$ ./a.out
inf
ولكن في Python ، فإن تسهيل هذا الأمر أسهل من أي وقت مضى:>>> 2 ** 20000
39802768403379665923543072061912024537047727804924259387134 ...
...
... 6021 digits long ...
...
6309376
لابد أن Python تقوم بشيء جميل للغاية تحت غطاء محرك السيارة ، واليوم سنكتشف ما تفعله للعمل مع أعداد صحيحة من الحجم التعسفي!العرض والتعريف
Integer في بايثون ، هذا هو هيكل C المحدد على النحو التالي:struct _longobject {
PyObject_VAR_HEAD
digit ob_digit[1];
};
PyObject_VAR_HEADهو ماكرو ، يتم توسيعه PyVarObject، والذي له البنية التالية:typedef struct {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
} PyVarObject;
الأنواع الأخرى التي لديها PyObject_VAR_HEAD:- PyBytesObject
- PyTupleObject
- PyListObject
هذا يعني أن العدد الصحيح ، مثل tuple أو list ، له طول متغير ، وهذه هي الخطوة الأولى لفهم كيف يمكن لـ Python دعم العمل مع الأرقام العملاقة. بمجرد التوسيع ، _longobjectيمكن اعتبار الماكرو على النحو التالي:struct _longobject {
PyObject ob_base;
Py_ssize_t ob_size; /* Number of items in variable part */
digit ob_digit[1];
};
هناك PyObjectبعض الحقول الوصفية في الهيكل التي يتم استخدامها للعد المرجعي (جمع القمامة) ، ولكن من أجل التحدث عن هذا ، نحتاج إلى مقالة منفصلة. المجال الذي سنركز عليه هذا ob_digitوبعد قليل ob_size.فك التشفير ob_digit
ob_digitصفيف مخصص بشكل ثابت لطول الوحدة من النوع digit (typedef uint32_t). نظرًا لأن هذه مصفوفة ، فهي في ob_digitالمقام الأول مؤشرًا لرقم ، وبالتالي ، إذا لزم الأمر ، يمكن زيادتها باستخدام وظيفة malloc إلى أي طول. بهذه الطريقة يمكن للبايثون تمثيل ومعالجة أعداد طويلة جدًا.عادة ، في اللغات ذات المستوى المنخفض مثل C ، فإن دقة الأعداد الصحيحة تقتصر على 64 بت ، لكن Python تدعم الأعداد الصحيحة من الدقة التعسفية . بدءًا من Python 3 ، يتم عرض جميع الأرقام في النموذج bignumوهي محدودة فقط بذاكرة النظام المتاحة.فك التشفير ob_size
ob_sizeيخزن عدد العناصر في ob_digit. يتجاوز Python ثم يستخدم القيمة ob_sizeلتحديد العدد الفعلي للعناصر الموجودة في الصفيف لزيادة كفاءة تخصيص الذاكرة للصفيف ob_digit.تخزين
الطريقة الأكثر سذاجة لتخزين الأعداد الصحيحة هي تخزين رقم عشري واحد في عنصر واحد من المصفوفة ، ثم يمكن إجراء عمليات مثل الجمع والطرح وفقًا لقواعد الرياضيات من المدرسة الابتدائية.باستخدام هذا النهج ، سيتم حفظ الرقم 5238 على النحو التالي:
هذا النهج غير فعال ، حيث سنستخدم ما يصل إلى 32 بتًا من الأرقام (uint32_t) لتخزين الرقم العشري ، والذي يتراوح في الواقع من 0 إلى 9 ويمكن تمثيله بسهولة مع 4 بتات فقط ، لأنه عند كتابة شيء متعدد الاستخدامات مثل الثعبان ، يجب أن يكون مطور النواة أكثر إبداعًا.لذا ، هل يمكننا أن نفعل أفضل؟ بالطبع ، وإلا لما كنت قد نشرت هذه المقالة. دعونا نلقي نظرة فاحصة على كيفية تخزين Python لعدد صحيح طويل جدًا.مسار بايثون
بدلاً من تخزين رقم عشري واحد فقط في كل عنصر من عناصر المصفوفة ob_digit، تقوم Python بتحويل الأرقام من نظام الأرقام بقاعدة من 10 إلى أرقام في نظام بقاعدة 2 30 وتستدعي كل عنصر كرقم تتراوح قيمته من 0 إلى 2 30-1 .في نظام الأرقام السداسية العشرية ، تعني القاعدة 16 ~ 2 4 أن كل "رقم" من الرقم السداسي العشري يتراوح من 0 إلى 15 في نظام الأرقام العشري. في بايثون ، بالمثل ، "رقم" بقاعدة 2 30 ، مما يعني أن الرقم سيختلف من 0 إلى 2 30 - 1 = 1073741823 بالأرقام العشرية.بهذه الطريقة ، تستخدم Python بشكل فعال تقريبًا كل المساحة المخصصة البالغة 32 بت لكل رقم ، وتوفر الموارد ، ولا تزال تؤدي عمليات بسيطة ، مثل الإضافة والطرح على مستوى الرياضيات في المدرسة الابتدائية.اعتمادًا على النظام الأساسي ، تستخدم Python صفائف عدد صحيح غير موقعة 32 بت أو صفائف عدد صحيح غير موقعة من 16 بت مع أرقام 15 بت. لإجراء العمليات التي ستتم مناقشتها لاحقًا ، تحتاج فقط إلى عدد قليل من البتات.مثال: 1152921504606846976كما ذكرنا ، بالنسبة إلى Python ، يتم تمثيل الأرقام في نظام الأساس 2 30 ، أي إذا قمت بتحويل 1152921504606846976 إلى رقم أساسي مع 2 30 قاعدة ، فستحصل على 100.1152921504606846976 = 1 * (2 30) 2 + 0 * (2 30 ) 1 + 0 * (2 30 ) 0نظرًا لأنه ob_digitأول من يخزن الرقم الأقل أهمية ، يتم حفظه على شكل 001 في شكل ثلاثة أرقام. ستحتويبنية _longobjectهذه القيمة على:ob_size مثل 3ob_digit مثل [0 ، 0 ، 1]
لقد أنشأت REPL تجريبيًا يوضح كيف تخزن Python عددًا صحيحًا بداخلها ، وتشير أيضًا إلى أعضاء الهيكل مثل ob_size، ob_refcountوما إلى ذلك.عدد صحيح عمليات طويلة
الآن لدينا فكرة واضحة عن كيفية تنفيذ Python للأعداد الصحيحة من الدقة التعسفية ، لقد حان الوقت لفهم كيفية تنفيذ العمليات الرياضية المختلفة معهم.إضافة
يتم تخزين الأعداد الصحيحة "بالأرقام" ، مما يعني أن الإضافة بسيطة كما هو الحال في المدرسة الابتدائية ، ويظهر لنا رمز مصدر Python أن هذه هي الطريقة التي يتم بها تنفيذ الإضافة. تضيف دالة تحمل اسمًا x_addفي ملف longobject.cرقمين....
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;
...
مقتطف الرمز أعلاه مأخوذ من دالة x_add. كما ترون ، فإنه يتكرر على عدد بالأرقام ويقوم بإضافة الأرقام ، ويحسب النتيجة ويضيف الواصلة.يصبح أكثر إثارة للاهتمام عندما تكون نتيجة الجمع رقمًا سلبيًا. العلامة ob_sizeهي علامة عدد صحيح ، أي إذا كان لديك رقم سالب ، ob_sizeفسيكون ناقصًا. ob_sizeسيحدد مودولو القيمة عدد الأرقام في ob_digit.الطرح
كما يحدث الجمع ، كما يتم الطرح. تقوم دالة تحمل اسمًا x_subفي الملف longobject.cبطرح رقم واحد من الآخر....
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 */
}
...
مقتطف الرمز أعلاه مأخوذ من دالة x_sub. في ذلك ، سترى كيف يحدث تعداد الأرقام ويتم الطرح ، ويتم حساب النتيجة وتوزيع التحويل. في الواقع ، إنه مشابه جدًا للإضافة.عمليه الضرب
ومرة أخرى ، سيتم تنفيذ عملية الضرب بنفس الطريقة الساذجة التي تعلمناها من دروس الرياضيات في المدرسة الابتدائية ، ولكنها ليست فعالة للغاية. للحفاظ على الكفاءة ، تطبق Python خوارزمية Karatsuba ، التي تضرب رقمين من n رقم في O (n log 2 3 ) خطوات بسيطة.الخوارزمية ليست بسيطة وتنفيذها هو خارج نطاق هذا المقال، ولكن يمكنك العثور على تنفيذه في وظائف k_mul و k_lopsided_mulفي الملف longobject.c.الانقسام والعمليات الأخرى
يتم تحديد جميع العمليات على الأعداد الصحيحة في الملف longobject.c، وهي بسيطة للغاية للعثور على عمل كل منها وتتبعه. انتباه: إن الفهم التفصيلي لعمل كل منهم سيستغرق بعض الوقت ، لذا قم بتخزين الفشار مسبقًا .يقوم Python بتحديد موقع عدد صغير من الأعداد الصحيحة في الذاكرة التي تتراوح من -5 إلى 256. يحدث هذا التخصيص أثناء التهيئة ، وبما أننا لا نستطيع تغيير الأعداد الصحيحة (عدم الثبات) ، فإن هذه الأرقام المخصصة مسبقًا تكون فردية ويتم الرجوع إليها مباشرة بدلاً من تخصيصها. هذا يعني أنه في كل مرة نستخدم فيها / ننشئ رقمًا صغيرًا ، تقوم Python بدلاً من بيعه بإرجاع مرجع إلى الرقم المخصص مسبقًا.يمكن تتبع هذا التحسين في الماكرو IS_SMALL_INTوالوظيفة get_small_intج longobject.c. لذا توفر Python الكثير من المساحة والوقت في حساب الأرقام الصحيحة المستخدمة بشكل شائع.هذه هي المقالة الثانية في سلسلة Python Internals. كانت المقالة الأولى حول كيفية تغيير إصدار Python الخاص بي لجعلهغامض . سيساعدك على اتخاذ الخطوات الأولى في فهم شفرة مصدر Python ومواصلة الطريق لتصبح مطورًا لـ Python kernel.إذا كنت ترغب في رؤية المزيد من المقالات المتشابهة ، اشترك في رسالتي الإخبارية واستلمها مباشرة في بريدك الوارد. أكتب عن الهندسة وهندسة النظم وقليلاً عن البرمجة كل يوم جمعة. أرسل لي على arpit_bhayani . يمكنك العثور على مقالاتي السابقة على @ arpitbhayani.me / المدونات .هذا كل شئ. نراكم في الدورة !