Acaba bu iki arama algoritmasından hangisi daha efektif.
Binary Search hakkında bilgi için buraya, Interpolation Search hakkında bilgi için de şuraya bakınız.
Binary Search Algoritmam:
# İkili Arama Algoritması
import time
# Zaman ölçümü başlangıcı
st = time.time()
# Dizi uzunluğu ve diğer değişkenler
n = 1000000
a = [0] * n
sayac = 0
# Dizi oluşturma
for i in range(n):
a[i] = i * i + 2 * i + 7
# Aranacak değer
x = 1007
# İkili arama başlangıcı
ilk = 0
son = n - 1
o = (ilk + son) // 2
while x != a[o] and son - ilk > 1:
sayac += 1
if x < a[o]:
son = o
else:
ilk = o
o = (ilk + son) // 2
# Aranan değeri kontrol etme
if x == a[ilk]:
print(f"Aranan {x} değeri dizinin içindedir, {ilk} indis değerli sayıya eşittir.")
elif x == a[son]:
print(f"Aranan {x} değeri dizinin içindedir, {son} indis değerli sayıya eşittir.")
elif x == a[o]:
print(f"Aranan {x} değeri dizinin içindedir, {o} indis değerli sayıya eşittir.")
else:
print("Aranan değer dizide bulunmamaktadır.")
# Zaman ölçümü bitişi
et = time.time()
elapsed_time = et - st
# Sonuçların yazdırılması
print('Execution time:', elapsed_time, 'seconds')
print("Döngü sayısı:", sayac)
İnterpolation Search Algoritmam:
# Interpolation Arama Algoritması
import time
# Zaman ölçümü başlangıcı
st = time.time()
# Dizi uzunluğu ve diğer değişkenler
n = 1000000
a = [0] * n
sayac = 0
# Dizi oluşturma
for i in range(n):
a[i] = i * i + 2 * i + 7
# Aranacak değer
x = 1007
# Interpolation arama başlangıcı
ilk = 0
son = n - 1
if a[ilk] <= x <= a[son]: # x'in dizide olma ihtimalini kontrol et
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
while x != a[o] and son > ilk:
sayac += 1
if x < a[o]:
son = o - 1
else:
ilk = o + 1
# Yeni o hesaplama
if a[son] != a[ilk]: # Bölme sıfır olmamalı
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
else:
break
# Aranan değerin kontrolü
if x == a[o]:
print(f"Aranan {x} değeri dizinin içindedir, {o} indis değerli sayıya eşittir.")
else:
print("Aranan değer dizide bulunmamaktadır.")
else:
print("Aranan değer dizide bulunmamaktadır.")
# Zaman ölçümü bitişi
et = time.time()
elapsed_time = et - st
# Sonuçların yazdırılması
print('Execution time:', elapsed_time, 'seconds')
print("Döngü sayısı:", sayac)
Binary Search Sonucu (kuadratik a[i]=i*i+2*i+7):
Aranan değer dizide bulunmamaktadır.
Execution time: 0.29457950592041016 seconds
Döngü sayısı: 19
Interpolation Search Sonucu (kuadratik a[i]=i*i+2*i+7):
Aranan değer dizide bulunmamaktadır.
Execution time: 0.2633037567138672 seconds
Döngü sayısı: 32
Sonuçlara bakacak olursak; 100.000 adet bir veri seti için binary search 19 defa orta değer güncellemesi yapmış (yani 19 döngüde bulmuş) ve 0,2946 saniye içinde çözüme ulaşmış. Interpolation Search ise 32 defa orta değer güncellemesi yapmış ve 0,2633 saniye içinde çözüme ulaşmış. Oysa beklenen şey Interpolation aramasının daha az döngüde sonucu bulması idi. Bunun tek nedeni veri setinin (a[i]=i*i+2*i+7) kuadratik bir şekilde oluşturulması. Oysa veri seti lineer bir şekilde oluşturulmuş olsaydı Interpolation Search çok daha hızlı sonuç verecekti. Ancak, döngü sayısının artmış olmasına rağmen Interpolation Search saniye olarak gene de hızlı. Bunun nedeni ne olabilir? Fikirlerinizi yazarsanız sevinirim.
Şimdi fonksiyonumuzu lineer hale getirip sonuçları yeniden test edelim.
Binary Search Sonucu (lineer a[i]=2*i+7):
Aranan 1007 değeri dizinin içindedir, 500 indis değerli sayıya eşittir.
Execution time: 0.1947474479675293 seconds
Döngü sayısı: 19
Interpolation Search Sonucu (lineer a[i]=2*i+7):
Aranan 1007 değeri dizinin içindedir, 500 indis değerli sayıya eşittir.
Execution time: 0.1947193145751953 seconds
Döngü sayısı: 0
Görüldüğü gibi veri seti lineer hale gelince Interpolation Search algoritması tek döngüde sonucu buldu.
Fakat gerçek hayatta veri setleri lineer bir dağılım göstermez çoğu defa. Buradan çıkan sonuç veri setimiz hakkında bilgi sahibi olmak hangi arama algoritmasını kullanmamız gerektiği konusunda bize ipuçları sunacaktır.
Kolay gele…
İlk Yorumu Siz Yapın