پست انواع سرچ ها روی لیست:

انواع سرچ ها روی لیست: خیلی خلاصه چند تا از انواع سرچ ها رو روی لیست باهم ببینیم: فرض کنید یه لیست نا مرتبی از اعداد داریم به این شکل: lst = [30, 2, 7, 14, 1, 25, 4, 15, 9] اگه بخواهیم دنبال عدد ۱۵ بگردیم باید چیکار کنیم؟ 1- Linear search(not optimized) میتونیم از ایندکس شماره صفر شروع کنیم و تک تک تا انتها بریم جلو و اعداد رو نگاه کنیم ببینیم ۱۵ داخلشون هست یا نه. این درواقع کاری هست که پایتون انجام میده زمانی که شما از in استفاده میکنید. چون اعداد ترتیبی ندارن کار دیگه ای نمیشه کرد. ________________________________________ اگه اعداد مرتب بودن چی؟ lst = [1, 2, 4, 7, 9, 14, 15, 25, 30] 2- Linear search(optimized) فرض کنیم میخواهیم دنبال عدد ۵ بگردیم. دوباره میتونیم شروع کنیم تک تک اعداد رو مقایسه کنیم، ولی بعد از اینکه به عدد ۷ رسیدیم، میتونیم دیگه ادامه ندیم. چون اعداد مرتب هستن، حتما توی اعداد بزرگتر از ۷ هم نخواهد بود. بهتر شد اینجا. 3- Jump search میتونیم به جای اینکه تک تک به جلو بریم و اعداد رو، چند تا چند تا جلو بریم و بپریم اصطلاحا (jump search). فرض کنید دنبال عدد ۲۵ میگردیم. میتونیم اعداد رو ۲ تا ۲ تا جلو بریم، یعنی اول ایندکس شماره ۰ (یا عدد ۱) و نگاه میکنیم، بعد میریم ایندکس شماره ۲ (یا عدد ۴)، بعد ایندکس شماره ۴ (یا عدد ۹) و تا آخر، هر جا که دیدیم عدد ایندکس مورد نظر بزرگتر از عدد مقصود ماست، یعنی به اون تیکه از لیست که ممکنه عدد هدف داخلش باشه رسیدیم، فقط کافیه داخل اون رو به صورت linear نگاه کنیم. برای پیدا کردن عدد ۲۵ ، فقط ۶ تا مقایسه لازم بود. (تو حالت خطی ۸ تا). حالا این jump ما چقدر باشه خوبه؟ محاسبات نشون میده که رادیکال n بهترین گام هست. ( n تعداد آیتم های داخل لیست هست) 4- Binary search کافیه توی هر مرحله لیستمون رو به دو قسمت تقسیم کنیم، و آیتم هدف رو با آیتم وسطی مقایسه کنیم، اگه کوچیکتر بود، دیگه فقط توی اون نیمه ی سمت چپ دنبالش میگردیم، اگه بزرگتر بود توی نیمه ی سمت راست. و دوباره همینکار رو تکرار میکنیم تا به هدف برسیم. 5- Interpolation search خیلی شبیه binary search هست با این تفاوت که اونجا نقطه ای که لیست ما رو تقسیم میکرد و دقیقا وسط لیست میگرفتیم، ولی اینجا با استفاده از این فرمول، اون نقطه رو بدست میاریم: mid = low + ((key - arr[low]) * (high - low) / (arr[high] - arr[low])); low = کوچکترین ایندکس high = بزرگترین ایندکس key = آیتم هدف این فرمول نقطه ی تقسیم رو مایل به چپ یا راست پیدا میکنه، نزدیک تر به آیتم هدف. ولی برای اینکه interpolation search بتونه خیلی سریع عمل کنه، باید لیست ما به صورت یکنواخت توزیع شده باشه. 6 - Exponential search توی این روش که برای لیست های خیلی بزرگ کاربرد داره، از ابتدا شروع میکنیم به گشتن، ولی گام های ما به صورت exponential هست (توان های ۲): 0, 1, 4, 9, 16, 25, ... وقتی که آیتمی پیدا کردیم که از آیتم هدف ما بزرگتر بود، میایم اون تیکه رو دوباره فقط جست و جو میکنیم(مثل jump search) ولی دیگه این جست و جو خطی نیست بلکه روش binary search انجام میدیم. نکته: این الگوریتم ها بسته به شرایط الگوریتم های خیلی بهتری هستن از کاری که پایتون انجام میده. به پایتون حتی اگه لیست مرتب شده هم بدید باز تک تک سرچ میکنه. ولی خب نکته اینجاست که اون با C پیاده سازی شده و احتمالا توی خیلی از پیاده سازی های pure python از الگوریتم هایی با time complexity بهتر سریعتر باشه. در آینده سعی میکنم بیشتر درمورد time complexity ی هرکدوم از این انواع سرچ و اینکه کجا کدوم بهتره استفاده بشه صحبت کنیم. 🖊 @AmirSoroushh