۰۰/۵/۲ شنبه
در پست قبل بلاگ پلازیکا در مورد کاربرد ساختمان دادهها در زندگی روزمره صحبت کردیم. همچنین در مورد نقش مهم ساختمان دادهها و الگوریتمها در برنامهنویسی و بهینهکردن کارایی نرمافزارها گفتیم. در این پست پلازیکا در مورد الگوریتمهایی صحبت خواهیم کرد که از آنها در زندگی روزمره استفاده میکنیم. امیدواریم این کار به درک بهتر و عمیقتر شما از ساختمان دادهها و الگوریتمها کمک کند.
اگر پست قبل را نخواندهاید، پیشنهاد میکنیم قبل از ادامه مطالعه این پست، آن را بخوانید: ساختمان دادهها در زندگی روزمره
مرتبسازی فرایند چیدن آیتمهای مشابه به صورت منظم و باقاعده است. مثلاً فرض کنید میخواهید کتابهای یک قفسه را بر اساس قدشان مرتب کنید. در این حالت میتوانیم همیشه کتاب بلندتر را سمت چپ بگذاریم و کتابهای کوتاهتر را به دنبال آنها بچینیم و یا بالعکس.
مفهومی مشابه با همین مثال در الگوریتم مرتبسازی نیز وجود دارد. الگوریتمهای مرتبسازی زیادی در حوزه ساختمان دادهها و الگوریتمها وجود دارند. یک برنامهنویس ماهر با توجه به منابع و محدودیتهایی که از نظر سیستمی با آن مواجه است، الگوریتم مناسب را انتخاب میکند.
در مثال بالا فرض کنید میخواهیم کتابها را به سریعترین شکل ممکن مرتب کنیم. برای این کار باید چند نکته را در نظر بگیریم:
الگوریتمها با در نظر گرفتن همه محدودیتها ساخته میشوند تا راه حلی بهینه شده برای برنامهنویسان و مهندسین نرم افزار فراهم کنند. برخی از الگوریتمهای مرتبسازی عبارت است از: مرتبسازی حبابی، مرتبسازی انتخابی، مرتبسازی ادغامی، مرتبسازی سریع و ...
الگوریتم جستجو، همانند نامش، به پیدا کردن چیزی کمک میکند.
فرض کنید که میخواهید یک کتاب به خصوص را در قفسه کتاب پیدا کنید. در این قفسه کتاب، کتابها به ترتیب خاصی قرار نگرفتهاند. به نظر شما سریعترین راه حل برای پیدا کردن کتاب مورد نظر ما چه راه حلی میباشد؟ ساختمان دادهها و الگوریتمها به بهترین نحو به این سؤال پاسخ میدهند.
شاید با خودتان بگویید: «از اول شروع میکنم، همه کتابها را نگاه میکنم تا کتابی که میخواهم را پیدا کنم.» یعنی یکی یکی همه کتابها را بررسی کنید تا کتاب مورد نظرتان را پیدا کنید. به این کار در علم الگوریتم، جستجوی خطی میگویند.
اگر کتاب مورد نظر ما ته قفسه باشد، این راه حل وقت زیادی از ما میگیرد. پس احتمالاً سریعترین راه ممکن نخواهد بود.
بیایید یک راه حل دیگر را امتحان کنیم. اول کتابها را به ترتیب الفبا مرتب کنیم؛ سپس از وسط به دنبال کتاب مورد نظرمان بگردیم. فرض کنید کتاب مورد نظر ما با حرف J شروع میشود.
از آنجایی که قرار است از وسط به دنبال کتابمان بگردیم، از حرف M که بین A و Z میباشد، شروع میکنیم.
حالا J را با M مقایسه میکنیم. میدانیم که J قبل از M قرار میگیرد؛ پس بیاید در موقعیت بین A و M به دنبال J بگردیم. G حرف وسط بین A و M است. باز هم نتوانستیم J را پیدا کنیم.
از آنجایی که J بین G و M است، بیایید حرفی که وسط G و M میآید را پیدا کنیم. ایول، J را پیدا کردیم. تبریک میگم!😁
به الگوریتمی که از آن برای یافتن کتاب موردنظرمان استفاده کردیم، جستجوی باینری یا جستجوی دوتایی میگویند.
آیا تابهحال به این فکر کردهاید که چطور گوگل مپ کوتاهترین مسیر بین مبدأ و مقصد را برای شما پیدا میکند؟ گوگل مپ و اپلیکیشنهای مشابه گوگل مپ برای این کار از مجموعهای از الگوریتمها استفاده میکنند که با عنوان الگوریتمهای یافتن کوتاهترین مسیر (Shortest Path Finding Algorithm) شناخته میشوند.
این الگوریتمها با استفاده از نمایش گراف که در پست قبل در مورد آن صحبت کردیم، کوتاهترین مسیر را پیدا میکنند. برای شبیه سازی این مسئله، بیاید کوتاهترین مسیر بین A و F را در نقشه زیر پیدا کنیم.
از چه مسیرهایی میتوان از A به F رفت؟ ابتدا بیایید گزینههای پیش رو را پیدا کنیم.
از این عکسها میفهمیم که کوتاهترین مسیر، مسیر 3 است اما برای پیدا کردن این مسیر مجبور شدهایم بقیه مسیرها را هم بررسی کنیم که این کار در مقیاس بزرگتر (مثلاً پیدا کردن مسیرها در شهرهای بزرگ و فاصلههای بیشتر) میتواند بسیار زمانبر باشد. برای اینکه بدون اتلاف وقت راه حل درست را پیدا کنیم، ابتدا کوتاه مسیر را تا راسی که با A همسایه است پیدا میکنیم. همسایههای A، B و C هستند که از بین اینها مسیر AC از AB کوتاهتر است.
حالا ما در موقعیت C قرار داریم. باز هم به دنبال کوتاهترین مسیر تا همسایههای C میگردیم. از بین CE و CD، CD کوتاهتر است.
از D فقط یک مسیر به F وجود دارد. البته از F به B هم میتوان رفت اما قبلاً نقطه B را بررسی کردهایم. پس مسیر DF را انتخاب میکنیم و به مقصد میرسیم.
باز هم تبریک میگویم!🥳 موفق شدیم الگوریتم دایجسترا را پیاده سازی کنیم.
وقتی سال آخر دانشگاه بودم و به عنوان یک مهندس نرم افزار و یک برنامهنویس به شرکتهای متفاوت رزومه ارسال میکردم، متوجه شدم چیزی در روند استخدام همه شرکتها مشترک است. همه آنها با پرسیدن سؤالاتی که راه حلشان شامل استفاده از ساختمان دادهها و الگوریتمها میشد، تواناییهای مرا محک میزدند. دانش کافی در حوزه ساختمان دادهها و الگوریتمها همیشه یکی از مهمترین فاکتورهای استخدام شرکتهای نرم افزاری بوده است. کارفرماها با پرسش سؤالاتی در این زمینه توانایی حل مسئله کارجویان را میسنجند.
همانطور که در مثالهای بالا دیدید، یادگیری ساختمان دادهها و الگوریتمها بسیار ساده و تا حدی سرگرم کننده است؛ زیرا میتوانیم موارد استفاده از آنها را در زندگی روزمره خود نیز بیابیم. حتی کسانی که تحصیلات مرتبط با نرم افزار ندارند ولی به برنامهنویسی علاقهمندند نیز میتوانند به سادگی ساختمان دادهها و الگوریتمها را بیاموزند.
به علاوه، هیچکس نمیتواند اهمیت ساختمان دادهها و الگوریتمها را در برنامهنویسی انکار کند. ساختمان دادهها و الگوریتمها هیچگاه منقرض نمیشوند؛ بلکه با تکامل زبانهای برنامهنویسی، آنها هم کاملتر شده و بهینهتر عمل میکنند.
در آخر به یاد داشته باشید که یک برنامهنویسی باید بداند چگونه از ساختمان داده و الگوریتمهای مناسب استفاده کند تا خروجی مطلوب را دریافت کند. سخن معروفی هست که میگوید:
«یک جنگجو نباید فقط اسلحه داشته باشد، بلکه باید بداند چه زمانی و چگونه از آن استفاده کند.»
در حال انجام عملیات