Arama hızını artırdığını kanıtlayan bir lisans öğrencisi araştırması

Giriş

• 2021 sonbaharında, Rutgers University lisans öğrencisi Andrew Krapivin hayatını değiştirecek bir makaleyle karşılaştı.
• Bu makale, bilgisayar belleğinde bilgiyi işaret eden "küçük işaretçiler" hakkındaydı.
• Krapivin, işaretçileri küçülterek bellek tüketimini azaltmanın bir yolunu geliştirdi.

Yeni bir hash tablosunun keşfi

• Krapivin, verileri depolamanın yaygın bir yolu olan hash tablolarını kullanarak deneyler yürüttü.
• Deneyler sırasında Krapivin, mevcut olanlardan daha hızlı çalışan yeni bir hash tablosu türü icat etti.
• Bu keşif, veri bilimi alanında 40 yıllık bir varsayımı çürüten bir sonuç ortaya çıkardı.

Hash tablolarının önemi

• Hash tabloları, bilgisayar bilimindeki en eski veri yapılarından biridir ve veri depolamada verimlilik sağlar.
• Hash tabloları; öğeleri arama, silme ve ekleme olmak üzere üç işlevi yerine getirecek şekilde tasarlanmıştır.

Yao'nun varsayımı ve çürütülmesi

• 1985'te bilgisayar bilimci Andrew Yao, belirli özelliklere sahip hash tablolarında en kötü durumda bir öğenin nasıl bulunacağına ilişkin bir varsayım ortaya koydu.
• Krapivin'in yeni hash tablosu, Yao'nun varsayımını çürütüyor ve en kötü durumda sorgu ile ekleme için gereken sürenin (log x)² ile orantılı olduğunu kanıtlıyor.

Ortalama sorgu süresine dair yeni bulgu

• Krapivin ve ekibi, açgözlü olmayan hash tablolarında ortalama sorgu süresinin x'e bağlı olmadığını gösterdi.
• Bu, hash tablosunun doluluk oranından bağımsız olarak sabit bir ortalama sorgu süresine ulaşılabileceği anlamına geliyor.

Sonuç

• Bu araştırma, hash tablolarına dair anlayışı derinleştiriyor ve pratik uygulamalara yol açma potansiyeli taşıyor.
• Veri yapılarına yönelik bu anlayış, gelecekteki pratik iyileştirmeler için bir temel oluşturabilir.

[GN⁺]

Hacker News görüşleri

• Krapivin, Yao'nun varsayımını bilmeden bir atılım gerçekleştirmiş

  • Balatro'nun geliştiricisi de mevcut deste kurma oyunlarını bilmeden ödüllü bir deste kurma oyunu yaptı
  • Bir probleme yaklaşmanın en iyi yolu, daha önceki benzer çabalardan habersiz olmak ya da onları görmezden gelmek olabilir
  • Günümüz dünyası fazla bağlantılı; bu yüzden önceki düşünce kalıplarına kapılmak kolay
  • İnternet harika, ama düşünce dünyasını homojenleştirme eğilimi var

• Harika bir sonuç, ama buna bilgisayar bilimi varsayımı denmesi daha doğru gibi görünüyor

• Bu implementasyona sahip bir GitHub deposu bilen var mı diye merak ediyorum

• Güzel, ama bu yazının "ünlüleştirme" tarzı biraz rahatsız edici

  • Üniversite ortamında çeşitli pozlar veren genç birinin birden fazla fotoğrafını görmemiz gerçekten gerekli miydi, emin değilim
  • Bilgisayarda başarıya ulaşmış hayatta kalanları parlatıp daha fazla katılım teşvik etmek için sanki bunun bir La La Land versiyonuna ihtiyaç varmış gibi

• Yeni hash tablosunda en kötü durumda sorgu ve ekleme için gereken süre (log x)^2 ile orantılı

  • Ekibin sonucu hemen uygulanabilir uygulamalara dönüşmeyebilir
  • Bunun neden hemen uygulanabilir sonuçlara dönüşmediğini anlamıyorum
  • Gerçek kullanım senaryolarının analizinin, saf matematiksel yaklaşımdan daha iyi hash implementasyonları ayarlayabildiği bir durum olup olmadığını merak ediyorum

• Bu makaleyi okumak Monty Hall probleminin açıklamasını okumak gibi

  • Sonuç sağduyuya aykırı görünüyor, ama kanıtlanabiliyor
  • Hash tablosunun doluluk oranından bağımsız olarak sabit ortalama sorgu süresine ulaşılabilmesi, yazarların bile beklemediği bir şeydi

• Son zamanlar için iyi bir test

  • Bakalım derin araştırma bu sonucu kopyalamadan ortaya çıkarabiliyor mu
  • gpt4, Gemini 2 ve Claude bu kez şanssızdı
  • İnsan liderliğindeki bilgisayar bilimi hâlâ güvende

• 'Tiny pointers' için basit bir implementasyonu olan biri var mı diye merak ediyorum

  • Benim zihnimde kanıttan önce kod/sözde kod geliyor

• <i>Scooby Doo</i>'daki kötü adamın hep dediği gibi:

  • <i>"Ve o yaramaz çocuklar olmasaydı, başaracaktım!"</i>

• Makaleye hızlıca göz attım; kullandıkları temel fark, hash tablosu ekleme algoritmasının ilk boş yuva açgözlü biçimde doldurmak yerine daha uzağı araması gibi görünüyor

  • Bunu, tablo çok dolu olsa bile boş yuvaları verimli şekilde bulmayı kanıtlanabilir kılan bir arama sırasıyla birleştiriyorlar
  • Hash tablosu daha az doluyken ekleme yavaşlıyor, ama son kalan boş yuvayı bulamama gibi en kötü senaryodan kaçınılabiliyor

• İlginç bir teorik sonuç, ama pratikte ihtiyaç duyulandan daha büyük bir tablo ayırmaya yönelik mevcut "hile" daha iyi bir çözüm gibi görünüyor

  • Örneğin Rust'ın hashbrown'u tablonun 1/8'ini (%12,5) boş bırakarak biraz daha fazla bellek kullanıyor, ama ekleme/arama çok hızlı oluyor