Bölüm 9 · Yazılımın içi · Ders 38

İkili arama

Sıralı kalibrasyon tablosunda her adımda yarıyı elemek

Veri. Robotun kızılötesi mesafe sensörü için 64 satırlık bir kalibrasyon tablosu var: her satırda bir ADC okuması (artan sırada) ve ona karşılık gelen mesafe. Sensör saniyede 100 kez okuma verir; her okumada robot tablodaki doğru satırı bulup mesafeyi oradan hesaplamalı. Satır satır aramak mı, ortadan bölmek mi?

32 satırlık sıralı kalibrasyon tablosu32 satır · sınır ⌈log2(32+1)⌉ = 6 adım

1 / 39

Aranan değer (ADC) 302Dizi boyu 32

ikili_arama.pypython

import numpy as np
rng = np.random.default_rng(7)
n = 32 # tablo boyu
adc = np.cumsum(rng.integers(4, 26, n)) # artan ADC tablosu
x = int(adc[21]) # aranan okuma
lo, hi, steps = 0, n, 0 # aralık [lo, hi)
while lo < hi:
mid = (lo + hi) // 2 # ortadaki satır
steps += 1
if adc[mid] < x: # tek karşılaştırma
lo = mid + 1 # sol yarıyı ele
else:
hi = mid # sağ yarıyı ele
found = lo < n and adc[lo] == x
lin = next((i + 1 for i in range(n) if adc[i] >= x), n) # doğrusal arama
print("satır", lo, "bulundu", found)
print("ikili", steps, "doğrusal", lin)
print("sınır", int(np.ceil(np.log2(n + 1)))) # ⌈log2(n+1)⌉

Sahnedeki her sayı, aynı algoritmanın tarayıcında yapılan gerçek çalıştırmasından gelir (sabit tohum, her seferinde aynı sonuç). Python kodunu kendi bilgisayarında çalıştırırsan rastgele başlangıçlar farklı olacağı için sayılar biraz değişebilir.

Veri seti

Tüm veri setleri →

Bu dersin kodu verisini kendi içinde üretir; indirilecek dosya yok. Kodu yine de aşağıda tarayıcında çalıştırabilirsin.

Kodu tarayıcıda çalıştırPython · NumPy · matplotlib · Pyodide

Python ve NumPy bu sayfada, tarayıcında çalışır (Pyodide). Kodu değiştirip yeniden çalıştırabilirsin; dersin veri setleri çalışma klasöründe hazır. Kod matplotlib kullanırsa grafikler çıktının altında görünür, yazdığı dosyalar (ör. egitim_gecmisi.csv) indirilebilir.

ikili_arama.pypython

import numpy as np
rng = np.random.default_rng(7)
n = 32                                        # tablo boyu
adc = np.cumsum(rng.integers(4, 26, n))       # artan ADC tablosu
x = int(adc[21])                              # aranan okuma
lo, hi, steps = 0, n, 0                       # aralık [lo, hi)
while lo < hi:
    mid = (lo + hi) // 2                      # ortadaki satır
    steps += 1
    if adc[mid] < x:                          # tek karşılaştırma
        lo = mid + 1                          # sol yarıyı ele
    else:
        hi = mid                              # sağ yarıyı ele
found = lo < n and adc[lo] == x
lin = next((i + 1 for i in range(n) if adc[i] >= x), n)  # doğrusal arama
print("satır", lo, "bulundu", found)
print("ikili", steps, "doğrusal", lin)
print("sınır", int(np.ceil(np.log2(n + 1))))  # ⌈log2(n+1)⌉

Kendi CSV’ni yükle

Çıktı

Çıktı burada görünecek.

Nasıl çalışır

Aralık [lo, hi) bütün tabloyla başlar. Ortadaki satıra (mid) bakılır.
Ortadaki değer aranandan küçükse aranan sağ yarıdadır (lo = mid + 1); değilse sol yarıdadır (hi = mid). Öbür yarı bir daha hiç okunmaz.
Her adım aralığı yarıya indirir: n satırda en çok ⌈log2(n+1)⌉ adım. 64 satır 7 adımda biter; doğrusal arama ortalama 32 satıra bakar.
Değer tabloda yoksa lo, onun sokulacağı yeri (ekleme noktasını) verir; robot iki komşu satır arasında ara değer bulur. Python'daki bisect modülü tam olarak budur.
Şunu dene: dizi boyunu 8’den 64’e çıkar; doğrusal sayaç 8 kat büyürken ikili sayaç yalnız 3 adım artar.

Neden önemli

Sıralı veride arama her yerde: sensör kalibrasyon tabloları, zaman damgalı kayıtlarda belirli bir ana gitmek, veritabanı indeksleri, git bisect ile hatalı commit'i bulmak. Robotun kontrol döngüsünde milisaniyeler sayılır; log2(n) adım, tablo büyüse de süreyi neredeyse sabit tutar.

ESOF 323, 11. hafta: robotlarda derin öğrenme →