3

我正在接收一个无序的 Int32 值流，并且需要跟踪我收到的不同值的计数。

我的想法是将 Int32 值添加到HashSet<Int32>. 根据 HashSet 的行为，根本不会添加重复条目。

我是否正确理解集合成员资格基于 GetHashCode() 并且 Int32 的哈希码是数字本身？

有没有一种方法可以提高 CPU 或内存效率？

更新

数据流相当大。简单地使用 Linq 迭代流以获得不同的计数不是我想要的，因为这将涉及第二次迭代流。

4

5 回答 5

4

假设你有某种IEnumerable<int>你可以做以下事情：

int count = stream.Distinct().Count();

我是否正确理解集合成员资格基于 GetHashCode()

不完全的。a 中的成员资格HashSet基于GetHashCode和 等式检查的组合。通常，两个对象可以具有相同的哈希码但不相等。虽然int那不可能发生。

并且 Int32 的哈希码是数字本身？

对，那是正确的。

有没有一种方法可以提高 CPU 或内存效率？

如果您知道您的整数将在一个小范围内，您可以使用位图有效地存储您所看到的。例如，如果您有 1,000,000 的范围，您可以将您看到的整数存储在 1,000,000 位中。在索引 n 处设置为 1 表示您已经看到整数 n。下面是一些示例代码，展示了一种实现方式：

void Main()
{
    int max = 1000000;

    IEnumerable<int> stream = GetStream(max);

    int count = DistinctCount(stream, max);
    int count2 = stream.Distinct().Count();
    Debug.Assert(count == count2);
}

int DistinctCount(IEnumerable<int> stream, int max)
{
    int[] seen = new int[max / 32];
    foreach (int x in stream)
    {
        seen[x / 32] |= 1 << (x % 32);
    }

    int count = 0;
    foreach (uint s in seen)
    {
        uint t = s;
        while (t > 0)
        {
            if (t % 2 == 1) { count++; }
            t /= 2;
        }
    }
    return count;
}

IEnumerable<int> GetStream(int max)
{
    List<int> stream = new List<int>();
    Random random = new Random();
    for (int i = 0; i < 2000000; ++i)
    {
        stream.Add(random.Next(max));
    }
    return stream;
}
于 2012-06-27T22:09:34.660 回答
1

一个想法是，如果您有非常大的数据流（数百万到数十亿），则可以使用Bloom 过滤器。这将使您能够在流式传输数据时确定近似计数，如果您需要精确计数，您可以离线处理它。

一个合理的 C# 实现在这里：http ://bloomfilter.codeplex.com/

于 2012-06-29T03:11:41.517 回答
1

不太了解您的领域，但是有一些算法可以使用非常小的内存和处理来计算大集合的基数。

我在我的一个项目中使用 HyperLogLog。我用它来计算数百万个不同的项目，使用低至 8KB 的内存，误差为 1%。

这是一篇描述它的论文：

http://algo.inria.fr/flajolet/Publications/FlFuGaMe07.pdf

我已经用 Java 和 Python 实现了它。Python版本是开源的，算法相当小。看看这个：

https://github.com/juanplopes/hyperloglog.py/blob/master/hyperloglog.py

于 2012-07-27T18:20:23.197 回答
0

我假设您以块的形式接收值，一次一个整数到一堆整数。

鉴于此，最简单的可能是最好的，我也会使用哈希。但是我看不到如何使用 HashSet。如果你想要不同值的计数，你只会得到找到的值

Dictionary<int,int> _countHash = new Dictionary<int,int>();
void moreIntsArrived(IEnumerable<int> bunch)
{
   foreach(var value in bunch)
   {
       if (_countHash.ContainsKey(value))
       {
             _countHash[value] += _countHash[value];
       }
       else
       {
             _countHash[value] = 0;
       }
   }
}

然而，按照汉斯尔曼先生的建议，测量它

如果您的流足够大以停止获取新的唯一值，则在执行 ContainsKey 检查和在未找到密钥时仅处理异常之间可能存在权衡

void moreIntsArrived(IEnumerable<int> bunch)
{
   foreach(var value in bunch)
   {
       try
       {
            int c = _countHash[value];
             _countHash[value] = c + 1;
       }
       catch(KeyNotFoundException)
       {
             _countHash[value] = 0;
       }
   }
}

然后还有 Dictionary::TryGetValue() 方法，但这取决于它内部的作用:-)使用源

于 2012-06-27T22:27:35.517 回答
0

我很欣赏其他答案，但发现使用 a 的原始方法HashSet<T>最适合我的情况。

重新迭代流以获得不同的计数效率不高。

于 2012-06-29T03:00:25.873 回答