ساختمان داده مقدماتی

ساختمان داده یعنی چه و چرا انتخابش اهمیت دارد؟

ساختمان داده شکلی است که چند چیز را کنار هم در آن نگه می دارید. تا اینجا ساده به نظر می رسد و همین سادگی باعث می شود اهمیتش دیده نشود: بیشتر تازه کارها فکر می کنند انتخاب بین این شکل ها سلیقه ای است، چون هر کدامشان می توانند همان داده را نگه دارند.

هر کدامشان واقعا می توانند. اسم صد نفر را می شود در یک فهرست گذاشت، می شود در یک دیکشنری گذاشت، و می شود در یک مجموعه گذاشت. تفاوت جای دیگری است: هر شکل یک سوال را ارزان جواب می دهد و بقیه سوال ها را گران.

پس قاعده ای که باید از این درس با خودتان ببرید این است. وقتی می خواهید تصمیم بگیرید داده را در چه شکلی نگه دارید، به خود داده نگاه نکنید؛ به سوالی نگاه کنید که قرار است بعدا از آن بپرسید. «عضو سوم کدام است» یک سوال است، «مقدار این کلید چیست» سوال دیگری است، و «این چیز اصلا اینجا هست» سوال سومی است. سه سوال، سه شکل.

و برای اینکه انتظار درستی داشته باشید: انتخاب اشتباه معمولا برنامه را خراب نمی کند. برنامه کار می کند، فقط کد شما برای پرسیدن یک سوال ساده مجبور می شود کار زیادی بکند، و آن کار زیادی وقتی داده بزرگ می شود یا وقتی چیزی به آن اضافه می شود خودش را نشان می دهد. بخش آخر همین درس یک نمونه واقعی از همین حالت است.

فهرست: وقتی ترتیب خودش یک اطلاعات است

فهرست چند چیز پشت سر هم است که ترتیبشان حفظ می شود. همین حفظ شدن ترتیب، تنها چیزی است که فهرست را از بقیه جدا می کند و بیشتر از آنکه به نظر می رسد اهمیت دارد.

prices = [12000, 8000, 15000]

prices.append(9000)
print(prices[0])
print(len(prices))

هر عضو یک شماره دارد که به آن شاخص می گویند، و شماره ها از صفر شروع می شوند نه از یک. پس prices[0] اولین قیمت است. این از صفر شروع شدن، دلیل تاریخی دارد و در تقریبا همه زبان های امروزی یکسان است، ولی برای همین هم منبع همان خطای یکی است که در درس شرط و حلقه دیدید.

فهرست وقتی درست است که ترتیب معنا داشته باشد: مراحل یک کار، نتایج یک جستجو به ترتیب رتبه، پیام های یک گفتگو. در همه اینها اگر جای دو عضو را عوض کنید، معنا عوض می شود، و همین نشانه است که فهرست انتخاب درستی است.

و یک ویژگی که در نگاه اول مزیت به نظر می رسد و بعدا هزینه می شود: شاخص یک عضو ثابت نیست. اگر عضو اول را حذف کنید، هر عضو بعدی یک پله جلو می آید و شاخصش عوض می شود. یعنی «عضو شماره سه» چیزی درباره خود آن عضو نمی گوید؛ فقط می گوید همین حالا کجای فهرست ایستاده. اگر جایی این شماره را نگه داشته باشید تا بعدا از آن استفاده کنید، همان جا یک باگ ساخته اید که هنوز اتفاق نیفتاده.

دیکشنری: وقتی کلید جای شماره را می گیرد

دیکشنری جفت هایی از کلید و مقدار است. به جای اینکه یک چیز را با شماره اش پیدا کنید، با اسمش پیدا می کنید. در زبان های مختلف اسم های مختلفی دارد، ولی ایده همان است.

user = {"name": "sara", "city": "shiraz"}

print(user["city"])
user["city"] = "tabriz"

تفاوت مهمی که معمولا جا می ماند این است: وقتی می نویسید user["city"]، برنامه داخل دیکشنری نمی گردد. مستقیم می رود سر جای درست. اگر همین داده را در یک فهرست از جفت ها نگه داشته بودید، برای پیدا کردن شهر باید کل فهرست را از اول می خواندید تا به جفتی برسید که کلیدش شهر است.

روی سه عضو این تفاوت به چشم نمی آید. روی سه هزار عضو، و مخصوصا وقتی این جستجو خودش داخل یک حلقه باشد، همان تفاوت است که یک صفحه را کند می کند. و بیشتر کدهای کند که ما در سایت های مشتری ها دیده ایم دقیقا از همین جنس اند: جستجوی خطی داخل حلقه، جایی که یک کلید کافی بود.

ویژگی دومی که به همان اندازه مهم است: کلید عوض نمی شود. برخلاف شاخص فهرست که با حذف و اضافه جا به جا می شود، کلید همان کلید می ماند. اگر لازم دارید بعدا به یک عضو مشخص برگردید، این تنها ویژگی ای است که واقعا لازم دارید، و بخش آخر همین درس نشان می دهد این حرف در عمل چقدر جدی است.

مجموعه: وقتی فقط می خواهید بدانید هست یا نه

مجموعه چند چیز یکتاست، بدون ترتیب مشخص. دو کار را خیلی خوب انجام می دهد و بقیه کارها را اصلا: تکراری ها را حذف می کند، و به سرعت جواب می دهد که یک چیز داخلش هست یا نه.

tags = {"seo", "speed", "seo"}

print(len(tags))
print("seo" in tags)

خروجی خط سوم دو است نه سه، چون تکراری در همان لحظه ورود حذف شده. این رفتار همان چیزی است که مجموعه را مفید می کند و همان چیزی است که اگر حواستان نباشد داده تان را بی صدا کم می کند؛ اگر تکرارها برایتان معنا دارند، مجموعه شکل غلطی است.

حالا یک نمونه از دنیای واقعی، از کد همین سایت. PHP اصلا نوع داده ای به اسم مجموعه ندارد. پس وقتی به یک مجموعه احتیاج پیدا می کنیم، از آرایه ای می سازیمش که کلیدهایش همان چیزهایی اند که می خواهیم بشماریم و مقدارهایش هیچ اهمیتی ندارند:

$used = array();

// ... در حلقه ای که برای هر تیتر یک شناسه می سازد:
while ( isset( $used[ $id ] ) ) {
    $id = $base . '-' . $n++;
}
$used[ $id ] = true;

به مقدار true دقت کنید: هیچ جای برنامه خوانده نمی شود. چیزی که واقعا ذخیره شده خود کلید است، یعنی «این شناسه قبلا استفاده شده». این دقیقا تعریف مجموعه است، ساخته شده از ابزاری که در دسترس بوده. و علت اینکه اینجا فهرست به کار نمی آید همان علت بخش قبل است: isset مستقیم سراغ کلید می رود، ولی گشتن دنبال یک شناسه در فهرستی از شناسه ها یعنی خواندن کل فهرست، آن هم داخل حلقه ای که برای هر تیتر یک بار اجرا می شود.

کدام یک را کجا؟

سه شکل بالا به اضافه یکی که هنوز نامش نیامده، تاپل، تقریبا هر چیزی را که در سال اول لازم دارید پوشش می دهند. تاپل همان فهرست است با یک تفاوت: بعد از ساخته شدن عوض نمی شود. برای چیزهایی به کار می آید که ذاتا نباید تغییر کنند، مثل یک جفت طول و عرض جغرافیایی.

ستون آخر مهم ترین ستون این جدول است و بقیه فقط توضیح آن هستند. اگر مطمئن نیستید کدام را انتخاب کنید، جمله ای را بنویسید که قرار است بعدا از این داده بپرسید و ببینید در کدام سطر می نشیند.

و یک موضع که با آموزش های معمول جور درنمی آید: در کار روزمره وب، دیکشنری بیشتر از فهرست به کار می آید و بیشتر از آن هم کمتر استفاده می شود. تازه کارها همه چیز را در فهرست می ریزند چون فهرست اولین چیزی است که یاد گرفته اند، و بعد برای پیدا کردن یک عضو داخل حلقه می گردند. اگر فقط همین یک عادت را عوض کنید، بخش خوبی از کدهای کندی که بعدا می نویسید اصلا نوشته نمی شوند.

یک تصمیم واقعی: چرا دفتر انتشار این درس ها فهرست نیست

همین بخش آموزشی که الان می خوانید، درس هایش یکی یکی و طبق یک برنامه منتشر می شوند: روزی سه درس، و به نوبت از میان شانزده مسیر. ترتیب این نوبت ها ذخیره نمی شود؛ هر بار از روی خود درس ها دوباره حساب می شود.

و همین جا یک مشکل واقعی هست. وقتی مسیری که هنوز خالی بوده پر می شود، درس های تازه اش وسط صف می نشینند و شماره هر درسی که بعد از آنها بوده یک پله جلو می رود. حالا فرض کنید دفتری که می گوید چه چیزی منتشر شده، فهرستی از شماره ها بود، یا حتی فقط یک عدد که می گفت پنج تای اول منتشر شده اند. درسی که دیروز منتشر شده بود، امروز بعد از جا به جا شدن صف دیگر جزو پنج تای اول نبود، از فهرست بیرون می افتاد و برای بازدیدکننده صفحه اش ۴۰۴ می شد.

پس دفتر یک دیکشنری است. کلیدش نشانی خود درس است و مقدارش لحظه ای که برای اولین بار منتشر شده. روزی که این درس بررسی شد، پنج کلید داشت و اولینشان این بود:

'seo/how-search-engines-work' => 1788539040

حالا صف هر چقدر هم عوض شود، این کلید سر جایش می ماند، چون کلید از اول هم یک جایگاه در صف نبود؛ اسم خود درس بود. کل ماجرا در یک جمله: فهرست جواب می دهد که در جایگاه سوم چه چیزی هست، و دیکشنری جواب می دهد که این درس مشخص کی منتشر شد. فقط سوال دوم است که وقتی صف دوباره ساخته می شود همچنان معنا دارد.

این همان چیزی است که بخش اول این درس گفت، ولی این بار روی یک صفحه واقعی: انتخاب اشتباه برنامه را خراب نمی کرد. برنامه کار می کرد، فقط یک روز صبح چند صفحه منتشر شده بی صدا ناپدید می شدند.