İkili aramadan daha hızlı yapmak mümkün

 (lemire.me)
3 puan yazan GN⁺ 2026-05-01 | 1 yorum | WhatsApp'ta paylaş
  • Sıralı bir dizide değer ararken yaygın olarak kullanılan ikili arama, bir seferde yalnızca tek bir değeri karşılaştırırken, modern CPU'lar tek bir komutla birden fazla değeri aynı anda karşılaştırabilir; bu yetenek kullanılırsa arama hızı büyük ölçüde artırılabilir
  • SIMD Quad, diziyi 16'şarlı bloklara ayırdıktan sonra blok konumunu 4'lü enterpolasyon araması ile hızla daraltan ve blok içinde SIMD komutlarıyla 16 öğeyi tek seferde karşılaştıran hiyerarşik bir arama algoritmasıdır
  • Benchmark sonuçlarında Intel warm cache koşullarında ikili aramaya kıyasla 2 kattan daha hızlı performans gösterdi; Apple cold cache koşullarında da 2 kattan daha hızlıydı ve tüm ölçüm koşullarında std::binary_search'ten üstündü
  • İkili aramada olduğu gibi ikiye bölmek yerine 4'e bölmek, komut sayısını biraz artırsa da Intel'de büyük diziler için bellek düzeyi paralelliğini daha iyi kullanarak cold cache performansını iyileştiriyor
  • Ders kitabı algoritmaları günümüz CPU'larının veri paralelliği ve bellek paralelliğini varsaymadan tasarlandığı için, donanım özelliklerini yansıtan yeniden tasarımla pratikte anlamlı performans artışı elde etmek mümkün

Temel fikir

  • İkili arama aynı anda tek bir değeri karşılaştıran bir yapıya sahiptir; ancak modern 64 bit ARM ve x64 işlemciler tek komutla 8 adet 16 bit tamsayıyı eşzamanlı karşılaştırabilir
  • Bu donanım yeteneğinden yararlanılırsa arama birimi tek tek öğeler yerine blok düzeyine taşınabilir ve karşılaştırma sayısı büyük ölçüde azaltılabilir
  • Diziyi ikiye bölmek yerine 4'e bölmek (4'lü arama), komut sayısını biraz artırsa da darboğaz büyük olasılıkla komut sayısı değildir; ayrıca bellek düzeyi paralelliği de daha iyi kullanılabilir

Sıralı dizide üyelik kontrolünün temel yöntemi

  • Sıralı bir dizide bir değerin bulunup bulunmadığını kontrol etmenin en basit yolu, değerleri tek tek tarayan doğrusal aramadır; C++'ta aynı etki std::find ile elde edilebilir
  • Büyük dizilerde ikili arama daha hızlıdır ve arama aralığının ortasındaki değeri temel alarak üst ya da alt yarıyı eleme işlemini tekrarlar
  • C++'taki std::binary_search, değerin var olup olmadığını boolean olarak döndürür
  • Roaring Bitmap biçimi, boyutu 1 ila 4096 arasında değişen 16 bit tamsayı dizileri kullanır ve değer varlığını kontrol etmek için ikili arama kullanır

SIMD Quad algoritmasının yapısı

  • 16 bit işaretsiz tamsayılardan oluşan sıralı dizi, 16 öğelik sabit boyutlu bloklara bölünür
  • Her bloğun son öğesi enterpolasyon anahtarı olarak kullanılır; hedef değerin bulunma olasılığı yüksek olan tek bir bloğa aralık daraltılır, ardından bu bloğun 16 öğesi SIMD ile eşzamanlı incelenir
  • Çalışma adımları:
    • Öğe sayısı 16'dan azsa tüm dizi üzerinde basit doğrusal arama yapılır
    • Dizi, ardışık 16 öğelik bloklara ayrılır ve toplam blok sayısı num_blocks = cardinality / 16 olur
    • Blokların son öğeleri anahtar olarak kullanılarak mevcut arama aralığındaki 1/4 noktaları hedef değerle karşılaştırılır ve base ayarlanır
    • Geçerli blok bulunduğunda ARM'de NEON, x64'te SSE2 ile 16 öğe yüklenir ve paralel eşitlik karşılaştırması yapılır
    • Tam bloklara sığmayan kalan öğeler doğrusal aramayla kontrol edilir

Benchmark yöntemi

  • 2 ila 4096 arasındaki her dizi boyutu için 16 bit işaretsiz tamsayılardan oluşan sıralı 100.000 dizi üretildi
  • Her boyut için iki modda 10 milyon üyelik sorgusu çalıştırıldı
    • cold modu: Her sorgu farklı bir dizide arama yaparak cache miss durumunu simüle eder
    • warm modu: Aynı dizi art arda 100 kez aranarak cache hit durumu simüle edilir
  • Ölçülen metrik ortalama sorgu süresidir; karşılaştırılan yöntemler doğrusal arama (std::find), ikili arama (std::binary_search) ve SIMD Quad'dır
  • Ölçüm sistemleri Apple M4 (Apple LLVM) ve Intel Emerald Rapids (GCC) idi

Ölçüm sonuçları

  • Dizi büyüdükçe ikili arama, doğrusal aramayı belirgin biçimde geçer; cold cache durumunda daha fazla veri erişimi gerektiği için doğrusal arama daha da dezavantajlıdır
  • Intel platformu: warm cache'te SIMD Quad, ikili aramadan 2 kattan fazla daha hızlıdır; cold cache'te kazanç daha küçüktür
  • Apple platformu: cold cache'te SIMD Quad 2 kattan fazla daha hızlıdır; warm cache'te kazanç daha sınırlıdır
  • Tüm durumlarda SIMD Quad, std::binary_search'ten daha hızlıydı
  • SIMD bölümü, özel komutlarla işi azaltır; daha az komut ve dallanma içerdiği için hız artışının nedeni açıktır

4'lü aramanın etkisi

  • SIMD optimizasyonu korunup 4'lü enterpolasyon araması ikili aramayla değiştirilen SIMD binary sürümü de karşılaştırıldı
  • Apple platformunda 4'lü yaklaşımın etkisi küçüktü
  • Intel platformunda büyük dizilerde cold cache koşullarında 4'lü yaklaşım anlamlı bir optimizasyon sağladı
  • Intel sunucularında 4'lü arama bellek düzeyi paralelliğini daha iyi kullanıyor

Uygulamanın temel noktaları

  • simd_quad fonksiyonu uint16_t dizisini, öğe sayısı cardinality'yi ve aranacak değer pos'u alıp boolean döndürür
  • gap 16'ya sabitlenmiştir; cardinality < gap ise basit bir döngüyle arama yapılır
  • Blok arama döngüsü, n > 3 olduğu sürece 1/4, 2/4, 3/4 noktalarındaki blok sonu değerlerini okuyup karşılaştırır ve üç karşılaştırmanın toplamına göre base'i kaydırır
  • Seçilen blokta ARM NEON'un vceqq_u16 ya da x64 SSE2'nin _mm_cmpeq_epi16 komutu ile 16 öğe iki grup halinde paralel karşılaştırılır
  • Kalan öğe aralığında v >= pos olan noktada v == pos olup olmadığı döndürülür

Sonuç

  • Ders kitabı tarzı ikili arama iyi bir algoritmadır, ancak pratikte anlamlı olacak şekilde daha da hızlandırılabilir
  • Standart algoritmalar çoğu zaman günümüz bilgisayarlarının yüksek paralellik düzeyi varsayımıyla tasarlanmış değildir
  • SIMD Quad, hem bellek düzeyi paralelliğini hem de veri paralelliğini kullanmayı amaçlayan bir yaklaşımdır
  • Daha iyi algoritmalar da mümkün olabilir; daha yaratıcı yaklaşımlara ihtiyaç var
  • Kaynak kodu
  • Faster intersections between sorted arrays with shotgun

İlgili okumalar

1 yorum

 
GN⁺ 2026-05-01
Hacker News görüşleri

  • Daniel Lemire’in sözünü ettiği düşük seviye donanım optimizasyonundan ayrı olarak, ikili arama ya da onun uygulama varyantları ancak veri hakkında sıralı/monoton olması dışında hiçbir şey bilinmediğinde en iyi seçimdir
    Veri dağılımı hakkında önceden bilgi varsa, bu bilgi kullanılarak çok daha hızlı algoritmalar yapılabilir. Kâğıt sözlükte bir insanın saf ikili aramadan daha hızlı biçimde uygun sayfa grubuna gitmesi buna örnektir
    Matematiksel olarak sıralı listede arama, kapalı çevrim bir kontrol algoritmasıyla monoton bir fonksiyonun tersini bulmaya yakındır; bir maliyet fonksiyonu kurup gradyan inişi ya da hızlandırılmış türevleri de kullanılabilir. Daha genel olarak, aşırı soyutlanmış bir ifadenin çözümünü almak yerine çözmeye çalışılan belirli problem hakkında daha fazla bilgi kullanmak her zaman daha verimlidir ve donanımı daha iyi kullanarak elde edilen sabit katsayılı iyileştirmelerden çok daha büyük, ölçeklenebilir hız artışları sağlayabilir

    • İkili arama üzerine epey kafa yordum ama bundan daha iyi bir uygulama bulamadım: https://github.com/protocolbuffers/protobuf/blob/44025909eb7...
      1. Yoğun bir liste olup olmadığını O(1) ile kontrol et
      2. Üst sınırı kontrol et
      3. Yineleme sayısı sabit olan ikili arama
        Sabit yineleme sayısı dal tahmincisi için iyidir ve çekirdek döngü de hedef donanıma uygun biçimde çarpmadan kaçınarak oldukça sıkı optimize edilmiştir. Daha akıllı yapma girişimleri döngüyü kötüleştirdi ve kazanç sağlamadı. Struct dizisi biçiminde boyut 12 ve genelde N küçük olduğu için iş daha da zor
    • Treap hakkında bir yazı okuduğumu hatırlıyorum; ağaç dengesini korumak yerine ağırlık kullanarak Huffman kodlaması gibi arama derinliğini ayarlıyor ve erişim sıklıkları farklıysa ortalama erişim süresini azaltıyordu
      Yer imlerine eklemediğim için yılda iki kez yeniden arıyorum. Efsaneye göre hâlâ arıyorum
    • Doğru, ama asıl nokta çoğu zaman veri hakkında daha fazlasını bilemememiz
      Bu yüzden veritabanlarında B-tree standarttır. Veri her şey olabilir ve büyük miktarda yeni satır gelirse özellikleri her an ciddi biçimde değişebilir
      Gradyan inişi benzeri yaklaşımlarla sorguları hızlandıran algoritmalar yapılabilir ama B-tree zaten çok hızlıdır ve en kötü durum performansı, I/O gereksinimlerinin öngörülebilirliği, aralık taraması, sıralı dolaşım, önek koşulu desteği gibi pek çok avantaja da sahiptir
      Belirli veri dağılımları için daha verimli sorgu algoritmaları yapılabilir ama bunlar çoğu zaman önemli özellikleri kaybeder. Başka bir algoritma daha yakın bir başlangıç tahmini verse bile son öğeyi bulmakta yavaş kalabilir ya da ortalamada hızlı olsa bile en kötü durum performansı kullanılamayacak kadar kötü olabilir
      Kâğıt sözlükte de ilk tahminden sonra neredeyse ikili arama kullanıyorduk ve o ilk tahminin azalttığı adım sayısı sadece birkaç taneydi. Uygun sayfa grubuna geldikten sonra gerekenden biraz daha fazla lineer göz gezdiriyoruz; katı ikili arama belki daha hızlı olurdu ama sayfa çevirme süresiyle de denge kurmak gerekiyor
    • “Çözmeye çalıştığın belirli problem hakkında daha fazla bilgi kullanmak daha verimlidir” sözü hem apaçık hem de derin. Zaten ne kadar çok bilgiye sahipsen, o kadar çok bilgiye sahipsindir
    • Fritz Henglein hızlı sıralama/gruplama üzerine ilginç çalışmalar yaptı. Ana makale muhtemelen Generic Discrimination Sorting and Partitioning Unshared Data in Linear Time[1]
      Ed Kmett bu fikri Haskell için discrimination[2] kütüphanesinde rafine etti ve ilgili teknik sunum[3] da çok ilginç
      [1]: https://dl.acm.org/doi/epdf/10.1145/1411203.1411220
      [2]: https://hackage.haskell.org/package/discrimination
      [3]: https://www.youtube.com/watch?v=cB8DapKQz-I

  • “Dörtlü arama” sonuçta ikili arama döngüsünün bir adım açılmış hâli değil mi? Öğenin bulunduğu aralığı bulmak için karşılaştırma sayısı kabaca benzer görünüyor; sadece bir seferde 2 yerine 4 işleniyormuş gibi. Döngü açma ile de aynı etki alınabilir gibi

    • Bundan daha karmaşık. Modern işlemciler spekülatif yürütme yapar; karşılaştırma sonucunu tahmin eder ve yanıldığını anlayana ya da iç sınırlarına ulaşana kadar bir dal boyunca ilerlemeye devam eder. Yanlışsa spekülatif işi atar, birkaç çevrim cezası öder ve sonra başka bir başlangıç noktasından yeniden dener
      Pratikte işlemci açısından bakınca tüm döngüler zaten bir ölçüde açılmış gibidir; geriye sadece döngünün kendi küçük ek yükü kalır. İkili aramada asıl maliyet veriyi bellekten ya da önbellekten getirmektir; dolayısıyla esas mücadele, ileride lazım olacak veriyi mümkün olduğunca erken istemeyi sağlayıp gelmesini daha az beklemektir
      Dörtlü arama gibi algoritmaların farkı, her dalın yalnızca bir tarafını derinlemesine önceden getirmek yerine olası tüm durumları sığ biçimde prefetch etmeleridir. Sonuçta eninde sonunda lazım olacak prefetch mutlaka gönderilir ve gerçek yürütme yolunda kullanılmayacak veriye biraz daha az bant genişliği harcanır
      Arama algoritmalarının gerçek performansını tahmin etmek için “karşılaştırma sayısı” neredeyse işe yaramaz bir metriktir. Darboğaz, ne kadar çok karşılaştırma yapılabildiği değil, bellek ve önbellek bant genişliğinin ne kadar iyi kullanılabildiğidir. Modern işlemcinin dal davranışını iç işleyişine kadar hesaba katarsan buna döngü açma da denebilir
    • Bu, döngünün biraz açılmış bir hâli olarak görülebilir. Performans artışı komut sayısını ya da bellek okumalarını ciddi biçimde azalttığı için değil, işlemler arasındaki bağımlılığı gevşetip tamamen seri yürütmeden kaçındığı içindir. Dalların iki tarafını da spekülatif yürütmeye biraz benzetilebilir
    • Dörtlü arama aslında mevcut yinelemenin karşılaştırmasıyla aynı anda sonraki yinelemede olası iki karşılaştırmayı da birlikte yapıyor. Basit döngü açmadan biraz daha karmaşık
      Sonuçta her iki arama da sabit katsayıları farklı O(log N). Algoritma derslerinde sabitler çok önemli görünmez ama gerçek hayatta oldukça etkili olabilirler
    • Bir ölçüde doğru ama açılmış adımlar arasındaki veri bağımlılığı da kaldırılıyor
    • Çünkü işlemciler bizim safça düşündüğümüz şekilde çalışmıyor

  • Yakın zamanda üstel arama[2] hakkında da bir yazı[1] yazdım. Aranan öğelerin kendileri de sıralıyken bir dizi içinde tekrar tekrar ikili arama yapmak gerektiğinde kullanılabilecek bir algoritma ve bizim iş yükümüzde 8 kat hız artışı sağladı
    [1] https://lalitm.com/post/exponential-search/
    [2] https://en.wikipedia.org/wiki/Exponential_search

    • Üstel arama, kaynakları sıralı ID’lerle adresleyen bir REST API’de son ID’ye ihtiyaç duyulup bunun için özel bir endpoint olmadığında faydalıdır
      HEAD /users/1 -> 200 OK
      HEAD /users/2 -> 200 OK
      HEAD /users/4 -> 200 OK
      ...
      HEAD /users/2048 -> 200 OK
      HEAD /users/4096 -> 404 Not Found
      Sonra 2048 ile 4096 arasında ikili arama yaparak en son kullanıcıyı ve yan ürün olarak kullanıcı sayısını bulabilirsin. Rakip SaaS şirketlerini araştırırken bilinmesi faydalı bir bilgi

  • CPU her zaman tüm cache line’ı, genelde 64 baytı bir kerede eriştiği için bütün cache line’ı aramak daha iyi olur gibi. Veri CPU’ya geldikten sonra neredeyse bedava sayılır
    Bu yüzden “ikili” aramada orta cache line içindeki tüm değerleri kontrol edip eşleşme yoksa sola/sağa gitmeyi denemek isterdim. Cache line araması tek bir 512 bit SIMD komutuyla yapılabilir. 64 baytlık bir cache line, 32 adet 16 bit tamsayı eder; dolayısıyla basit ikili aramadan neredeyse 32 kat hızlı olabilir ya da en azından bellek erişimini 32 kat azaltır ki çoğu gerçek programda baskın olan da budur

    • İkili arama ağacında, yani sıralı vektörün üst cache line’larında hedef değeri bulma olasılığı düşüktür. Bunun yerine satır içindeki ek veriyi kullanarak arama aralığını daraltmak daha iyidir; bu da B-tree ya da B+tree’ye götürür
      4 bayt anahtar ve 4 bayt çocuk işaretçisi ya da dizi indeksi kullanırsan iç düğüm, 7 anahtar + 8 çocuk işaretçisi + 1 sonraki işaretçi ile 64 baytlık cache line’ı tam doldurabilir. 1 milyon öğede ağaç derinliği yaklaşık 20’den yaklaşık 7’ye iner ve üst seviyelerdeki birkaç adımın cache’te kalma olasılığı yüksektir
      Biraz uğraşırsan SIMD ile B-tree düğümü içindeki aramayı hızlandırabilirsin ama veri bağımlılığı çok yüksektir

  • Daha küçük dizilerde sona sentinel değeri koyulmuş lineer aramayı yenmek zaten zordur. Ancak bu iddianın muğlak olmasının nedeni “küçük”ün çok belirsiz bir koşul olması ve bu yüzden sezgisel gelmemesidir

    • Bu doğru değil. Bu yazıdaki harika benchmark’a bakarsan lineer arama yaklaşık 200–400 öğe civarında geri düşmeye başlıyor
      Genel olarak bu yazıyı beğendim. Uzun süredir merak ettiğim bir şeyi, faydalı eleme deneyleriyle birlikte eksiksiz biçimde incelemiş
    • Bu yazının anlattığı şey bu değil

  • Küçük dizilerde, 16–32 öğe civarında biraz arama deneyi yaptım ve ikili arama çok fazla dal içerdiği için en kötü yöntemlerden biriydi. Küçük dizilerde en hızlı yöntem dalsız lineer arama oldu
    Döngüyü ortada kesmeden tüm öğeleri dolaşan yaklaşım. Örneğin dizide belirli bir sayı var mı diye bakacaksan, tüm öğeler üzerindeki test sonuçlarını mantıksal OR ile birleştiriyorsun. SIMD kullanmadım ama küçük dizilerde dallar çok pahalı, bu yüzden dal olmadan tüm öğeleri doğrudan kontrol etmek daha hızlı

    • Bunun prefetcher’ın sevdiği bir erişim örüntüsü olmasından kaynaklanıp kaynaklanmadığını merak ediyorum

  • Algoritmanın açıklaması biraz kafa karıştırıcıydı
    SIMD kısmı yalnızca son aşamada, yani son 16 öğeyi ararken kullanılıyor
    Dörtlü arama kısmı 3 noktayı kontrol edip 4 yol oluşturuyor ama basitçe doğru anahtarı değil, doğru bloğu buluyor
    Ayrıntı ilginç: yazar, her bloğun son öğesini dörtlü aramada kullanıyor. İlk öğe ya da rastgele bir öğe kullanılsa algoritmanın nasıl değişeceğini merak ediyorum

  • Buradaki temel sezgi olan SIMD çoklu karşılaştırma, son aşamadan daha büyük ölçeklerde de kullanılabilir gibi görünüyor
    Taslak şu: a) gather ile eşit aralıklı 16 noktadan birden fazla öğe al b) SIMD komutuyla paralel karşılaştır c) doğru bloğa odaklan d) blok küçükse lineer aramaya geç, değilse gather/karşılaştırma döngüsünü tekrarla
    gather komutu ardışık olmayan bellekten okur ve ikili aramaya göre gerekmeyecek kadar fazla veri okuyabilir. Yine de çok yönlü karşılaştırma mümkün olur ve ikili aramanın 4 adımını tek hamlede toplarsa büyük tablolarda kazanabilir gibi
    Her veri türünde tam 16 yönlü karşılaştırma da mümkün değil. float64 aramada AVX-512’de bile 8 yönlü karşılaştırma ile sınırlısın ama int32 ve float32 için 16 yönlü karşılaştırma yapılabiliyor

    • gather aşırı yavaş. Verim peşindeki biri gather’dan kaçınır
      gather tabanlı bir yöntemden ikili aramanın gerçekte daha hızlı olma ihtimali daha yüksek bence

  • Klasik bilgisayar bilimi algoritmaları fiilen paralelliği olmayan CPU’lar için “tasarlanmış” sayılır. Birden fazla çekirdek, Hyper-threading, SIMD komutları gibi paralellik yoktur; tüm bellek erişim süreleri aynıdır, yani L1/L2/L3 cache gecikmesi gibi kavramlar yoktur; ayrıca genel/rastgele veri varsayılır
    Bu varsayımlardan herhangi birinden çıktığında performansı artırmak için yapılabilecek çok sayıda ayar ortaya çıkar
    Klasik algoritmalar, belirli veri biçimleri veya belirli CPU özellikleri/yetenekleri hakkında daha fazla şey öğrendikten sonra daha optimize çözümler geliştirmek için çok iyi bir başlangıç noktası sağlar
    Optimizasyonun sivri ucuna kadar gittiğinde genelde verinin bellekte nasıl tutulduğuna ve erişildiğine, ayrıca bunu iyileştirmek için yapılan değişikliklerin sonraki aşamalara zarar verip vermediğine bakarsın. Yıllar önce çalıştığım yerde biri kodun belirli bir kısmını fazlasıyla optimize etmişti ama o optimizasyon yüzünden sonradan gereken birçok bilgi cache’ten atıldı ve tüm uygulama daha yavaş oldu
    Bu muhtemelen Rob Pike’ın programlama için 5. kuralına, daha doğrusu The Mythical Man Month’ta Fred Brooks’un söylediğinin yeniden ifadesine yakın. Başvuru: https://www.cs.unc.edu/~stotts/COMP590-059-f24/robsrules.htm...

  • Ergenlik çağımda bir hafta sonunu, ikili arama her adımda arama uzayını yarıya indirdiği için iyiyse üçlü arama her seferinde üçte bire indiriyor, o zaman daha da iyi olmalı diye düşünerek geçirmiştim
    Ortadaki tek değeri karşılaştırmak yerine 1/3 noktasındaki değeri karşılaştırıp, çok düşükse 2/3 noktasındaki değeri karşılaştırmak gibi
    Ama her adımda ikili aramadaki 1/2 yerine 1/3’e indirirken ortalamada 3/2 kat daha fazla karşılaştırma yaptığını düşündüm; bu yüzden sonunda aynı kapıya çıktığını varsaydım
    Düzeltme: zamadatix’in yanıtını görünce aslında durumların 2/3’ünde 2 karşılaştırma gerektiği için ortalamanın 5/3 kat olduğunu fark ettim

    • Bu üçlü yaklaşımda adım başına ortalama karşılaştırma sayısı gerçekte 3/2 değil
      İlk 1/3: 1 karşılaştırma
      İkinci 1/3: 2 karşılaştırma
      Üçüncü 1/3: 2 karşılaştırma
      (1+2+2)/3 = ortalama 5/3 karşılaştırma eder. “1 ya da 2 karşılaştırma yapılıyor” hissi yüzünden %50 sanmak kolay ama gerçekte ilk karşılaştırmada sonuca gitme olasılığı 1/3, 2 karşılaştırma yapma olasılığı 2/3
      Dolayısıyla toplam ortalama karşılaştırma sayısında üçlü aramanın çok az daha kötü olduğu gösterilebilir: 5/3*Log_3[n] = 1.052... * Log_2[n]
      Yani adım sayısı azalır ama sona ulaşmak için ortalamada daha fazla karşılaştırma yaparsın. Bu tür tüm aramalarda, yani bölme sayısının 2’den büyük olduğu durumlarda genel olarak böyledir. Elbette aranan değerin eşit dağıldığı ve işlem maliyetinin idealize edildiği gibi bazı varsayımlar var; metindeki tartışma tam da bu noktada devreye giriyor
    • Meğer ergenlikteki o düşüncede de bir şey varmış
      İkili arama algoritmasının üçlü bir sürümü olarak değil. Çünkü bu gerçek bir üçlü arama değil, daha çok dengesiz bir ikili aramaya benziyor. Karşılaştırma özünde ikilidir; bu yüzden karşılaştırmaya dayalı tüm arama algoritmaları bir anlamda ikili aramadır ve ortadaki öğe dışındaki seçimler algoritmik karmaşıklık açısından daha az verimlidir. Yine de gerçek donanımda bazı koşullarda daha iyi olabilir. Gerçek üçlü arama için temel işlem olarak 3 yönlü karşılaştırma gerekir
      İşin ilginçleştiği nokta “radix verimliliği”[1] hesaba katıldığında ortaya çıkıyor. En iyi seçim, e’ye en yakın doğal sayı olan 3’tür. Ağaç aramayla da ilişkili; bu yüzden üçlü ağaçlar ikili ağaçlardan daha iyi olabilir
      [1] https://en.wikipedia.org/wiki/Optimal_radix_choice
    • Hızlı aramanın mümkün olmadığı disk gibi ortamlarda örneğin 128 yönlü B-tree kullanılabilir. 128 anahtarı getirmenin maliyeti 1 anahtarı getirmekten çok daha yüksek değildir ama ek olarak 7 getirme işlemini ortadan kaldırır
    • Peki sonra üçlü karşılaştırıcı içeren bir CPU mu hayal ettin?
    • Ergenlik günlerinden bu yana CPU’lar hem yürütme genişliği hem de vektör yetenekleri açısından dramatik biçimde büyüdü. Aktarım kapasitesi arttıkça denge, bağımlılık zincirlerini azaltmak için daha fazla işlem yakma yönüne kayıyor
      Bu yüzden o fikir o zamanki CPU’larda pratik olmayabilirdi ama bugünün CPU’larında daha olası hâle gelmiş olabilir