مهدی موسوی
مهدی موسوی
خواندن ۴ دقیقه·۴ سال پیش

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

مقدمه

تو دنیای کامپیوتر یکسری ابزار داریم که با اون ها کار هامون رو انجام میدیم مثل زبان های برنامه نویسی. بیایید یه کمی ساده تر حرف بزنیم فک کنید که شما میخواید پریز خونتون رو عوض کنید , ازچه ابزاری استفاده میکنید؟ درسته فازمتر. پیچ هارو با فارمتر باز میکنید, پریز جدید رو قرار میدید و پیچ هارو میبندید تهش هم با همون فازمتر امتحان میکنید ببینید برق داره یا نه. زبان های برنامه نویسی هم مثل همون فازمترن. ازشون استفاده میکنیم تا به اهدافمون (که همون تعویض پریزه) برسیم. حالا ما توی سری در اعماق پایتون میخوایم ببینیم خود این ابزار چگونه کار میکنه. تو این سری باید یه کمی سی, و پایتون بلد باشید. البته من تمام سعی خودم رو کردم که همه چیز رو ساده و روون توضیح بدم اما برای درک عمیق موضوع خیلی نیازتون میشه. نکته بعدی اینه که پایتون چند تا مفسر داره مثل 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) بپردازم.

در نهایت هم خیلی عالی میشه هر نظری دارید بگید , بدون تعارف بدون پرده :)




پایتونلیستسیcpython
May the FORCE be with you
شاید از این پست‌ها خوشتان بیاید