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

معرفی

جستجوی داده‌های ذخیره‌شده در ساختارهای داده مختلف، بخش مهمی از تقریباً هر برنامه کاربردی است. الگوریتم های مختلفی برای استفاده در هنگام جستجو وجود دارد و هر کدام پیاده سازی ها و تکیه های متفاوتی دارند. روی ساختارهای داده مختلف برای انجام کار

توانایی انتخاب یک الگوریتم خاص برای یک کار مشخص، یک مهارت کلیدی برای توسعه دهندگان است و می تواند به معنای تفاوت بین یک برنامه سریع، قابل اعتماد و پایدار و برنامه ای باشد که از یک درخواست ساده از بین می رود.

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

اپراتورهای عضویت

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

یکی از رایج ترین مشکلات در حوزه علوم کامپیوتر جستجو در یک مجموعه و تعیین اینکه آیا یک شی معین در مجموعه موجود است یا خیر.

تقریباً هر زبان برنامه نویسی پیاده سازی خاص خود را از یک الگوریتم جستجوی پایه دارد، معمولاً به عنوان تابعی که a را برمی گرداند Boolean ارزش True یا False هنگامی که یک مورد در یک مجموعه معین از اقلام یافت می شود.

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

این in اپراتور برمی گرداند True اگر عنصر داده شده بخشی از ساختار باشد. از سوی دیگر، not in برمی گرداند True اگر عنصر داده شده بخشی از ساختار نباشد. نگاهی بیاندازید:

print('apple' in ('orange', 'apple', 'grape'))


print('t' in 'rasanegar')


print('q' in 'rasanegar')


print('q' not in 'rasanegar')

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

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

جستجوی خطی

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

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

def LinearSearch(numbers, element):
    for i in range (len(numbers)):
        if numbers(i) == element:
            return i
    return -1

بنابراین اگر از تابع برای محاسبه استفاده کنیم:

numbers = (1,2,3,4,5,2,1)
index = LinearSearch(numbers, 2)
print(index)

پس از اجرای کد، ما با استقبال مواجه می شویم:

1

این نمایه اولین رخداد موردی است که ما به دنبال آن هستیم – با در نظر گرفتن این که شاخص های پایتون مبتنی بر 0 هستند.

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

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

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

جستجوی باینری

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

با فرض اینکه ما به دنبال یک مقدار هستیم val در یک آرایه مرتب شده، الگوریتم مقایسه می کند val به مقدار عنصر میانی آرایه که آن را فراخوانی می کنیم mid:

• اگر mid عنصری است که ما به دنبال آن هستیم (بهترین حالت)، شاخص آن را برمی گردانیم.
• اگر نه، ما تشخیص می دهیم که کدام طرف mid val احتمال بیشتری وجود دارد روی مستقر روی چه val کوچکتر یا بزرگتر از mid، و طرف دیگر آرایه را دور بیندازید.
• سپس به صورت بازگشتی یا تکراری همان مراحل را دنبال می کنیم و مقدار جدیدی را برای آن انتخاب می کنیم mid، مقایسه آن با val و نیمی از مطابقت های ممکن را در هر تکرار الگوریتم کنار بگذارید.

الگوریتم جستجوی دودویی را می توان هر دو نوشت به صورت بازگشتی یا به صورت مکرر. بازگشت به طور کلی در پایتون کندتر است زیرا مستلزم تخصیص قاب های پشته ای جدید است.

از آنجایی که یک الگوریتم جستجوی خوب باید تا حد امکان سریع و دقیق باشد، بیایید آن را در نظر بگیریم اجرای تکراری جستجوی دودویی:

def BinarySearch(numbers, val):
    first = 0
    last = len(numbers)-1
    index = -1
    while (first <= last) and (index == -1):
        mid = (first+last)//2
        if numbers(mid) == val:
            index = mid
        else:
            if val<numbers(mid):
                last = mid -1
            else:
                first = mid +1
    return index

اگر از تابع برای پیدا کردن استفاده کنیم 20 در آرایه (10,20,30,40,50):

numbers = (10,20,30,40,50)
index = BinarySearch(numbers, 20)
print(index)

نتیجه را می گیریم:

1

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

• برگرداندن شاخص عنصر فعلی
• جستجو در نیمه چپ آرایه
• جستجو در نیمه سمت راست آرایه

ما فقط می‌توانیم یک امکان را در هر تکرار انتخاب کنیم، و مجموعه تطابق‌های احتمالی ما در هر تکرار بر دو تقسیم می‌شود. این باعث پیچیدگی زمانی جستجوی باینری می شود O (log n).

یکی اشکال جستجوی دودویی این است که اگر چندین عنصر در آرایه وجود داشته باشد، ایندکس عنصر اول را برمی‌گرداند، بلکه شاخص نزدیک‌ترین عنصر به وسط را برمی‌گرداند:

numbers = (4,4,4,4,4)
index = BinarySearch(numbers, 4)
print(index)

اجرای این قطعه کد به نمایه عنصر میانی منجر می شود:

1

برای مقایسه انجام یک جستجوی خطی روی همان آرایه برمی گردد:

0

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

اگر جستجوی باینری انجام دهیم روی آرایه (1,2,3,4,4,5) به عنوان مثال، و جستجو برای 4، ما دریافت می کنیم 3 در نتیجه.

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

جستجوی پرش

جستجوی پرش شبیه جستجوی باینری است که کار می کند روی یک آرایه مرتب شده و از یک آرایه مشابه استفاده می کند تفرقه بینداز و حکومت کن رویکردی برای جستجو از طریق آن

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

با توجه به یک آرایه مرتب شده، به جای جستجوی تدریجی در عناصر آرایه، در آن جستجو می کنیم می پرد. بنابراین در لیست ورودی ما numbers، اگر اندازه پرش داشته باشیم پرش الگوریتم ما عناصر را به ترتیب در نظر می گیرد numbers(0)، numbers(0+jump)، numbers(0+2jump)، numbers(0+3jump)، و غیره روی.

با هر پرش، مقدار قبلی و شاخص آن را ذخیره می کنیم. وقتی مجموعه ای از مقادیر را پیدا می کنیم که در آن numbers(i)< عنصر<numbers(i+jump)، جستجوی خطی را با انجام می دهیم numbers(i) به عنوان چپ ترین عنصر و numbers(i+jump) به عنوان سمت راست ترین عنصر در مجموعه جستجوی ما:

import math

def JumpSearch (numbers, val):
    length = len(numbers)
    jump = int(math.sqrt(length))
    left, right = 0, 0
    while left < length and numbers(left) <= val:
        right = min(length - 1, left + jump)
        if numbers(left) <= val and numbers(right) >= val:
            break
        left += jump;
    if left >= length or numbers(left) > val:
        return -1
    right = min(length - 1, right)
    i = left
    while i <= right and numbers(i) <= val:
        if numbers(i) == val:
            return i
        i += 1
    return -1

از آنجایی که این یک الگوریتم پیچیده است، بیایید محاسبه گام به گام جستجوی پرش را با این ورودی در نظر بگیریم:

numbers = (1,2,3,4,5,6,7,8,9)
index = JumpSearch(numbers, 5)
print(index)

• جستجوی پرش ابتدا اندازه پرش را با محاسبه تعیین می کند math.sqrt(len(numbers)). از آنجایی که ما 9 عنصر داریم، اندازه پرش √9 = 3 خواهد بود.
• بعد، مقدار the را محاسبه می کنیم right متغیر، که حداقل طول آرایه منهای 1 یا مقدار است left+jump، که در مورد ما 0+3= 3 خواهد بود. از آنجایی که 3 کوچکتر از 8 است، از 3 به عنوان مقدار استفاده می کنیم. right.
• اکنون بررسی می کنیم که آیا عنصر جستجوی ما، 5، بین است یا خیر numbers(0) و numbers(3). از آنجایی که 5 بین 1 و 4 نیست، حرکت می کنیم روی.
• در مرحله بعد، دوباره محاسبات را انجام می دهیم و بررسی می کنیم که آیا عنصر جستجوی ما بین است یا خیر numbers(3) و numbers(6)، که در آن 6 3 + پرش است. از آنجایی که 5 بین 4 و 7 است، جستجوی خطی انجام می دهیم روی عناصر بین numbers(3) و numbers(6) و شاخص عنصر ما را به صورت زیر برگردانیم:

4

پیچیدگی زمانی جستجوی پرش است O(√n)، جایی که √n اندازه پرش است و n طول لیست است که از نظر کارایی، جستجوی پرش را بین الگوریتم های جستجوی خطی و جستجوی باینری قرار می دهد.

مهمترین مزیت جستجوی پرش در مقایسه با جستجوی باینری این است که متکی نیست روی اپراتور تقسیم (/).

در اکثر CPU ها، استفاده از عملگر تقسیم در مقایسه با سایر عملیات های حسابی پایه (جمع، تفریق و ضرب) پرهزینه است، زیرا اجرای الگوریتم تقسیم تکراری است.

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

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

جستجوی فیبوناچی

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

اعداد فیبوناچی با صفر شروع می شوند و از الگو پیروی می کنند 0، 1، 1، 2، 3، 5، 8، 13، 21… که در آن هر عنصر جمع دو عددی است که بلافاصله قبل از آن قرار می گیرند.

این الگوریتم با سه عدد فیبوناچی در یک زمان کار می کند. بیایید با این سه شماره تماس بگیریم fibM، fibM_minus_1، و fibM_minus_2 جایی که fibM_minus_1 و fibM_minus_2 دو عدد بلافاصله قبل هستند fibM به ترتیب:

fibM = fibM_minus_1 + fibM_minus_2

ما مقادیر را به 0،1 و 1 یا سه عدد اول در دنباله فیبوناچی مقداردهی می کنیم تا از دریافت خطای شاخص در مواردی که آرایه جستجوی ما numbers شامل تعداد بسیار کمی از اقلام است.

سپس کوچکترین عدد دنباله فیبوناچی را انتخاب می کنیم که بزرگتر یا مساوی تعداد عناصر موجود در آرایه جستجوی ما باشد. numbers، به عنوان ارزش fibM، و دو عدد فیبوناچی بلافاصله قبل از آن به عنوان مقادیر fibM_minus_1 و fibM_minus_2. در حالی که آرایه دارای عناصر باقی مانده و مقدار است fibM بزرگتر از یک است، ما:

• مقایسه کنید val با مقدار بلوک در محدوده تا fibM_minus_2و در صورت مطابقت، شاخص عنصر را برگردانید.
• اگر مقدار از عنصری که در حال حاضر به آن نگاه می کنیم بیشتر باشد، مقادیر آن را جابجا می کنیم fibM، fibM_minus_1، و fibM_minus_2 در دنباله فیبوناچی دو پله پایین آمده و شاخص را به شاخص عنصر تنظیم مجدد کنید.
• اگر مقدار کمتر از عنصری باشد که در حال حاضر به آن نگاه می کنیم، مقادیر آن را جابجا می کنیم fibM، fibM_minus_1، و fibM_minus_2 یک پله پایین تر در دنباله فیبوناچی.

بیایید نگاهی به پیاده سازی پایتون این الگوریتم بیندازیم:

def FibonacciSearch(numbers, val):
    fibM_minus_2 = 0
    fibM_minus_1 = 1
    fibM = fibM_minus_1 + fibM_minus_2
    while (fibM < len(numbers)):
        fibM_minus_2 = fibM_minus_1
        fibM_minus_1 = fibM
        fibM = fibM_minus_1 + fibM_minus_2
    index = -1;
    while (fibM > 1):
        i = min(index + fibM_minus_2, (len(numbers)-1))
        if (numbers(i) < val):
            fibM = fibM_minus_1
            fibM_minus_1 = fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
            index = i
        elif (numbers(i) > val):
            fibM = fibM_minus_2
            fibM_minus_1 = fibM_minus_1 - fibM_minus_2
            fibM_minus_2 = fibM - fibM_minus_1
        else :
            return i
    if(fibM_minus_1 and index < (len(numbers)-1) and numbers(index+1) == val):
        return index+1;
    return -1

اگر از FibonacciSearch تابع برای محاسبه:

numbers = (1,2,3,4,5,6,7,8,9,10,11)
index = FibonacciSearch(numbers, 6)
print(index)

بیایید نگاهی به مرحله به مرحله بیاندازیم process از این جستجو:

• تعیین کوچکترین عدد فیبوناچی بزرگتر یا مساوی طول لیست به عنوان fibM; در این حالت، کوچکترین عدد فیبوناچی که نیازهای ما را برآورده می کند، است 13.
• مقادیر به صورت زیر تخصیص داده می شود:
  • fibM = 13
  • fibM_minus_1 = 8
  • fibM_minus_2 = 5
  • index = -1
• بعد، عنصر را بررسی می کنیم numbers(4) که در آن 4 حداقل 1+5 است. از آنجایی که ارزش numbers(4) 5 است که کوچکتر از مقدار مورد جستجوی ما است، اعداد فیبوناچی را جابجا می کنیم یکی در ترتیب پایین آمده و مقادیر را ایجاد کنید:
  • fibM = 8
  • fibM_minus_1 = 5
  • fibM_minus_2 = 3
  • index = 4
• بعد، عنصر را بررسی می کنیم numbers(7) که در آن 7 حداقل 4+3 است. از آنجایی که ارزش numbers(7) 8 است، که بزرگتر از مقداری است که به دنبال آن هستیم، اعداد فیبوناچی را جابجا می کنیم دو به ترتیب پایین می آید.
  • fibM = 3
  • fibM_minus_1 = 2
  • fibM_minus_2 = 1
  • index = 4
• اکنون عنصر را بررسی می کنیم numbers(5) که در آن 5 حداقل 4+1 است. ارزش numbers(5) 6 است که است ارزشی که ما به دنبال آن هستیم!

نتیجه همانطور که انتظار می رود این است:

5

پیچیدگی زمانی برای جستجوی فیبوناچی است O (log n); همان جستجوی باینری این بدان معناست که الگوریتم در بیشتر موارد از جستجوی خطی و جستجوی پرش سریعتر است.

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

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

جستجوی نمایی

جستجوی نمایی یکی دیگر از الگوریتم های جستجو است که می تواند به سادگی در پایتون پیاده سازی شود، در مقایسه با جستجوی پرش و جستجوی فیبوناچی که هر دو کمی پیچیده هستند. با نام ها نیز شناخته می شود جستجوی تاخت و تاز، دو برابر شدن جستجو، و جستجوی Struzik.

جستجوی نمایی بستگی دارد روی جستجوی باینری برای انجام مقایسه نهایی مقادیر. الگوریتم بر اساس:

• تعیین محدوده ای که عنصر مورد نظر ما احتمالا در آن قرار دارد
• استفاده از جستجوی باینری برای محدوده برای یافتن شاخص دقیق مورد

پیاده سازی پایتون از الگوریتم جستجوی نمایی به شرح زیر است:

def ExponentialSearch(numbers, val):
    if numbers(0) == val:
        return 0
    index = 1
    while index < len(numbers) and numbers(index) <= val:
        index = index * 2
    return BinarySearch( arr(:min(index, len(numbers))), val)

اگر از تابع برای یافتن مقدار زیر استفاده کنیم:

numbers = (1,2,3,4,5,6,7,8)
index = ExponentialSearch(numbers, 3)
print(index)

الگوریتم بر اساس:

• بررسی اینکه آیا اولین عنصر در لیست با مقدار مورد جستجوی ما مطابقت دارد – since numbers(0) 1 است و ما به دنبال 3 هستیم، شاخص را روی 1 قرار می دهیم و حرکت می کنیم روی.
• با مرور تمام عناصر موجود در لیست، و در حالی که آیتم در موقعیت شاخص کمتر یا مساوی مقدار ما است، به طور تصاعدی ارزش را افزایش می دهیم. index در مضرب دو:
  • index = 1، numbers(1) 2 است که کمتر از 3 است، بنابراین شاخص در 2 ضرب می شود و روی 2 تنظیم می شود.
  • index = 2، numbers(2) 3 است که برابر با 3 است، بنابراین شاخص در 2 ضرب می شود و 4 می شود.
  • index = 4، numbers(4) 5 است که بزرگتر از 3 است. حلقه در این نقطه شکسته است.
• سپس یک جستجوی باینری را با برش دادن لیست انجام می دهد. arr(:4). در پایتون، این بدان معنی است که فهرست فرعی شامل تمام عناصر تا عنصر چهارم خواهد بود، بنابراین ما در واقع فراخوانی می کنیم:

index = BinarySearch((1,2,3,4), 3)
print(index)

که برمی گردد:

2

ایندکس عنصری است که هم در لیست اصلی و هم در لیست تکه‌ای که پاس می‌دهیم جستجو می‌کنیم. روی به الگوریتم جستجوی دودویی

جستجوی نمایی اجرا می شود O (log i) زمان، کجا من نمایه موردی است که ما به دنبال آن هستیم. در بدترین حالت، پیچیدگی زمانی است O (log n)، زمانی که آخرین مورد مورد جستجوی ما باشد (n طول آرایه است).

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

جستجوی درون یابی

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

index = low + ((val-numbers(low))*(high-low) / (numbers(high)-numbers(low)))

جایی که متغیرها عبارتند از:

• numbers – آرایه ورودی ما
• val – عنصری که ما به دنبال آن هستیم
• index – شاخص احتمالی عنصر جستجو. زمانی که مقدار val به عنصر انتهای آرایه نزدیک‌تر باشد، این مقدار بالاتر محاسبه می‌شود.numbers(high)(numbers(low))
• low – شاخص شروع آرایه
• high – آخرین شاخص آرایه

الگوریتم با محاسبه مقدار جست و جو می کند index:

• اگر مطابقت پیدا شد (زمانی که numbers(index) == val، شاخص برگردانده می شود
• اگر ارزش از val کمتر است از numbers(index)، مقدار شاخص با استفاده از فرمول زیر آرایه سمت چپ مجدداً محاسبه می شود
• اگر ارزش از val بزرگتر است از numbers(index)، مقدار شاخص با استفاده از فرمول زیر آرایه سمت راست مجدداً محاسبه می شود

بیایید جلو برویم و جستجوی درون یابی را با استفاده از پایتون پیاده سازی کنیم:

def InterpolationSearch(numbers, val):
    low = 0
    high = (len(numbers) - 1)
    while low <= high and val >= numbers(low) and val <= numbers(high):
        index = low + int(((float(high - low) / ( numbers(high) - numbers(low))) * ( val - numbers(low))))
        if numbers(index) == val:
            return index
        if numbers(index) < val:
            low = index + 1;
        else:
            high = index - 1;
    return -1

اگر از تابع برای محاسبه استفاده کنیم:

numbers = (1,2,3,4,5,6,7,8)
index = InterpolationSearch(numbers, 6)
print(index)

مقادیر اولیه ما این خواهد بود:

• val = 6،
• low = 0،
• high = 7،
• numbers(low) = 1،
• numbers(high) = 8،
• index = 0 + ((6-1)*(7-0)/(8-1)) = 5

از آنجا که numbers(5) است 6، که مقداری است که به دنبال آن هستیم، اجرا را متوقف می کنیم و نتیجه را برمی گردانیم:

5

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

پیچیدگی زمانی جستجوی درون یابی است O (log log n) زمانی که مقادیر به طور یکنواخت توزیع می شوند. اگر مقادیر به طور یکنواخت توزیع نشوند، در بدترین حالت پیچیدگی زمانی وجود دارد بر)، همان جستجوی خطی است.

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

چرا از پایتون برای جستجو استفاده کنیم؟

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

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

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

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

import time

start = time.time()

end = time.time()
print(start-end)

نتیجه

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

انتخاب الگوریتم مورد استفاده بر اساس آن است روی داده هایی که باید از طریق آن جستجو کنید؛ آرایه ورودی شما، که ما آن را فراخوانی کرده ایم numbers در تمام پیاده سازی های ما

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

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