3

順序付けされていない Int32 値のストリームを受信して​​おり、受信した個別の値の数を追跡する必要があります。

私の考えは、Int32 の値を に追加することHashSet<Int32>です。HashSet の動作により、重複するエントリが追加されることはありません。

セット メンバーシップが GetHashCode() に基づいていること、および Int32 のハッシュ コードが数値そのものであることを正しく理解していますか?

CPU 効率またはメモリ効率を高める方法はありますか?

アップデート

データ ストリームはかなり大きいです。Linq を使用してストリームを反復処理し、個別のカウントを取得するだけでは、ストリームを 2 回反復処理する必要があるため、私が求めているものではありません。

4

5 に答える 5

4

何らかの種類があると仮定するとIEnumerable<int>、次のことができます。

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

セット メンバーシップが GetHashCode() に基づいていることを正しく理解していますか?

そうではありません。a のメンバーシップは、と の等価性チェックHashSetの組み合わせに基づいています。GetHashCode一般に、2 つのオブジェクトが同じハッシュコードを持つことはできますが、等しくはなりません。しかし、intそれは起こり得ません。

そして、Int32 のハッシュ コードは数値そのものですか?

はい、そうです。

CPU 効率またはメモリ効率を高める方法はありますか?

int が狭い範囲にあることがわかっている場合は、ビットマップを使用して見たものを効率的に保存できます。たとえば、範囲が 1,000,000 の場合、見た int を 1,000,000 ビットで格納できます。インデックス n で 1 に設定されたビットは、整数 n を見たことを意味します。これを実装する 1 つの方法を示すサンプル コードを次に示します。

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

あなたのドメインはよくわかりませんが、非常に小さなメモリと処理を使用して大きなセットのカーディナリティを計算するアルゴリズムがいくつかあります。

私のプロジェクトで 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 に答える
1

非常に大きなデータ ストリーム (数百万から数十億) がある場合は、ブルーム フィルターを使用することをお勧めします。これにより、データをストリーミングするときにおおよその数を決定できるようになります。正確な数が必要な場合は、オフラインで処理できます。

妥当な C# 実装はこちら: http://bloomfilter.codeplex.com/

于 2012-06-29T03:11:41.517 に答える
0

一度に 1 つの int から一連の 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;
       }
   }
}

ただし、Hansleman 氏が提案することを実行し、それを測定します

ストリームが新しい一意の値の取得を停止するのに十分な大きさである場合、 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 に答える