Yeni kitap sıralama algoritması neredeyse kusursuz performansa ulaşıyor

 (quantamagazine.org)
2 puan yazan GN⁺ 2025-01-26 | 1 yorum | WhatsApp'ta paylaş
  • Kütüphane sıralama problemi, raf düzenlemenin ötesinde sabit diskler ve veritabanlarında sıralı depolama maliyetini belirliyor; yeni çalışma ise ortalama ekleme süresini kuramsal sınıra çok yaklaştırıyor
  • 1981 tarihli algoritma deterministik ve smooth bir yaklaşımla ortalama ekleme süresini ((log n)^2) olarak garanti ediyordu, ancak 40 yılı aşkın süredir daha düşük bir üst sınır bulunamamıştı
  • Daha sonra elde edilen alt sınır sonuçları, genel algoritmalarda en iyi değerin (log n), smooth algoritmalar ile deterministik algoritmaların sınırının ise ((log n)^2) olduğunu göstererek rastgeleleştirilmiş ve smooth olmayan bir yaklaşımın gerekli olduğunu ortaya koydu
  • 2022'de Bender, Kuszmaul ve diğerleri geçmişten bağımsız (history independent) rastgeleleştirilmiş bir algoritmayla üst sınırı ((log n)^{1.5}) düzeyine indirdi; en yeni çalışma ise sınırlı geçmiş bilgisini de kullanarak ((log n)(log log n)^3) değerine ulaşıyor
  • Geriye kalan fark (log log n) terimi kadar; bu ilerleme, liste etiketlemeye dayalı dinamik grafik depolama ve işleme gibi uygulamalarda hız artışına yol açabilir

Kütüphane sıralama probleminin sorduğu şey

  • Kütüphane sıralama problemi, sıralı düzeni korurken yeni bir öğe eklemek için gereken taşıma süresini en aza indirme problemidir
  • Kitaplar bir tarafa yığılırsa, araya yeni bir kitap eklerken çok sayıda kitabı yeniden taşımak gerekir
    • Isabel Allende'nin bir kitabı eklendiğinde tüm kitapları kaydırmak gerekebilir
    • Ardından Douglas Adams'ın bir kitabı eklenirse aynı iş tekrar yaşanabilir
  • Boş alanı rafın geneline uygun şekilde dağıtmak ekleme maliyetini azaltabilir, ancak asıl mesele boşluğun nereye ve ne kadar bırakılacağıdır
  • Daha biçimsel olarak bu problem liste etiketleme (list labeling) problemi olarak bilinir ve 1981 tarihli makalede tanıtılmıştır
  • Kullanım alanı kitap raflarının ötesine geçerek sabit diskler ve veritabanlarındaki dosya ve öğe yerleşimine kadar uzanır
    • Öğe sayısı milyarlarca olabilir
    • Verimsiz yerleşim, uzun bekleme sürelerine ve yüksek hesaplama maliyetlerine yol açar

Performansa üst ve alt sınırlar üzerinden bakış

  • Sıralı yerleşimin performansı genellikle yeni bir öğenin eklenmesi için gereken süreyle değerlendirilir
  • Öğe sayısı (n) iken tüm kitapları taşımak gerekiyorsa ekleme süresi (n) ile orantılıdır
    • Bu, yeni bir öğe eklemenin alabileceği sürenin bir üst sınırı olarak görülebilir
  • 1981 tarihli makale, ortalama ekleme süresinin (n)'den çok daha aşağı çekilip çekilemeyeceğini sordu ve ((log n)^2) garantisi veren bir algoritma sundu
    • Rastgeleliğe dayanmayan bir deterministik algoritmaydı
    • Ekleme ya da silmenin yaşandığı aralık içinde öğelerin dengeli biçimde yayılması gereken smooth özelliğine sahipti
  • Araştırmacılar, üst ve alt sınırlar arasındaki farkı daraltmaya çalışır; iki değer çakıştığında algoritmanın optimal olduğu kabul edilir

Mevcut alt sınır sonuçlarının yarattığı kısıtlar

  • 2004 tarihli bir çalışma, kütüphane sıralama probleminin en genel sürümünde hiçbir algoritmanın (log n)'den daha iyi olamayacağını gösteren nihai alt sınırı ortaya koydu
  • 1990'da smooth algoritmalar için alt sınırın ((log n)^2) olduğu doğrulandı
  • 2012'de ise rastgelelik kullanmayan deterministik algoritmaların da aynı ((log n)^2) alt sınırına sahip olduğu gösterildi
  • Bu sonuçlar, yalnızca smooth algoritmalar ya da deterministik algoritmalarla 1981'deki ((log n)^2) üst sınırının iyileştirilmesinin zor olduğunu gösterdi
  • Michael Bender, daha iyi bir sonuç için rastgeleleştirilmiş ve smooth olmayan algoritmalara ihtiyaç olduğunu düşündü
    • Smooth olmayan yaklaşım, öğeleri dengeli biçimde dağıtmadığı için sezgisel olarak riskli görünüyordu
    • Rastgele seçimlerin neden yardımcı olacağı da net değildi

2022: geçmişten bağımsızlıkla üst sınırın düşmesi

  • Bender, William Kuszmaul ve diğer altı araştırmacı 2022'de geçmişten bağımsız, smooth olmayan ve rastgeleleştirilmiş bir algoritma geliştirdi
  • Geçmişten bağımsız algoritma, rafın geçmiş durumunu açığa çıkarmaz
    • Kuszmaul, rafta duran bir kitabın çıkarılması durumunda başka birinin bunu fark edemeyeceği örneğini verdi
    • Bu özellik, gizlilik veya güvenlik gerekçeleriyle kullanılabilir
  • Bu algoritma, 1981'deki üst sınırı ilk kez aşağı çekerek ortalama ekleme süresini ((log n)^{1.5}) seviyesine indirdi
  • Kuszmaul, normalde gizlilik için kullanılan bir aracın algoritmayı daha hızlı hale getirebilmesini şaşırtıcı buldu
  • Georgia Institute of Technology'den Helen Xu, geçmişten bağımsızlığı güvenlik dışındaki nedenlerle kullanma fikrinin başka problemlere de etki edebileceğini değerlendirdi

En yeni çalışma: sınırlı geçmiş bilgisi ile rastgeleliğin birleşimi

  • Bender, Kuszmaul ve diğerleri en yeni makalede üst sınırı yeniden düşürerek ((log n)(log log n)^3) değerine ulaştı
  • Bu değer, ((log n)^{1.000…1}) düzeyine karşılık geliyor ve nihai alt sınır olan (log n)'ye çok yakın
  • Yeni yaklaşım da smooth olmayan ve rastgeleleştirilmiş, ancak bu kez sınırlı ölçüde geçmişe bağımlılık (history dependence) kullanıyor
  • Algoritma, gelecekteki eklemelere hazırlanmak için geçmiş eğilimlere kısmen bakıyor
    • Nabokov, Neruda ve Ng gibi soyadı N ile başlayan yazarlardan çok sayıda kitap geldiyse, N bölümünde biraz daha fazla boş alan bırakılıyor
    • Ancak fazla alan ayrılırsa bu kez soyadı A ile başlayan yazarlardan çok sayıda kitap geldiğinde sorun yaşanabilir
  • Bender, karar verirken ne kadar geçmişe bakılacağını stratejik olarak rastgeleleştirmenin bu yaklaşımı işe yarar hale getirdiğini söylüyor
  • Seth Pettie, bu çalışmanın rastgeleliği 2022 makalesinden tamamen farklı bir biçimde kullandığını değerlendiriyor

Kalan fark ve uygulama potansiyeli

  • Geriye kalan fark küçük bir (log log n) terimi
  • Bender, üst sınırın daha da düşürülmesi mi yoksa alt sınırın yükseltilmesi mi gerektiğinin henüz bilinmediğini söylüyor
  • Pettie'ye göre fark bu kadar dar olduğunda ve sınırlardan biri doğal, diğeri yapay görünüyorsa genellikle doğru cevap doğal görünen taraftır
    • Gelecekteki iyileşmenin üst sınırı (log n)'ye düşürme yönünde olması daha olası görünüyor
    • Ancak yine de “dünya tuhaf sürprizlerle dolu” diye ekliyor
  • University of Chicago'dan Brian Wheatman, bu makalelerin kuramsal olarak önemli bir iyileşme sunduğunu ve uygulamalar açısından da büyük gelişme potansiyeli taşıdığını düşünüyor
  • Helen Xu, son dönemde liste etiketlemeye dayalı veri yapılarıyla dinamik grafiklerin depolanması ve işlenmesiyle ilgilendiğini, bu ilerlemenin bunları neredeyse kesin olarak hızlandıracağını söylüyor

İlgili okumalar

1 yorum

 
GN⁺ 2025-01-26
Hacker News yorumları

  • “Gizliliği korumak için kullanılan bir aracın başka faydalar da sağlayabilmesi” beni de şaşırttı.
    Düşününce, performansın büyük kısmı kelimenin tam anlamıyla “saat başına daha fazla komut çalıştırmak” meselesi değil; daha çok daha az iş yapmanın yolunu seçmek gibi.
    Burada bir güvenlik özelliği olan geçmişten bağımsızlık, “geçmişi izleme işini yapmaya gerek yok, hatta kelimenin tam anlamıyla yapılamaz” anlamına da geliyor; bu yüzden kriptografiyi bir kısıt olarak kullanıp gereksiz işi engelleyen ilginç bir performans yaklaşımı gibi hissettiriyor.

    • Bu yorum doğru görünmüyor. Algoritmanın yavaşlığını hesaplama süresiyle ölçüyorsanız doğru olabilir, ama burada asıl ölçüt taşınması gereken kitap sayısı.
      Anladığım kadarıyla hesaplama süresinin sınırsızca kullanılabildiği bir model söz konusu.
    • İyi bir içgörü. İyi algoritma/veri yapısı tasarımının özünün, veri kümesindeki tüm bilgiden yararlanmak olduğunu düşünürdüm.
      Örneğin listenin sıralı olduğunu bilirseniz ikili arama kullanabilirsiniz. Ama belki de ne kadar bilgiyi atlayacağını seçmek de işin özü olabilir. Yine de bu tür durumlar daha az görülüyor ve aklıma hemen basit bir örnek gelmiyor.
    • Sonuçta algoritmanın “daha çok çalışmak” yerine “daha akıllıca” çalışması için, problem bağlamının hangi kısmının seçici olarak gizlenebileceğini ve gizlenmesi gerektiğini bulma meselesi gibi görünüyor. Tuhaf.
    • Aslında daha iyi algoritma geçmişe bağımlılığı kullanıyor. Bu yüzden makaledeki bu kısmın biraz yanıltıcı olduğunu düşünüyorum.

  • Makalede açıklanan temel makaleleri, yani özgün problemle neredeyse optimal algoritma makalesi [1] ve [2]’yi bulmaya çalışan tek kişi ben miyim diye merak ettim.
    İkisi de makalenin derinlerinde bir yerde bağlantılanmış gibi görünüyor; Quanta makalenin sonunda tüm kaynakları zorunlu olarak toplasa okurlar için çok faydalı olurdu.
    [1] Nearly Optimal List Labeling:
    https://arxiv.org/abs/2405.00807
    [2] A sparse table implementation of priority queues:
    https://link.springer.com/chapter/10.1007/3-540-10843-2_34

    • İki makale de yazıda gayet açık biçimde bağlantılanmış ve okumadan sadece göz gezdirerek bile hemen bulunabiliyordu.
      “This problem was introduced in a 1981 paper” cümlesindeki “1981 paper” https://link.springer.com/chapter/10.1007/3-540-10843-2_34 adresine bağlanıyor; bir sonraki paragraftaki “Last year, in a study that was presented at the Foundations of Computer Science conference in Chicago, a team of seven researchers” cümlesinde de “a study” https://arxiv.org/abs/2405.00807 adresine bağlanıyor.
      İkisi de girişin üçüncü ve dördüncü paragraflarında, ayrıntılara, tarihe ve bağlama girilmeden önce yer alıyor. Buna “makalenin derinleri” deniyorsa, derinler ölçütünün epey farklı olması gerekir.

  • Geçen hafta tam da bu probleme bakıyordum. Bir veritabanı tablosundaki öğeleri keyfi konumlara yerleştirmek, ama mümkünse listenin geri kalanına dokunmamak istiyordum.
    Kullanıcı 5. öğeden sonra yeni bir eleman eklerse o eleman 6 oluyor, ama daha önce 5’in arkasında bulunan öğeler güncellenmiyor, gibi. Bu problemi yöneten ve teorik sınırları en aza indiren gerçekten çok incelikli algoritmalar var.
    Ancak bu belirli sürümde kesirli indeksler kullanmak ve ara sıra listeyi yeniden yerleştirmenin maliyetine katlanmak en basit çözüm gibi görünüyordu.

    • Wikipedia’daki exponential labels bölümünde bu algoritma var: https://en.m.wikipedia.org/wiki/List-labeling_problem
      Temelde etiket alanı öğe sayısına göre büyükse iyi çalışıyor. Öyle değilse daha incelikli yöntemler gerekiyor. Örneğin etiketler için yalnızca 4 baytınız varsa ve 1 milyar öğe bulunuyorsa sorun oluyor.
    • Bu problemi doğrudan mülakat sorusu olarak aldığım olmuştu.
      Hatırladığım kadarıyla pratik çözüm, elemanlar arasında boşluk bırakma yöntemiydi. Örneğin 0, 1, 2 yerine 0, 100, 200 gibi koyup gerektiğinde yeniden indekslemek. Yeterince iyi çalışacak gibi.
      Benim aklıma gelen, söylediğin gibi kesirli indekslemeydi; ama ondalıklarla uğraşmak can sıkıcı olduğundan bunu vektörle temsil edip, sözlük sırasına göre sıralanan sayı dizgeleriyle ifade edebilirsiniz.
      1 ile 2 arasına eklenen elemanın indeksi 11 olur. 11 ile 19 arasında herhangi biri olabilir. 1 ile 11 arasındaysa 101, 11 ile 2 arasındaysa 12 gibi. Ancak bu indeksler sayı değil, sözlük sırasına göre karşılaştırılan dizgelerdir.
      Mutlaka dezavantajları da vardır. Örneğin böyle indeksleri sıralamak çok daha fazla bellek kullanır; çünkü dizgeler sayılardan çok daha büyüktür. Beklenmedik bir dezavantajı olmaması için fazla zekice duruyor.
    • Eski BASIC programlarındaki satır numaralarına benziyor.
    • Teorik olarak kesirleri liste etiketi olarak kullanmak, kesirleri saklamak için sonsuz bellek gerektirir.
      Pratikte bu sınır çok kısıtlayıcı değildir; ama mesele yalnızca bir koleksiyona sıra etiketi vermek değil de bu etiketleri doğrudan dizi indeksi olarak kullanıp elemanları saklamaksa fark gerçekten sorun olur. Kütüphane sıralama problemini daha kelimesi kelimesine modelleyen biçim de bu.
    • Bu, hash tablosu zincirlemesi değil mi?

  • Birkaç yıl önce öğrencilere Library Sort algoritmasını temel alan bir problem sunduğumu hatırlıyorum.
    Orijinal makalenin başlığı hâlâ aklımda çok net: “Insertion Sort is O(n log n)”

  • Bu algoritmanın gerçek dünyada şu an kullanılan yöntemlerden gerçekten daha hızlı olmasını gerektiren bir neden var mı merak ediyorum.
    Bu problemle en çok karşılaştığım yer B-tree düğümlerindeki diziler; orada sadece memmove() kullanmaktan daha hızlı olacağından şüpheliyim, gerçekten büyük dizilerde de B-tree kullanmak daha kolay olur gibi.
    Öyleyse bu algoritma da asimptotik olarak daha hızlı olsa da, paradoksal biçimde pratikte kullanılan algoritmalardan daha yavaş kalan sınıfa giriyor. Hızlı matris çarpımı algoritmalarının, iyi uygulanmış ders kitabı tipi O(n^3) algoritmadan (GEMM) daha yavaş olması buna örnek.

    • Böyle algoritmalara bazen Galactic Algorithms deniyor: https://en.wikipedia.org/wiki/Galactic_algorithm
      Sayfadaki ilk örnek, işe yararlığını iyi açıklayan bir alıntı içeriyor:
      “Bir galactic algorithm örneği olarak, iki sayıyı çarpmanın bilinen en hızlı yöntemi 1729 boyutlu Fourier dönüşümüne dayanır. Yalnızca O(n log n) bit işlemi gerektirir, ancak büyük O gösteriminin içinde saklı sabitler büyük olduğundan pratikte kullanılmaz. Yine de bu tür algoritmaların neden faydalı olabileceğini gösterir. Yazarlar, ‘ek iyileştirmelerle yalnızca milyarlarca ya da trilyonlarca basamaklı sayılar için bile pratik hale gelmesini umduklarını’ söylüyor.”

  • üst sınırı (log n) × (log log n)^3 seviyesine indiriyor — bu da (log n)^(1.000...1) değerine karşılık geliyor ifadesi doğru.
    Polinom tabanlı aileler açısından büyük O karmaşıklığına bakarken güzel noktalardan biri, logaritmaların sonsuz küçük değer vermesidir. “Sonsuz küçükler gerçekte yoktur” diyenlere iyi bir cevap.

    • Bir dakika, ne? Bunu öğrenebileceğim bir kaynak var mı?

  • British Library’nin milyonlarca kitabı ve her hafta gelen çok sayıda yeni yayını nasıl yönettiğini öğrenince şaşırmıştım.
    Bu yıl en önce gelen kitap rafta 2025.0000001 konumuna kondu, sonraki kitap hemen yanındaki 2025.0000002 konumuna kondu. Geri kalanını elektronik katalog hallediyor.
    Kitapları yeniden karıştırmaya gerek yok, ama raflarda dolaşıp kitap arama yöntemine uymayan bir çözüm.

    • Amazon’un ürünleri bir mağaza gibi benzer olanları yan yana yerleştirmemesi aklıma geliyor. Bir elektrikli süpürge modelinin yanında mutfak tabak seti olabilir.
      Hatta toplayıcının benzer ama yanlış ürünü almaması için benzerlikten özellikle kaçınıyorlar.
      Evde de bazen ara sıra kullandığım şeyleri nereye koyduğumu sık sık unutuyorum. x-acto bıçak yedeklerini hangi dolabın hangi saklama kutusuna koyduğum gibi. Benzer şeyleri bir araya toplamaya çalışınca bir kutu taşıyor, diğeri yarı boş kalıyor.
      Bazen tüm eşyalarımı bir elektronik tabloda takip edip hangi kutuda olduklarını yazsam, hiçbir şeyi kaybetmeden depolama alanını da en verimli şekilde kullanabileceğimi hayal ediyorum. Ama yeni bir şey koyarken güncellemeyi atlayacağım kesin; ayrıca insandan çok bir robotun yapacağı, insanlık dışı derecede tuhaf bir yöntem gibi geliyor.

  • Makalenin en üstündeki animasyonla bir ekran koruyucu yapmak istedim.

  • Temel kısıtı anlamaya çalışıyorum. Problem tanımı sabit uzunluklu, önceden ayrılmış bir dizi varsayıyor mu?

    • Hayır, dizi varsaymıyor. Toplam sıralı bir kümeyi koruyan bir veri yapısı; üç işlem var:
      insert(X), delete(X), label(X)
      label, daha önce eklenmiş ve henüz silinmemiş X elemanının etiketini getirir. Etiket 0’dan n-1’e kadar bir sayıdır; n de o anda depolanan eleman sayısıdır.