ممکن است شنیده باشید که توسعه دهندگان نیاز دارند که در زمینه الگوریتم مهارت داشته باشد. الگوریتم چیست؟ واین ساختارداده ها مهم هستند.

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

از زمانی که Donald knuth کتاب مهارت های برنامه نویسی کامپیوتر را نوشت( که می توان این کتاب را به عنوان دایره المعارف الگوریتم ها و ساختار داده ها دانست)  این کلمه کلمه ای گیج کننده بود و شبیه به کسی به بود که الگوریتم و ریاضیات را له می کند.

خلاصه ای درباره این مطلب

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

یک الگوریتم چیست؟

این کلمه برای تعریف یک رویکرد گام به گام که دقیقا در آن یک گام بعدی وجود دارد مورد استفاده قرار می گیرد. درون یک الگوریتم با توجه به گام فعلی و مراحلی که برای ما تعیین شده است تنها یک راه برای عمل کردن است و آن دقیقا راه درست برای انجام شدن فرایند می باشد. بگذارید برویم به سراغ یک مثال واقعی از الگوریتم که در زندگی روزانه ما بسیار مورد استفاده قرار می گیرد. ما قصد داریم الگوریتمی را برای پوشش دادن دوره های cs در کل کشور توصیف کنیم و آن دقیقا الگوریتم جست و جوی دودویی می باشد. ترسناک است؟ واقعا ترسناک نیست.

توضیحاتی درباره این بخش

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

الگوریتم جست و جوی خطی

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

مثلاً اگر به جای دفترچه تلفن یک کاغذ در دست شما باشد و بخواهید از میان ۱۰ نفر شماره تلفن دوست خود را پیدا کنید احتمالاً حرکت از بالا به سمت پایین به صورت خطی بهترین روش و هوشمندانه ترین روش برای پیدا کردن شماره دوست شما است.

الگوریتم جست و جوی chunking

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

روند الگوریتم جست و جوی chunking

روند الگوریتم chunking  در ابتدا شامل پیدا کردن یک منطقه عمومی برای جست و جو خواهد بود، بعد از آن این روند به بررسی هر یک از مناطق عمومی خواهد پرداخت. بنابراین زمانی که شما به دنبال اسم Bill Maher در دفترچه تلفن هستید، شما به صورت 100 صفحه 100 صفحه حرکت خواهید کرد، شما می‌بینید که در 100 صفحه اول آخرین اسم با c شروع می شود بنابراین 100 صفحه به جلو می‌ روید، شما می‌بینید که آخرین اسم در پایان این دویست صفحه با K شروع می شود، حال اگر 75 صفحه به جلو بروید ممکن است به حرف L برسید. حرف L  تنها یک حرف با حرف M فاصله دارد بنابراین از این جا به بعد باید حرکت خود را آرام تر کنید. این فرآیند معمولاً روش است که افراد آی تی برای  جست و جوی اسامی در دفترچه تلفن به کار می برند. ما به عنوان انسان اغلب روش‌ها را به عنوان شیوه های غریزی به کار میبریم و این الگوریتم یکی از آن روش ها است.

الگوریتم جست و جوی دودویی

کارآمد ترین الگوریتم برای پیدا کردن یک شخص در دفترچه تلفن تقسیم کردن دفترچه تلفن به دو قسمت می باشد، بعد از آن باید تعیین کنید شخص در کدام نیمه از دفترچه تلفن است، به این ترتیب شما در مرحله اول موفق شده‌اید نیمی از دفترچه تلفن را حذف کنید و روند جستجو را در نیمه دیگر صفحات ادامه دهید. فرض کنید دفترچه تلفن 400 صفحه باشد، اگر شما به دنبال اسمی با نام vince Offer باشید که در صفحه 291 قرار دارد شما می‌توانید آن را با استفاده از الگوریتم جست و جوی دودویی پیدا کنید. برای این کار کافی است دفترچه تلفن را به چهار قسمت تقسیم کنید و به احتمال زیاد با این کار به حروف m و n خواهید رسید که خیلی ساده می توانید حرف o را نیز بیابید.

مثال این بخش

از آن جایی که حرف o بعد از M و N  است، این به آن معنا است که می توانیم یک واقعیت را بیان کنیم:

نام vince offer در میان صفحات 200 تا 400 واقع شده است.

به عنوان یک انسان شما می‌دانید که حرف o درست بعد از حرف N می باشد، شما ممکن است وسوسه شوید که چند صفحه را پیش بینی کنید، اما بعد از انجام دادن الگوریتم جست و جوی دودویی شما نمی‌توانید این کار را انجام دهید. بعد از انجام یک مرحله از الگوریتم جست و جوی دودویی شما فقط نیمی از مشکل را پیش رو خواهید داشت. یعنی کافی است شما صفحه 300 را بررسی کنید با انجام دادن این کار احتمالاً در اطراف حرف s قرار خواهید گرفت، حرف O قبل از حرف S است بنابراین شما باید قاعده زیر را پیروی کنید:

نام vince offer در میان صفحات 200 تا 300 قرار گرفته است.

پیدا کردن نام vince offer در این مثال

در ابتدا با 400 صفحه شروع کردیم اما حالا فقط با انجام دو مقایسه مشکل را به 1/4 مشکل اولیه کاهش داده ایم،  با توجه به اینکه نام Vince offer در صفحه 291 قرار دارد، مقایسه های زیر را در این الگوریتم انجام خواهیم داد تا نام او را پیدا کنیم:

[200-300] -> [250-300] -> [275-300] -> [287-300] -> [287-293] -> [290-293] -> [290-291] -> 291

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

در واقع تعداد مقایسه هایی که شما با استفاده از این الگوریتم زمانی که با یک مسئله برخورد کردید لازم است انجام دهید log2(n) می باشد. که ما در این مسئله تنها 8 مقایسه را برای پیدا کردن جواب لازم داشتیم.

Log2(400) = 2.64… که یعنی ما در بدترین حالت نیاز به 9 مقایسه داشتیم.

اجازه دهید درباره دفترچه تلفن بزرگتری صحبت کنیم، یک دفترچه تلفن با 4 میلیون صفحه را در نظر بگیرید، حدس بزنید، چه تعداد از مقایسه باید انجام دهیم تا بتوانیم نام Vince Offer را پیدا کنیم؟

Log2(4,000,000) = 21.93 که یعنی شما در بدترین حالت تنها نیاز به 22 مقایسه دارید تا بتوانید این نام را پیدا کنید.

مقایسه الگوریتم ما با الگوریتم خطی برای پیدا کردن عناصر در یک دفترچه تلفن

در بدترین حالت زمانی که ما یک دفترچه تلفن را بررسی می‌کنیم ممکن است ورودی مد نظر ما در آخرین صفحه قرار دارد که در این صورت برای یک دفترچه با 4000000 صفحه در جست و جوی خطی شما نیاز به 4000000 مقایسه خواهید داشت ولی در روش جست و جوی دودویی تنها نیاز به 22 مقایسه دارید.

یادگیری الگوریتم یادگیری این موضوع است که چگونه مسئله را به مسئله های کوچکتر بشکنید

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

ترفندهایی که شما به آن نیاز دارید

ما مفهوم جستجوی دودویی عناصر را از خودمان نساخته ایم، دانشمندان کامپیوتر ترفند های بسیار زیادی را دارند که تمامی برنامه نویسان باید آنها را در ذهن خود داشته باشند.  یادگیری الگوریتم تماماً هنر تسلط بر فرایند ها و تبدیل آنها به کدی است که توسط کامپیوتر اجرا شود. همانطور که در مثال بالا دیدید استفاده از یک ترفند مناسب در یک سناریو باعث شد که کاری که 4,000,000 مقایسه نیاز داشت تنها با 22 مقایسه انجام شود. زمانی که شما بتوانید یک الگوریتم مفید علم کامپیوتر را به یک کد در هر زبان برنامه نویسی تبدیل کنید، شما در واقع این مهارت را دارید که هر کدی که به سمت شما در دنیا ارسال شود را بنویسید.

برخی دیگر از ترفندهایی که شما بعید است بتوانید خودتان به آن ها دست بیابید( در واقع باید از دانشمندان علم کامپیوتر یاد بگیرید) الگوریتم هایی مانند الگوریتم های زیر هستند:

1-      الگوریتم جست و جوی عمیق

2-      Breadth-first search

3-      نوشتن الگوریتم های مرتب سازی

توضیحاتی درباره این بخش

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

ساختار داده صف

صف یک ساختار داده مشخص است که شما نیاز دارید در آن الگوریتم breadth-first search  را پیاده سازی کنید، اگر شما ساختار داده های مختلف را درک نکنید شما به عنوان یک برنامه نویس باید با ابزارهای کمتری کار کنید و همین طور برای اجرای برخی از الگوریتم ها زمان زیادی را باید بگذرانید.

شما میتوانید یک مثال بسیار بزرگ از ساختار داده  صف را در هنگام غذا خوردن تجربه کنید، زمانی که شما در صف غذا ایستاده اید یک شماره می‌گیرید و منتظر می‌مانید تا شماره شما صدا زده شود. هر کسی که زودتر از شما شماره گرفته باشد زودتر نیز سرویس غذا را دریافت خواهد کرد.

صف ها دارای دو ویژگی بسیار جالب هستند:

1-      Enqueue به زمانی گفته می شود که شما شروع به منتظر ماندن می کنید. در واقع آن دقیقا زمانی است که شما یک شماره دریافت می کنید.

2-      Dequeue به زمانی گفته می شود که شما باید سرویس دریافت کنید، این دقیقا معادل است با زمانی که شماره شما صدا زده می شود که سرویس غذای خود را دریافت کنید.

جمع بندی

بنابراین به صورت خلاصه می‌توان گفت که الگوریتم‌ ها الگوها و رویه های هستند که برای رسیدن به یک هدف خاص مورد استفاده قرار می‌گیرند. ساختار داده ها مانند ابزاری در ذهن شما هستند که می توانید از آنها برای برنامه نویسی استفاده کنید، شما نیازی ندارید که از آنها در برنامه نویسی استفاده کنید و در واقع می ‌توان گفت لزومی ندارد که از آن ها استفاده کنید ولی استفاده از آن ها در هنگام برنامه نویسی برای یک کار خاص باعث می‌شود تا کد شما تمیز تر و راحت تر نوشته شود و استفاده از این ابزارها باعث می شود تا شما برنامه نویس و توسعه دهنده بهتری باشید.