Video: Sihirli Sayılar (1/3): Hannah Fry'in Gizemli Matematik Dünyası-Tanrı Olarak Sayılar 2024
Bir akıştaki nesneleri saymayı öğrenmek, en sık kullanılan öğeleri bulmanıza veya olağan ve olağandışı olayları sıralamanıza yardımcı olabilir. Bu algoritma, karma işlevleri ve yaklaşık eskizleri etkiler. Yinelenen nesneleri filtreledikten sonra ve veri akışında görülen farklı öğeleri saydıktan sonra bunu yapar.
Bu tekniği, bir arama motorunda en sık sorulan, bir çevrimiçi perakendecinin en çok satan öğeleriyle, bir web sitesindeki en popüler sayfalarda veya en uçucu hisse senetleriyle (bir stokun zamanlarını sayarak) çözmek için kullanırsınız. satılmış ve satın alınmıştır).
Bu sorunu çözümü uygularsınız, Count-Min Sketch, bir veri akışına. Tek bir veri geçişi gerektirir ve mümkün olduğunca az bilgi depolar. Bu algoritma, birçok gerçek dünyada (ağ trafiğini analiz etmek veya dağıtılmış veri akışlarını yönetmek gibi) uygulanır. Tarif, şekildeki gibi bir Bloom filtresi benzeyecek şekilde, her biri biraz vektörle ilişkilendirilmiş bir grup karma işlev kullanmayı gerektirir:
- Tüm bit vektörlerini tüm pozisyonlarda sıfırlara başlatır.
- Bir akıştan bir nesne alırken her bit vektörü için karma işlevini uygulayın. Elde edilen sayısal adresi, o konumdaki değeri arttırmak için kullanın.
- Karma işlevini bir nesneye uygulayın ve bir nesnenin frekansını tahmin etmeniz istendiğinde ilişkili konumdaki değeri alın. Bit vektörlerinden alınan tüm değerlerden en küçük değerini akışın frekansı olarak alırsınız.
Çoğaltma, karma işleci kullanırken her zaman mümkündür, özellikle ilişkili bit vektöründe birkaç yuvası varsa, eldeki birden fazla bit vektörüne sahip olmak, bunlardan en az birinin doğru değeri koruduğunu size garanti eder. Çarpışma nedeniyle yanlış pozitif sayımlarla karıştırılmadığından, seçim değeri en küçük olmalıdır.
