Yeni verimli sayma algoritması geliştirildi
Giriş
- Hayal edin, ilkel bir ormanda yaban hayatı sensör çalışması yürütüyorsunuz.
- Dijital kamerayla hayvan fotoğrafları çekiyor ve tekrar etmeyen hayvanların sayısını bilmek istiyorsunuz.
- Mevcut yöntemler tüm hayvanları hatırlayıp karşılaştırmayı gerektirir, ancak bu verimsizdir.
Sorun durumu
- Facebook gibi büyük ölçekli platformlarda her gün giriş yapan benzersiz kullanıcıların sayısını saymak zordur.
- Kısa süre önce bilgisayar bilimcileri, uzun listelerdeki benzersiz öğe sayısını tahmin etmek için yeni bir yöntem önerdi.
- Bu algoritma yalnızca az sayıda öğeyi hatırlamayı gerektirir.
CVM algoritması
- CVM algoritması, 40 yıldan uzun süredir araştırılan benzersiz öğeler problemini çözmede önemli bir adımdır.
- Bu algoritma, veri akışındaki benzersiz öğe sayısını verimli biçimde tahmin edebilir.
- "Yeni algoritma şaşırtıcı derecede basit ve uygulanması kolay" - Andrew McGregor
Örnek: Hamlet sesli kitabı
- Hamlet'te 30.557 kelime vardır. Bunların kaçının benzersiz olduğunu öğrenmek için normalde tüm kelimeleri hatırlamak gerekir.
- CVM algoritması, bellek kullanımını azaltmak için rastgeleleştirme kullanır.
CVM algoritmasının çalışma şekli
- Birinci tur: 100 kelime kaydedilir ve tekrar eden kelimeler yazı tura atılarak silinir.
- İkinci tur: tekrar eden kelimeleri elde tutmayı daha zorlaştırmak için iki kez yazı tura atılması gerekir.
- Üçüncü tur: üç kez yazı tura atılması gerekir.
- Benzersiz kelime sayısı,
k'inci tura kadar bu işlem tekrarlanarak tahmin edilir.
Doğruluk doğrulaması
- Doğruluk, bellek boyutuna göre değişir.
- Hamlet'teki benzersiz kelime sayısı 3.967'dir; 100 bellekle ortalama tahmin 3.955, 1.000 bellekle ise ortalama tahmin 3.964'tür.
Sonuç
- "Temel ve iyi çalışılmış problemlerde bile basit ama sezgisel olmayan çözümler bulunabilir" - William Kuszmaul
GN⁺ görüşü
- Veri akışı ortamlarında faydalı: CVM algoritması, büyük veri akışlarında benzersiz öğeleri verimli biçimde tahmin edebildiği için gerçek zamanlı analizlerde faydalıdır.
- Bellek verimliliği: Bellek kullanımını en aza indirirken yüksek doğruluğu koruyabildiğinden, bellek kısıtı olan ortamlarda özellikle avantajlıdır.
- Rastgeleleştirmenin önemi: Rastgeleleştirme sayesinde karmaşık bir problemin basitçe çözülebilmesi, başka alanlarda da uygulanma potansiyelinin yüksek olduğunu gösterir.
- Teknolojinin benimsenmesinde dikkat edilmesi gerekenler: Bu algoritma benimsenirken bellek boyutu ile doğruluk arasındaki denge göz önünde bulundurulmalıdır. Bellek yeterli değilse doğruluk düşebilir.
- İlgili teknolojiler: HyperLogLog gibi diğer benzersiz öğe tahmin algoritmalarıyla karşılaştırmaya değerdir. Her algoritmanın artı ve eksilerini anlayıp duruma uygun en iyi çözümü seçmek önemlidir.
1 yorum
Hacker News görüşü
Hacker News yorumları derleme özeti
HyperLogLog benzeri algoritma
HyperLogLog benzeri bir algoritma olarak, yazı tura atışlarındaki ardışıklığı kullanarak basit bir algoritma açıklanıyor. Özellikle streaming veride verimli çalışıyor ve az bellek kullanıyor.
Algoritma açıklamasındaki hata işaret ediliyor
Algoritma açıklamasının hatalı olduğu belirtiliyor ve doğru yöntem kod örneğiyle gösteriliyor. Önce kelimeleri depolayıp sonra silme yöntemi daha doğru sonuç veriyor.
Makale önerisi
Makalenin blog yazısı kadar kolay okunabildiği ve daha fazla bilgi sunduğu belirtiliyor. Streaming veride kümenin kardinalitesini tahmin eden basit bir algoritmayı açıklıyor.
Python uygulama örneği
Streaming algoritmanın Python uygulama örneği veriliyor. Basit kodla algoritmayı anlamak ve pratik yapmak mümkün.
Sistem refactoring'i için faydalı
Ziyaret sayılarını tabloya ekleyerek sayan bir sistemi refactor ederken, bunun HyperLogLog yaklaşımının yerine geçebilecek ilginç bir yöntem olduğu belirtiliyor.
Bellek açısından verimli yöntem
Bilgisayar bilimcilerinin, alt kümenin boyutunu bellek açısından verimli bir şekilde tahmin etme yöntemi icat ettiği belirtiliyor.
Chernoff Bound üzerine tartışma
Makalede kullanılan Chernoff Bound varyantı tartışılıyor. Bunun ispatın doğruluğunu bozup bozmadığından emin olunmadığı belirtiliyor.
Benzersiz öğe tahmini ile saymanın farkı
Benzersiz öğe sayısını tahmin etmekle gerçekten saymanın çok farklı olduğu belirtiliyor ve başlığın uygun olmadığına dikkat çekiliyor.
Verimli stream algoritması tanıtımı
Stream içinde en üstteki k öğeyi bulmak için verimli ve kolay uygulanabilir bir algoritma tanıtılıyor. Karp, Shenker & Papadimitriou'nun makalesi öneriliyor.
Yaratıcı düşünmenin önemi
"Kalıpların dışında düşünme" örneklerinden hoşlanıldığı belirtiliyor ve problem çözmek için doğru soruyu bulmanın önemli olduğu vurgulanıyor. Çeşitli örnekler aracılığıyla yaratıcı düşünmenin içselleştirilip uygulanabilmesi umuluyor.