logo

درک الگوریتم

ارشیا فلاحی•۱۴۰۳ اسفند•۱۵ دقیقه مطالعه
درک الگوریتم

توی این سری پست ها که شامل چند پارت خواهد بود میخواهیم درباره الگوریتم ها صحبت کنیم. اما چرا این پست ها خیلی مهم هستند؟ دلیل اصلیش اینه که این بحث دقیقا همون بخش از دنیای کامپوتر هستش که برای تبدیل شدن به یه مهندس نرم افزار باید بدونید و نه لزوماً یه کدنویس. درک این مسائل باعث میشه بفهمیم کامپیوتر‌ها چطور کار میکنن و ما هدف و نقشمون در دنیای کامپیوتر دقیقا چیه؟

الگوریتم

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

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

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

جستوجوی ساده

[تصویر]

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

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

جوستوجوی دودویی (binary search)

فکر کنم بهترین الگوریتم جستوجو تا به امروز همین الگوریتم جستوجوی دودویی هستش. اگر یادتون باشه من اشاره کردم لیستی که با اون طرفیم باید مرتب شده باشه، مثلا اگه شامل اعداد هستش باید به صورت افزایشی (۱،۲،۳) یا کاهشی (۳،۲،۱) مرتب شده باشه و اگر هم کلمه یا متن هستش باید به ترتیب حروف الفبا مرتب شود. اما چطور باید اون آیتم(شماره) مورد نظر را پیدا کنیم. قضیه از این قرار ما میتونیم به جای برسی کردن تک تک آیتم ها با شماره‌ای که در نظر داریم. میتونیم یه ضرب با آیتم وسطی مقایسه کنیم که بیشترین تعداد از موارد نا مطلوب حذف بشن. اجازه بدید با یه لیست عددی بیشتر توضیح بدم. فرض کنید یه لیست عددی ۱-۱۰ داریم دقیقا مثل دفتر تلفن منتهی با عدد.

![[binary_search.png]]

مثلا توی این مثال من دنبال عدد ۷ توی لیست ۱-۱۰ میگردم به جای اینکه با تک تک آیتم ها از اول لیست مقایسه کنم یه ضرب با آیتم وسطی مقایسه میکنم اگر که آیتم وسطی عدد ۷ بود برنامه تمومه در غیر این صورت دو حالت داریم یک حالت این است که عدد وسط لیست از آیتم مورد نظر ما کوچیک تر باشد که در این حالت ما مطمعن میشیم که تمام آیتم های قبل از آیتم وسط هم از آیتم مورد نظر ما کوچکتر هستند (زیرا لیست مرتب شده است) و ما می توانیم آن بخش از لیست را در نظر نگیریم یا حذف کنیم. اما حالت دیگر بزرگ تر بودن آیتم وسط از عدد مورد نظر ما است که دقیقا بر عکس همان حالت قبل است یعنی ما مطمعن میشویم که تمام آیتم های بعد از آیتم وسط همگی از آیتم مورد نظر ما بزرگتر هستند پس میتوانیم آنهارا نادیده بگیریم یا حذف کنیم. بعد از این دستور العمل ها ما با یک لیست کوچیک تر طرفیم (دقیقا مثل تصویر بالا) که دقیقا یا تقریبا نصف لیست قبلی است که باید برای این لیست کوچک شده هم همان دستورالعمل های قبلی رو اجرا کنیم تا دوباره لیست نصف شود و همین حلقه را آنقدر تکرار میکنیم تا به جایی برسیم که آیتم وسط همان عدد مدنظر ما (در بدترین حالت لیست ما تا اندازه ۱ کوچک میشود)

int binary_search(const std::vector<int>& list, int target) {
	if (list.empty()) return -1;

	int low = 0;
	int high = static_cast<int>(list.size()) - 1;

	  while (low <= high) {
	    int guess =  (high + low) / 2;
	
	    if (list[guess] == target)
	      return guess;
	    else if (list[guess] > target)
	      high = guess - 1;
	    else
	      low = guess + 1;
	  }

	  return -1;
}

مقایسه الگوریتم ها

فکر نکنم لازم باشه که خیلی توضیح بدم همیشه الگوریتم های بد و الگوریتم های خوب وجود دارن، مثلا اگه شما کلید خونتونو گم کرده باشید و بخواهید آنرا پیدا کنید یک الگوریتم اینه که تک تک مکان های ممکن در خونتونو به ترتیب بگردید که در نهایت کلید رو پیدا کنید طبیعتا این کار خیلی زمانبر هستش شما اگه بخواهید کلید خود را پیدا کنید، مکان هایی رو میگردید که فکر میکنید ممکنه کلید اونجا باشه و اینطوری خیلی سریع تر از (گشتن همه جا) کلیدتونو پیدا میکنید. اما در رابطه با الگوریتم هایی که در کامپیوتر ها اجرا میشوند این قضیه کمی متفاوت است. الگوریتم هارو ما میتونیم با دو مولفه "زمان اجرا‌ء" و "حافظه (memory)" مقایسه کنیم. در ادامه میخواهیم نگاه دقیق تری به هر کدام از این مولفه ها داشته باشیم و یه سری نکات راجب اینکه توجه نکردن به هر کدوم از این مولفه ها چه مشکلاتی رو میتونه به وجود بیاره.

زمان اجراء و نماد O

طبیعتا هر الگوریتمی برای اجرا شده نیاز به زمان داره، ولی خوب از طرفی هم میدونیم که سخت افزار های مختلف سرعت مختلفی دارن مثلا روی یه cpu و ram قدیمی طبیعتا یه الگوریتم زمان اجراء بیشتری نیاز داره تا روی سیستم های جدید تر و قوی تر در نتیجه ما نمی تونیم الگوریتم هارو با واحد ثانیه یا میلی ثانیه مقایسه کنیم پس چطور باید این مقایسه رو انجام بدیم؟ برای این کار با واحدی تحت عنوان "تعداد عملیات" این مقایسه رو انجام میدیم تعریفش خیلی سر راسته، میگیم توی بد ترین حالت باید چند تا عملیات انجام بدیم تا مسئله رو حل کنیم. با این تعریف میتونیم الگوریتم هایی که توضیح داده بودیم رو یه بار دیگه برسی کنیم و ببینیم زمان اجرا هر کدوم چقدره با توجه به این واحد. در الگوریتم جستوجوی ساده اگر ما ۱۰۰ آیتم داشته باشیم و آیتم مورد نظر ما فرضا عدد ۱۰۰ باشد(بدترین حالت) ما باید ۱۰۰ بار عملیاتِ "مقایسه با عدد مدنظر" رو انجام بدیم پس میشه گفت زمان اجراء الگوریتم جستوجوی ساده n هستش اما چون n به تنهایی فقط یه متغییر هستش از نماد O بزرگ استفاده میکنیم که برای نشون دادن زمان اجرای الگوریتم ها است. یعنی باید بگیم زمان اجرای الگوریتم جستوجوی ساده $O(n)$ هستش. اما این متغییر n دقیقا معنیش چیه؟ n تعریف واضحی نداره میتونید تعداد ورودی ها، یا تعداد کل حالات در نظر بگیرید. پس وقتی میگیم زمان اجراء الگوریتم جستوجوی ساده n هستش یعنی در بدترین حالت به تعداد تمام ورودی ها یا تمام حالات ممکن باید عملیات انجام شود تا مسئله حل شود. الگوریتم جستوجوی دودویی چطور؟ در این الگوریتم به ازای ۱۰۰ ورودی در بدترین حالت باید ۷ عملیات انجام شود تا بتوانیم آیتم مورد نظر رو پیدا کنیم همونطور که میبینید به مراتب عملیات های کمتری صورت میگیره اما این عدد ۷ از کجا اومد؟ توی الگوریتم جستوجوی دودویی ما گفتیم که در هر عملیات ما اندازه لیست یا کل ورودی هارو تقسیم بر ۲ میکردیم. توی ریاضیات چند بار تقسیتم شدن بر ۲ رو با $\log_2 n$ (لوگاریتم مبنای ۲) نشون میدیم پس میتونیم بگیم که زمان اجرای الگوریتم جستوجوی دودویی برابر با $O(\log_2 n)$ است.

حافظه (memory) ‍

حافظه یکی دیگه از منابعی هستش که یه الگوریتم برای اجراء شدن نیاز داره همون چیزی هستش که ما تحت عنوان ram میشناسیم. زمانی اهمیت آن را متوجه می‌شوید که هنگام اجرای بازی مورد علاقه تون به مصرف رم نگاه میکنید ): وقتی میگیم حافظه‌ی مصرفی رم چقدره داریم راجب مقدار حافظه‌ای صحبت میکنیم که الگوریتم ما برای اجرا شدن به اون نیاز داره. که شامل بخش های مختلفی هم هست.

این بحث نیاز به زمان بیشتری برای توضیح داره و برای درک بهتر اون نیاز داریم که یک زبان برنامه نویسی سطح پایین رو به خوبی بدونیم به همین خاطر در زمان دیگه ای بیشتر در موردش صحبت میکنیم. و راجب این ۳ نوع ورودی هم در ادامه همین بحث بیشتر صحبت میکنیم.

بی توجی به منابع

حالا که ما این دو مولفه رو میشناسیم میتونیم بریم سراغ اینکه بی توجی به هر کدوم چه مشکلاتی میتونه به وجود بیاره.

داده های بزرگ میشوند اما سخت افزار نه!

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

سرعت رشد در زمان اجراء

چه چیزی باعث میشود الگوریتم جستوجوی دودویی با تاکید آنقدر بهتر از حالت ساده باشد؟ فرض کنید که شما وظیفه دارید الگوریتمی ارائه دهید که از بین ۱ میلیاد عنصر به دنبال آیتم مد نظر بگردید خوب شما برای تست اینکه از چه الگوریتمی استفاده کنید. برای ۱۰ آیتم از جستجوی دودویی و ساده استفاده میکنید نتیجه چنین چیزی می‌شود (فرض ما بر این است که هر عملیات 1ms طول می‌کشد)

بعد از این نتیجه شما پیش خودتون فکر میکنید که اختلاف این دو الگوریتم خیلی هم زیاد نشد کلا ۶.۵ میلی ثانیه اختلاف دارن. اما اینجا شما اشتباه خیلی بزرگی مرتکب شدید. چون اگر همین دو الگوریتم را روی صورت مسئله که ۱ میلیارد آیتم است تست کنید نتیجه بسیار متفاوت میشود

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

عملکرد حافظه

وقتی از حافظه صحبت می‌کنیم منظورمون همون رم (RAM) هستش که مخفف random access memory است. اما حافظه دقیقا چیه و چیکار میکنه؟ حافظه مثل یک دِراور بزرگ از کشو هاست که درون هر کشو می‌توان داده هایی را قرار داد.

![[RAM.png]]

هنگامی که شما در برنامه خود یک متغییر تعریف می‌کنید در حقیقت دارید به کامپیوتر میگید که یک بخش از حافظه رو به من بده تا داده های دلخواهمو درون اون بزارم.

int number = 10;

فرضا توی این مثال داریم به کامپیوتر میگم یه فضای ۲ یا ۴ بایتی رو به من اختصاص بده که دورن اون عدد ۱۰ قرار می‌گیره و نوع این متغییر هم int هست که یعنی همون عدد صحیح. در ضمن به هر کدوم از اون کشو‌ های حافظه یه بایت فضای ذخیره سازی داره معادل ۰-۲۵۵ عدد (بیت با بایت فرق داره). میتونیم حافظه رو مثل یه جدول هم ببینیم که هر خونش یه بایته اینم تعریف بدی نیست و میتونه توی مسائل بعدی بهمون کمک کنه.

آرایه‌ها و لیست‌های پیوندی

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

![[Array.png]]

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

![[Array_issue.png]]

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

لیست‌ های پیوندی

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

![[linked_list.png]]

تفاوت‌های آرایه ها و لیست های پیوندی

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

اما خواندن اطلاعات تنها کاری نیست که ما با یک آرایه یا لیست پیوندی انجام می‌دهیم عمل دیگری که باید برسی کنیم درج و حدف اطلاعات است که در این زمینه لیست های بسیار بهتر عمل می‌کنند اما چرا ؟ اجازه بدید اول راجب این توضیح بدیم که چرا آرایه ها در این کار کُند هستند همونطور که دیدید من توی مثال نام دوستان که باهاش آرایه هارو تعریف کردم گفتم اگه یه دوست جدید پیدا کنید و بخواهید نام اون رو اضافه کنید به این لیست نیازه که کلا آرایه رو جابه‌جا کنیم به همین دلیل میتونیم درک کنیم که چرا توی درج و حذف آرایه‌ها کند عمل می‌کند حتی اگه نیاز نباشه که کل آرایه رو جابه‌جا کنید اگه بخواهید یک آیتم به اول لیست اضافه کنید لازمه که تمام آیتم هارو یکی ببرید جلو و برای حذف آیتم اول باید تمام آیتم هارو یکی بیارید عقب که خوب طبیعتا خیلی کُنده. اما برای لیست های پیوندی این عمل خیلی راحت تر هست کافیه هر جایی خواستید آیتم جدیدی اضافه کنید فقط اون رو داخل حافظه قرار بدید و به آیتم قبلی اون بگید که اکنون به این آیتم جدید اشاره کن یعنی صرف لازمه اشاره‌گر هارو تغییر بدیم. خوب پس میتونیم زمان اجراء درج و حذف این دو را اینطوری بنویسیم.

ادامه در پارت بعدی