.NET中不同Int32值的计数

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

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

我是否正确理解设置成员资格基于GetHashCode（），并且Int32的哈希码是数字本身？

有没有一种方法是更多的CPU或更高的内存效率？

UPDATE

该数据流是相当大的。简单地使用Linq迭代流来获得不同的计数并不是我所追求的，因为这将涉及到第二次迭代流。

2012-06-27 Eric J.

一个Int32的hashCode与诠释 - 是的，绝对！见这里http://stackoverflow.com/questions/3893782/how-is-gethashcode-implemented-for-int32附加问题;你是否一次收到所有的价值，或者随着时间爆发？ – dash

集合成员资格（对于HashSet）基于一般的哈希码*和*相等。对于Int32来说，这是同样的事情，但对于大多数类型而言，它不是。 –

int的哈希码实际上就是这个值本身，但它是无关紧要的，因为无论如何都会比较这些值。 –

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

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

来源

2012-06-29 03:00:25

假设你有某种IEnumerable<int>，你可以做到以下几点：

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

难道我理解正确的是集合成员基于GetHashCode（）方法

不太。 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-27 22:09:34

枚举（非常大）流只是为了获得不同的计数效率似乎相当低效，因为我已经列举了其他处理。这就是为什么我的问题集中在如何有效地实现自己独特的计数。 –

@EricJ我必须同意;你原来的'HashSet <>'也是合理的。 –

我假设你在块收到的价值观，无论是一个INT同时一堆整数的。

鉴于最简单的事情可能是最好的，我也会使用哈希。但是我不明白你如何使用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; 
     } 
    } 
}

但是，做什么Mr Hansleman suggests, measure it

有可能是掉在做的containsKey检查，只是采取的打击之间的贸易当钥匙未发现异常，IF您的流足够大，以停止获取新的独特的价值观

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

话又说回来有字典:: TryGetValue（）方法，但是这取决于什么牛逼帽子里面:-) 使用确实源

来源

2012-06-27 22:27:35

当且仅当它不是该组的成员时，HashSet才会添加一个新项目。它就像一本字典，但没有不必要的值。 –

但是如果你想要点数？那存储在哪里？ myhash.Add（8），myHash.Add（8），我如何发现有8个2个实例？我在文档中看不到（或者我误解了这个问题=“我收到一串无序的Int32值，需要跟踪我收到的不同值的计数。”） –

我不需要知道许多2，6和42，只是不同整数的总数。如果数据令是6 6 2 6 42 2 42，答案将是“3”。 –

一想，如果你有一个非常大数据流（百万到十亿）是使用Bloom filter。这将为您提供在流式处理数据时确定大致计数的功能，并且如果您需要确切计数，则可以离线处理。

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

来源

2012-06-29 03:11:41 codekaizen

好的建议，但我需要第一次精确计数（+1虽然...） –

你仍然可以得到一个确切的计数，但它做得更慢（任何时候后的近似计数）。使用哈希集合来包含整数有一个物理限制 - 大约有五千万（或更少）哈希集合变得太大而内存成为问题。在这一点上，你必须采用其他策略来精确计数，并且它们都比较慢或者受到类似的内存限制。我会质疑马上需要一个确切的数字......通常一个近似值是有价值的，即使它是一个决策编号，确切的数字可以追溯到几秒或几分钟。 – codekaizen

真的不知道你的域名，但也有一些算法来计算的大型成套基数使用非常小的内存和处理。

我在我的项目中使用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-27 18:20:23

.NET中不同Int32值的计数

回答

相关问题