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:
# ikili arama algoritması
import time
st=time.time()
n = 1000000
a = [0] * (n)
sayac=0
for i in range(0, n - 1 + 1, 1):
a[i] = i*i+2*i+7
x = 1007
ilk = 0
son = n - 1
o = int((ilk + son) / 2)
while x != a[o] and son - o > 1:
sayac=sayac+1
if x < a[o]:
son = o
o = int((ilk + son) / 2)
else:
ilk = o
o = int((ilk + son) / 2)
if x == a[ilk]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(ilk) + " indis değerli sayıya eşittir.")
else:
if x == a[son]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(son) + " indis değerli sayıya eşittir.")
else:
if x == a[o]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(o) + " indis değerli sayıya eşittir.")
else:
print("Aranan değer dizide bulunmamaktadır.")
et=time.time()
elapsed_time = et - st
print('Execution time:', elapsed_time, 'seconds')
print(sayac)
İnterpolation Search Algoritmam:
# interpolation arama algoritması
import time
st=time.time()
n = 1000000
a = [0] * (n)
sayac=0
for i in range(0, n - 1 + 1, 1):
a[i] = i*i+2*i+7
x = 1007
ilk = 0
son = n - 1
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
while x != a[o] and son - o > 1:
sayac=sayac+1
if x < a[o]:
son = o
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
else:
ilk = o
o = ilk + int(((x - a[ilk]) * (son - ilk)) / (a[son] - a[ilk]))
if x == a[ilk]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(ilk) + " indis değerli sayıya eşittir.")
else:
if x == a[son]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(son) + " indis değerli sayıya eşittir.")
else:
if x == a[o]:
print("Aranan " + str(x) + " değeri dizinin içindedir, " + str(o) + " indis değerli sayıya eşittir.")
else:
print("Aranan değer dizide bulunmamaktadır.")
et=time.time()
elapsed_time = et - st
print('Execution time:', elapsed_time, 'seconds')
print(sayac)
Binary Search Sonucu (kuadratik a[i]=i*i+2*i+7):
Interpolation Search Sonucu (kuadratik a[i]=i*i+2*i+7):
Sonuçlara bakacak olursak; 100.000 adet bir veri seti için binary search 16 defa orta değer güncellemesi yapmış (yani 16 döngüde bulmuş) ve 0,046875 saniye içinde çözüme ulaşmış. Interpolation Search ise 31 defa orta değer güncellemesi yapmış ve 0,03125 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):
Interpolation Search Sonucu (lineer a[i]=2*i+7):
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.