Enterpolasyon araması

Telefon rehberinde “Taylor” adını ararken rehberi ortadan açmazsınız: sona yakın bir yerden açarsınız, çünkü T alfabede geç gelir. Enterpolasyon araması aynısını sayılarla yapar. Hedefin nerede olması gerektiğini ne kadar büyük olduğuna bakarak tahmin eder ve düzgün dağılmış verilerde bu tahmin şaşırtıcı derecede iyidir.

İlk çubuktan son çubuğa bir çizgi çekilmiş sıralı bir çubuk dizisi ve hedefin yüksekliğinin bu çizgiyle buluştuğu yere konmuş yoklama
İlk çubuktan son çubuğa bir çizgi çekilmiş sıralı bir çubuk dizisi ve hedefin yüksekliğinin bu çizgiyle buluştuğu yere konmuş yoklama

Fikir

İkili arama, ne ararsa arasın her zaman ortayı yoklar. Enterpolasyon araması ise değerleri kullanır. Listenin kalan kısmı 10'dan 100'e gidiyorsa ve hedef 70 ise hedef, ilk değerden son değere giden yolun üçte ikisindedir; bu yüzden sıraların üçte ikisindeki yeri yoklar. Formülle yoklama lo + (target − a[lo]) / (a[hi] − a[lo]) × (hi − lo) konumundadır. Yoklamadan sonra, tıpkı ikili aramadaki gibi doğru taraftaki kısmı tutar ve yeniden tahmin eder.

İki örnek

10, 20, 30, 40, 50, 60, 70, 80, 90, 100 listesinde 70'i arayan arama hemen 7. sırayı yoklar: 1 yoklamada bulunur, ikili arama ise 4 yoklama gerektirir. Şimdi 1, 2, 3, 4, 5, 6, 7, 8, 9, 999 listesini alın ve 9'u arayın. 999 yüzünden her tahmin başa yakın düşer: arama 1, 2, 3 diye sıraları birer birer yoklar ve 9 yoklama gerektirir; ikili arama ise 3 yoklama gerektirir.

Ne kadar hızlı

Değerler düzgün dağılmışsa ya da düzgün bir dağılımdan rastgele seçilmişse her yoklama kalan kısmı yaklaşık n'den yaklaşık √n'ye küçültür. Bu, ortalama yaklaşık log₂(log₂ n) yoklama demektir: bir milyar değer için bile yaklaşık 5, ikili aramada ise 30. Değerler çok düzensiz dağılmışsa bir yoklama yalnızca tek bir değeri eleyebilir ve en kötü durum, doğrusal arama kadar kötü olan n yoklamadır. Her yoklama ayrıca bir bölme işlemine mal olur; bu yüzden pratikte en çok, diskten okuma gibi yoklamaların pahalı olduğu durumlarda işe yarar.

Tarihçe ve çeşitleri

W. W. Peterson enterpolasyon aramasını 1957'de, rastgele erişimli bellekte kayıt bulmak için tanımladı. Düzgün dağılmış anahtarlar için ortalama log log n değeri 1978'de Perl, Itai ve Avni tarafından kanıtlandı. Pratik sürümler kötü verilere karşı ikili adımlar katarak korunur, örneğin enterpolasyon-ardışık arama ya da enterpolasyon-ikili arama; böylece en kötü durum log n'ye yakın kalır.

Kendiniz deneyin

Uygulamayı açın, Aranan değer alanında bir değer seçin ve Adım'a basın. Her yoklama, hedefin iki uç değer arasında ne kadar uzakta olduğunu ve bunun hangi sırayı gösterdiğini söyler. Dağılım'ı Düzgün yaptığınızda çoğu arama tek yoklamada biter; Çarpık yaptığınızda yoklamalar listenin başında ağır ağır ilerler. Son kutucuk, aynı değer için ikili aramanın kaç adım gerektireceğini gösterir.

Sık sorulan sorular

Enterpolasyon aramasının zaman karmaşıklığı nedir?

Düzgün dağılmış değerlerde ortalama O(log log n), en kötü durumda O(n). O(1) ek bellek ve sıralı bir liste gerektirir.

Enterpolasyon araması ile ikili arama arasındaki fark nedir?

İkili arama her zaman kalan kısmın ortasını yoklar. Enterpolasyon araması ise iki uçtaki değerlere bakarak hedefin olması gereken yeri yoklar. Bu, düzgün dağılmış değerlerde çok daha iyidir, çarpık değerlerde ise çok daha kötü olabilir.

Enterpolasyon aramasına hangi veriler uygundur?

Oldukça düzgün dağılmış sıralı sayısal anahtarlar: az boşluklu ardışık kimlikler, düzenli olayların zaman damgaları ya da hash'lenmiş anahtarlar. Yoklamanın pahalı, biraz aritmetiğin ucuz olduğu veriler için uygundur.

Uygulama neden farklı dağılımlar sunuyor?

Çünkü tahminlerin ne kadar iyi olacağını dağılım belirler. Düzgün değerler enterpolasyon aramasını neredeyse sihirli gösterir, çarpık değerler ise zayıflığını ortaya koyar. Bunları ikili aramanın sayısıyla karşılaştırmak, hangisinin ne zaman kullanılacağını görmenin en açık yoludur.

Denemeye hazır mısınız?

PictorX'i tarayıcınızda açın — kurulum gerekmez, başlamak için kredi kartı gerekmez.

Enterpolasyon aramasını deneyin