Ben öğrenme hakkında farklı algoritmalar boş vaktimde son zamanlarda ve ben rastladım ki öyle görünüyor çok ilginç denir HyperLogLog algoritma - tahminleri kaç benzersiz öğeleri bir liste.

Bu özellikle ilginç olduğu için benim MySQL geri getirdi çünkü beni görünce gün "Önem" değeri tahmin ettim hesaplanmamış olduğunu her zaman yakın zamana kadar kabul.

Kaç benzersiz öğeleri bir dizi vardır hesaplayabilecek O(n) bir algoritma yazmayı biliyorum. Javascript ile bunu yazdım

function countUniqueAlgo1(arr) {
    var Table = {};
    var numUnique = 0;
    var numDataPoints = arr.length;
    for (var j = 0; j < numDataPoints; j  ) {
        var val = arr[j];
        if (Table[val] != null) {
            continue;
        }
        Table[val] = 1;
        numUnique  ;
    }
    return numUnique;
}

Ama sorun(n) ise benim algoritması, Bellek (Table değerleri depolama) çok kullanır.

O liste(n) çiftleri sefer sayısı hakkında bu kağıt okuma ve en az bellek kullanarak oldum. http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

Ve bit falan karma sayarak belirli bir olasılık (liste eşit olarak dağıtılır varsayarak) içindeki bir listede benzersiz öğe sayısını tahmin edebilirsiniz açıklar.

Gazeteyi okudum, ama bunu anlamak için görünmüyor olabilir. Birinin adını duymadım daha bir açıklaması olan var mı? Karma ne olduğunu biliyorum, ama bu HyperLogLog algoritma nasıl kullanılacağını anlamıyorum.

HyperLogLog algoritma oldukça yoğun altyapımızı kullanıyoruz. Sonuç olarak geliştiriciler için yöneticilerinden herkese anlatmaya çalışıyoruz end. Hayatımızı biraz daha kolaylaştırmak için, blog post koymak zorundayız ve bunu göstermek için bir simülasyon D3 yazılı dahil. Yardımcı olur umarım!