پرش جستجو در پایتون

معرفی

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

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

در این مقاله پوشش خواهید داد پرش جستجو در پایتون – ترکیبی ترکیبی از جستجوی متوالی و جستجوی فاصله ای روی آرایه های مرتب شده

جستجوی پرش

با جستجوی پرش، آرایه مرتب شده از داده ها به زیر مجموعه هایی از عناصر به نام بلوک تقسیم می شود. با مقایسه کلید جستجو (مقدار ورودی) را پیدا می کنیم کاندید جستجو در هر بلوک همانطور که آرایه مرتب شده است، کاندید جستجو بالاترین مقدار یک بلوک است.

هنگام مقایسه کلید جستجو با یک نامزد جستجو، الگوریتم می تواند 1 از 3 کار را انجام دهد:

1. اگر نامزد جستجو کوچکتر از کلید جستجو باشد، بلوک بعدی را بررسی می کنیم
2. اگر نامزد جستجو بزرگتر از کلید جستجو باشد، یک جستجوی خطی انجام می دهیم روی بلوک فعلی
3. اگر نامزد جستجو با کلید جستجو یکسان است، نامزد را برگردانید

اندازه بلوک به عنوان مربع انتخاب می شود root از طول آرایه بنابراین، آرایه های با طول n اندازه بلوک دارند √n، به این صورت روی میانگین بهترین عملکرد را برای اکثر آرایه ها ارائه می دهد.

توضیح روش کارکرد آن ممکن است مفید باشد. در اینجا آمده است که چگونه Jump Search مقدار 78 را در آرایه ای از 9 عنصر پیدا می کند:

مثال بالا عنصر را در 5 مرحله پیدا می کند، زیرا دو بررسی در بخش جستجوی خطی وجود دارد.

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

پرش مراحل جستجو

ورودی ها:

• آرایه/فهرست A از اندازه n
• کلید جستجو item

خروجی:

• فهرست کلید جستجوی منطبق یا -1 اگر item یافت نشد

مراحل

• مرحله 1: طول مرتب شده را پیدا کنید فهرست منبع – n = len(A)
• گام 2: اندازه بلوک مناسب را تعیین کنید – m = √n
• مرحله 3: تکرار از شاخص شروع می شود item در i = 0 با یک قدم از m و تا زمانی که پنجره به انتهای لیست برسد ادامه می یابد.
• مرحله 4: مقایسه کنید A(i+m) (i+m آخرین شاخص یک بلوک است) و item
  • آ) اگر A(i+m) == item، برگشت i+m; کد خارج می شود
  • ب) اگر A(i+m) > item، به جستجوی خطی در داخل بلوک معروف به عنوان ادامه دهید لیست مشتق شده B = A(i: i+m)
    • هر عنصر لیست را با کلید جستجو تکرار و مقایسه کنید و مطابقت را برگردانید i در صورت یافتن؛ کد خارج می شود
  • ج) اگر A(i+m) < item، با تکرار بعدی به مرحله 4 بروید: arrows_clockwise:
• مرحله 5: عناصر لیست را که در بلوک نمی گنجند تکرار کنید و شاخص تطبیق را برگردانید i. اگر مطابقت پیدا نشد، برگردید -1; کد خارج می شود

همانطور که اکنون متوجه شدیم که چگونه کار می کند، اجازه دهید این الگوریتم را در پایتون پیاده سازی کنیم!

پیاده سازی

با دانستن اینکه Jump Search چگونه کار می کند، بیایید جلوتر برویم و آن را در Python پیاده سازی کنیم:

'''
Jump Search function
Arguments:
A    - The source list
item - Element for which the index needs to be found
'''
import math

def jump_search(A, item):
    print("Entering Jump Search")
    n = len(A)                          
    m = int(math.sqrt(n))               
    i = 0                               

    while i != len(A)-1 and A(i) < item:
        print("Processing Block - {}".format(A(i: i+m)))
        if A(i+m-1) == item:            
            return i+m-1
        elif A(i+m-1) > item:           
            B = A(i: i+m-1)
            return linear_search(B, item, i)
        i += m

    B = A(i:i+m)                        
    print("Processing Block - {}".format(B))
    return linear_search(B, item, i)

این jump_search() تابع دو آرگومان می گیرد – لیست مرتب شده در حال ارزیابی به عنوان آرگومان اول و عنصری که باید در آرگومان دوم یافت شود. این math.sqrt() تابع برای یافتن اندازه بلوک استفاده می شود. تکرار توسط a تسهیل می شود while شرط و افزایش با افزایش امکان پذیر می شود i += m.

شما متوجه شده اید که Step 4b و Step 5 داشتن یک linear_search() تابع فراخوانی شد این linear_search() عملکرد در یکی از سناریوهای زیر فعال می شود.

• Step 4b – وقتی وجود دارد تغییر در مقایسه. اگر آخرین عنصر یک بلوک/پنجره بزرگتر از item، linear_search() تحریک می شود.

• Step 5 – عناصر باقی مانده از فهرست منبع A که در یک بلوک قرار نمی گیرند به عنوان یک لیست مشتق شده به آن ارسال می شوند linear_search() تابع.

این linear_search() تابع را می توان به صورت زیر نوشت:

'''
Linear Search function
Arguments:
B    - The derived list
item - Element for which the index needs to be found
loc  - The Index where the remaining block begins
'''

def linear_search(B, item, loc):
    print("\t Entering Linear Search")
    i = 0

    while i != len(B):
        if B(i) == item:
            return loc+i
        i += 1
    return -1

در مرحله 5، عناصر باقی مانده از لیست اصلی به قسمت ارسال می شوند linear_search() به عنوان یک لیست مشتق شده عمل کنید. مقایسه با هر عنصر از لیست مشتق شده انجام می شود B.

نمایه مطابق فهرست مشتق شده به نمایه بلوک منبع اضافه می شود تا موقعیت شاخص دقیق عنصر در لیست منبع ارائه شود. اگر هیچ مسابقه ای یافت نشد، ما برمی گردیم -1 برای نشان دادن آن item پیدا نشد

قطعه کامل را می توان یافت روی GitHub.