در اعماق پایتون ۱ - چگونگی مدیریت لیست ها در پایتون

مقدمهتو دنیای کامپیوتر یکسری ابزار داریم که با اون ها کار هامون رو انجام میدیم مثل زبان های برنامه نویسی. بیایید یه کمی ساده تر حرف بزنیم فک کنید که شما میخواید پریز خونتون رو عوض کنید , ازچه ابزاری استفاده میکنید؟ درسته فازمتر. پیچ هارو با فارمتر باز میکنید, پریز جدید رو قرار میدید و پیچ هارو میبندید تهش هم با همون فازمتر امتحان میکنید ببینید برق داره یا نه. زبان های برنامه نویسی هم مثل همون فازمترن. ازشون استفاده میکنیم تا به اهدافمون (که همون تعویض پریزه) برسیم. حالا ما توی سری در اعماق پایتون میخوایم ببینیم خود این ابزار چگونه کار میکنه. تو این سری باید یه کمی سی, و پایتون بلد باشید. البته من تمام سعی خودم رو کردم که همه چیز رو ساده و روون توضیح بدم اما برای درک عمیق موضوع خیلی نیازتون میشه. نکته بعدی اینه که پایتون چند تا مفسر داره مثل CPython, PyPy, pythonnet, jython و... ما در اینجا از مشهور ترین مفسر پایتون یعنی همونی که اکثرمون استفاده میکنیم یعنی CPython استفاده میکنیم.لیست ها در پایتوناول از همه خیلی کوتاه و مختر ببینیم لیست توی پایتون چیه؟لیست خیلی خیلی ساده بخوایم بگیم مجموعه ای چیزهاست (جلوتر میبینیم این چیز ها همشون آبجکت هستن)مثلا لیست A:A = [1, 2.3, 'a', 'HI']همون طور که میدونیم پایتون در مفسر CPython با زبان برنامه نویسی C ساخته شده. یعنی لیست ها در پایتون با C پیاده شدن. حالا بریم ببینیم که لیست ها یا خیلی رسمی تر آرایه ها در C چی هستن.آرایه ها در Cمفهوم آرایه ها در سی شبیه پایتونه, یعنی مجموعه از ای چیز ها. اما دوتا موضوع رو باید درنظر بگیریم.سایز آرایه محدود هست و ما باید اون رو قبل از ساختن آرایه تعیین کنیمتمام اجزای آرایه باید یک تایپ مشترک داشته باشن مثلا همشون Interger یا Float باشنبیایید با مثال بریم جلو ببینیم منظورمون چیه.به مثال بالا که زدم دقت کنید:A = [1, 2.3, 'a', 'HI']ما اینجا نه تعداد عناصر آرایه A و نه تایپ ورودی آرایه A رو وارد کردیم یعنی توش هم Integer داره هم Float هم string اما در سی اینطوری نیست مثلا برای تعریف یک آرایه میگیم:int A[10];این یعنی ما یک آرایه به نام A داریم که قراره ده تا Integer بگیره. این ده تا به هیچ وجه نمیتونه بشه 11 تا و به هیچ وجه نمیشه به آرایه A چیزی غیر از Integer دادint A[5] = {1000, 2, 3, 7, 50};همون طور که میدونیم پایتون برپایه سی ساخته شده و دو قانون گفته شده (ثابت بودن سایز و نوع آرایه) باید در پایتون برقرار باشه. پس چطوری در پایتون ما میتونیم آرایه ای بدون محدودیت های گفته شده بسازیم؟بریم دونه دونه این دوتا مورد رو بررسی کنیممحدودیت تایپ اجزای آرایههمونطور که گفتیم در سی اجزای آرایه باید تایپ مشترکی داشته باشن مثلا همشون Integer یا Float باشن اما در پایتون اینطوری نیست.نکته جالب اینجاست که توی پایتون هم همه اعضای یک لیست تایپ مشترکی رو دارن! یعنی آرایه A = [1, 2.3, 'a', 'HI']که توش هم Int داره هم Float هم String همشون از دید پایتون یک Type مشترک دارن همشون فرزند PyObject هستن.typeof strcut _object{ _PyObject_HEAD_EXTRA Py_ssize_t ob_refcnt; PyTypeObject *ob_type; } PyObject;همون طور که میدونید همه چیز در پایتون آبجکت هست و اون آبجکت ها فرزند های PyObject هستن. یعنی زمانی که یک آرایه در پایتون ساخته میشه انگار آرایه ای از PyObject ها داریم حتی اگه یک کلاس جدید بسازیم:class A:pass a = A()A = [1, 2.3, 'a', 'HI', a]. پس مشکل اول حل شد بریم سراغ مشکل دوماندازه آرایهخوب همونطور که گفتیم اندازه لیست ها توی سی ثابته درحالی که توی پایتون اینطوری نیست اما در اصل موضوع اینه که پایتون هم لیست های ثابت میسازه اما هروقت اون لیست پر شد یک آرایه دیگه که یه کمی بزرگ تره میسازه و کل اون دیتاهارو کپی میکنه تو اون لیست جدید. (بهش میگن Dynamic Array).مثلا توی C آرایه زیر رو داریم:int A[5] = {1000, 2, 3, 7, 50};حالا برای اینکه بتونیم اعداد 25, 30 رو توش اضافه کنیم باید یک آرایه جدید دیگه بسازیم و اعضای آرایه قبل رو همراه با دو عدد گفته شده (25, 30) بهش اضافه کنیم:int ANew[7];for (int i = 0; i<5; i++){ ANew[i] = A[i];}ANew[5] = 25;ANew[6] = 30;خوب بریم سراغ دنیای پایتون و کدی که پایتون ازش استفاده میکنه تا آرایه جدید بسازه رو بررسی میکنیم.ما در اینجا فانکشن list_resize رو برسی میکنیم.PyObject **items; size_t new_allocated, num_allocated_bytes; Py_ssize_t allocated = self->allocated;خوب اینجا متغیر هارو تعریف میکنیم, new_allocated اندازه جدید آرایه و num_allocated_bytes سایز اون آرایه توی حافظه هست.if (allocated >= newsize && newsize >= (allocated >> 1)) { assert(self->ob_item != NULL || newsize == 0); Py_SIZE(self) = newsize; return 0; }توی این بخش بررسی میکنیم که تعداد ورودی جدید حتما بزرگتر از مقدار خود آرایه باشه در غیر این صورت همون آرایه قبلی رو بدون تغییر برمیگردونیم با اهتمام به این نکته که سایز آرایه جدید رو به عنوان سایز آرایه فعلی قرار دادیم.new_allocated = (size_t)newsize + (newsize >> 3) + (newsize < 9 ? 3 : 6);اینجا میاییم و اندازه جدید آرایه رو ست میکنیم اینجاست که میگیم دفعه اول که آرایه ساخته شد سایزش 0 باشه و بعدش به صورت زیر رشد میکنه0, 4, 8, 16, 25, 35, 46, 58, 72, 88 ...و در نهایت ساخت یک آرایه جدید و کپی کردن کل مقدارش به اون:items = (PyObject **)PyMem_Realloc(self->ob_item, num_allocated_bytes);و تمام. البته خود کد خیلی پیچیده تره ولی ما اینجا خیلی ساده به موضوع نگاه کردیمموخرههمون طور که میبیند بخش های اصلی پایتون کاملا روی سی پیاده شده. در نظر دارم توی بخش های بعدی در اعماق پایتون به بررسی بخش های دیگه هسته پایتون (CPython) بپردازم.در نهایت هم خیلی عالی میشه هر نظری دارید بگید , بدون تعارف بدون پرده :)