2

我正在构建一个知识库站点，对于知识库中的每个页面，我希望能够显示以下统计信息：Y 不同的人查看了 X 次

计算视图数量很简单

为了计算总浏览量，我可以在每次加载页面时简单地增加一个页面浏览计数器（用户已登录，因此没有垃圾邮件问题等）。

唯一页面视图的简单方法 - 存储所有查看者 ID

为了决定是否将新访问计为新的唯一访问者或以前的访问者之一只是再次返回，我需要记录谁已经看过该页面。

这意味着为每个页面保留以前的访问者 ID 的存储。每次访客到达时，我都会检查他们的 ID 是否存在于商店中。如果有，我什么也不做，如果没有，我会追加它。同时，我记录了唯一 ID 的总数。

存储和查找所有 ID 以计算单个总数感觉很麻烦

这在编程上非常简单，但感觉很难看。存储许多 ID，然后查找每个新 ID 以计算单个整数的想法感觉就像比我更聪明的头脑找到了一个紧凑的解决方案。

这是标准问题模式吗？

确定新观察是独特的还是预先存在的最有效的方法是什么？

我对这是否是一些涉及散列或类似的紧凑解决方案的标准问题感兴趣？

注意我的兴趣是是否有一些智能数学或算法可以做到这一点。我可以解决它我只是怀疑有一个更聪明的方法......

4

2 回答 2

3

只是在这里大声思考，但让我们看看这在算法上是否有意义：

对于每一页，存储三个字段：

  • 一个视图计数器，就像您已经拥有的一样

  • 一个“唯一查看器”计数器

  • 一个“bloom filter”（基本上是一个很大的字段，但谷歌搜索了实现细节）

当用户点击页面时，为该用户生成哈希。如果该散列已经在布隆过滤器中，只需碰撞视图计数器

如果它不在布隆过滤器中，则碰撞两个计数器并将该哈希添加到过滤器中。但是，根据您的哈希值，布隆过滤器成员资格检查中可能会出现误报（但绝不会出现误报），因此请注意如何选择哈希算法。

三个领域。还不错。:)

参考：维基百科上的布隆过滤器

编辑：我已经让这段代码漂浮了一段时间 - 不确定核心最初来自哪里，但多年来我已经对其进行了调整 - 为 LINQPad 做好了准备：

void Main()
{
    var estimatedCount = 100000;
    var falsePositiveProbability = 0.001;
    var falsePositiveCount = 0;
    var memberCount = 0;
    var bloom = BloomFilter<char>.Create(
        estimatedCount, 
        falsePositiveProbability,
        c => c.GetHashCode(),
        c => (int)c);
    var allChars = Enumerable.Range(0, 0xffff).Select(i => (char)i).ToList();
    foreach(var c in allChars)
    {
        var alreadyIn = bloom.Test(c);
        if(alreadyIn)
        {
            falsePositiveCount++;
        }
        bloom.Add(c);
        memberCount++;
    }
    Console.WriteLine("Predicted count: {0} Predicted false positive: {1:p} ", estimatedCount, falsePositiveProbability);
    Console.WriteLine("Actual false positive count: {0} Actual member count: {1} ", falsePositiveCount, memberCount);
    Console.WriteLine("False positive rate: {0:p}", ((double)falsePositiveCount / memberCount));
}

// Define other methods and classes here
public class BloomFilter<TValue>
{
    private BitArray hashbits;
    private int numKeys;

    private Func<TValue,int> _hashFunc1;
    private Func<TValue,int> _hashFunc2;

    public static BloomFilter<TValue> Create(int estimateCount, double falsePositiveRate, Func<TValue,int> hash1, Func<TValue,int> hash2)
    {
        // formulae courtesy of http://hur.st/bloomfilter
        var tableSize = Math.Ceiling((estimateCount * Math.Log(falsePositiveRate)) / Math.Log(1.0 / (Math.Pow(2.0, Math.Log(2.0)))));
        var keyCount = Math.Round(Math.Log(2.0) * tableSize / estimateCount);
        return new BloomFilter<TValue>((int)tableSize, (int)keyCount)
        {
            _hashFunc1 = hash1,
            _hashFunc2 = hash2
        };
    }

    private BloomFilter(int tableSize, int nKeys)
    {
        numKeys = nKeys;
        hashbits = new BitArray(tableSize);
    }

    public bool Test(TValue val)
    {
        var hashKeys = GenerateHashes(val);
        foreach (int hash in hashKeys)
        {
            if (!hashbits[hash])
                return false;
        }
        return true;
    }

    public bool Add(TValue val)
    {
        bool rslt = true;
        var hashKeys = GenerateHashes(val);
        foreach (int hash in hashKeys)
        {
            if (!hashbits[hash])
            {
                rslt = false;
                hashbits[hash] = true;
            }
        }
        return rslt;
    }

    private int[] GenerateHashes(TValue val)
    {
        int hash1 = _hashFunc1(val);
        int hash2 = _hashFunc2(val);

        var hashKeys = new int[numKeys];

        hashKeys[0] = Math.Abs(hash1 % hashbits.Count);
        if (numKeys > 1)
        {
            for (int i = 1; i < numKeys; i++)
            {
                hashKeys[i] = Math.Abs((hash1 + (i * hash2)) %
                    hashbits.Count);
            }
        }
        return hashKeys;
    }
}
于 2013-01-06T17:32:20.027 回答
0

在这种情况下，关系数据库可能不是解决这个问题的最有效或最具可扩展性的方法。我建议查看键值存储，例如 Redis - http://redis.io，其中键可以是页面标识符，值可以是由哈希表支持的集合 - 请参见http:// redis.io/commands#set

于 2013-01-06T16:53:04.940 回答