Yeni kitap sıralama algoritması, kusursuzluğa çok yakın performans sergiliyor

Giriş

• Yeni bir algoritma, kütüphane sıralama problemini çözmenin bir yolunu ortaya koyuyor.
• Bu problem yalnızca kitapları sıralamakla ilgili değil; sabit disklerdeki ve veritabanlarındaki dosya dizilimlerine de uygulanabiliyor.
• Yeni yaklaşım, kitaplığın geçmiş içeriği ile rastgeleliği birleştirerek kuramsal ideale yakın sonuçlar üretiyor.

Sınırları daraltmak

• İyi sıralanmış bir kitaplığı ölçmenin yaygın yolu, tek tek öğeleri eklemenin ne kadar zaman aldığına bakmaktır.
• 1981 tarihli bir makale, ortalama ekleme süresi n'den çok daha az olan bir algoritma tasarlanıp tasarlanamayacağı sorusunu ortaya attı.
• 2004 tarihli bir çalışma, kütüphane sıralama problemi için en iyi alt sınırın log n olduğunu ortaya koydu.
• Düzgün ya da deterministik algoritmaların, ortalama ekleme süresinde (log n)²'den daha iyi bir sonuca ulaşamayacağını gösterdi.

Gizli tarihçe

• 2022'de Bender ve çalışma arkadaşları, rastgele ve düzgün olmayan bir algoritmayı deneyerek ortalama ekleme süresini (log n)¹.⁵'e düşürdü.
• Bu algoritma, geçmişteki kitaplık kayıtlarına dayanmaz; bu da güvenlik açısından yararlı olabilir.

Açığı kapatmak

• Bender ve Kuszmaul, üst sınırı (log n) × (log log n)³ seviyesine indirerek kuramsal alt sınıra çok yaklaştı.
• Bu algoritma, gelecekteki olayları planlamak için sınırlı ölçüde geçmişe bağımlılık kullanıyor.
• Bu sonuç, önceki çalışmaları temel alıyor ve rastgeleliği tamamen farklı bir biçimde kullanıyor.

Sonuç

• Bu araştırma, kuramsal açıdan önemli bir iyileşmeyi temsil ediyor ve uygulama tarafında da büyük gelişme potansiyeli taşıyor.
• Yine de log log n terimi tam çözümün önünde engel olmaya devam ediyor; çözüm, ya üst sınırı düşürmek ya da alt sınırı yükseltmek olabilir.

[GN⁺]

Hacker News görüşleri

• Kriptografi tekniklerinin performansı artırmak için kullanılabilmesi ilginç. Performans, sadece daha fazla komut çalıştırmak değil, işi nasıl daha az yapacağını seçmektir. "Geçmişten bağımsızlık" adlı güvenlik özelliği, geçmişi izleme işi yapılmadığı anlamına geliyor

• Makalede bahsedilen ana makaleleri bulmak zor. Quanta tüm kaynakçayı makalenin sonunda listelese, okuyucular için faydalı olurdu

  • [1] Nearly Optimal List Labeling: bağlantı
  • [2] A sparse table implementation of priority queues: bağlantı

• Veritabanı tablolarında öğeleri rastgele yerleştirme sorununu çözmek için karmaşık algoritmalar var. Ama bu sorunun basit çözümü kesirli değerler kullanmak ve listeyi ara sıra yeniden düzenlemek

• Öğrencilere 'Library Sort' algoritmasına dayalı bir problem verdiğimi hatırlıyorum. Orijinal makalenin başlığı 'Insertion Sort is O(n log n)' idi

• Şu anda kullanılan algoritmalardan gerçekten daha hızlı olması için bir neden var mı, merak ediyorum. B-tree düğüm dizilerinde memmove() kullanmak daha hızlı olabilir. Büyük diziler için B-tree kullanmak daha kolay

• Problem tanımının sabit uzunlukta, önceden ayrılmış bir dizi varsayıp varsaymadığını merak ediyorum

• British Library'nin kitapları yönetme biçimi şaşırtıcı. Kitap geldiğinde elektronik katalog gerisini hallediyor, bu yüzden kitapları yeniden yerleştirmeye gerek kalmıyor

• Makalenin üst kısmındaki animasyonu ekran koruyucu yapmak istiyorum

• Mobil kullanıcılar için temiz bağlantılar

  • Oyun: bağlantı
  • Kod: bağlantı
  • Subpixel geometri kaynağı: bağlantı

• Üst sınırı (log n) * (log log n)^3 seviyesine indirdikleri doğru. Big-O karmaşıklığında polinom referans sınıfı kullanırken logaritmaların sonsuz küçük değerler sağlaması ilginç