4

ここに問題があります: count = M というランダムな整数があり、それらを N 個のバケットに均等に (またはほぼ均等に) 分割する必要があります。

M と N に範囲を割り当てると、N は約 10000 になり、M は 1 億から 500 万になります。

これまでのところ、これは小さなハッシュの問題のように見えます。しかし、ここでそれをさらに複雑にしています。したがって、これらの数は数えると M ですが、段階的に検討する必要があるため、最初は X がないとします。整数の場合、それらを均等に分配してから、Y no. の整数がより多く利用できるので、それらを再度配布してから、Z no. の整数が利用可能です (X+Y+Z = M)。

また、特定の番号。バケット番号が次のようになるような方法で配布する必要があります。効率よく検索できます。

これまでのところ、いくつかのアプローチを考えましたが、どれも均等に分散することさえできませんでした。

1) バケット番号を持っています。高いので、N の最大値は 500 万です。均等配分とは 500 個のバケットを意味するため、500 個のバケットを作成することから始めます。それらは最終的に均等にいっぱいになります。しかし、これにも扱いにくい最終的なケースがあります。2）現在利用可能なサイズ（X、後でX + Y、次にM）に応じたバケットサイズを持ち、完全に再ハッシュしてnoを増やす場合。バケツの。これは、私のユースケースではコストのかかる作業になる可能性があり、避けたいと思います。3) どうにかビンパッキング問題に当てはめようとしている。しかし、整数が入るビンが何であるかはすぐにはわかりません。心に留めておくべき明らかなことの 1 つは、これらはランダムな番号であるため、カウントが 100,000 の場合、番号の 1 つです。50万でもいい。

どのようなアプローチをお勧めしますか? 必要に応じて、後でユースケースを提供できます。

4

2 に答える 2

11

あなたはこれを複雑にしすぎています。整数はランダムなので、考える必要はありません。整数がランダムでない場合は、ハッシュ アルゴリズムを考え出す必要があるかもしれません。

整数の範囲がバケットの数よりもかなり大きい限り、バケットの数のモジュロによって整数をバケットに割り当てます。

このような：

void assignToBucket( int r )
{
    bucket[ r % NUM_BUCKETS ].add( r );
}

挿入しようとする数は重要ではありません。一度に挿入する場合も、数回に分けて挿入する場合も問題ありません。ストリームがランダムである限り、モジュロはそれらがバケットにほぼ均等に分散されることを保証します。

各 r の範囲がバケットの数に近い場合、これは機能しません。つまり、各 r が 0 ～ 7 であり、6 つのバケットがある場合、均等に分散されません。また、ランダムでないストリームでは機能しません。

ランダムでない分布のストリームの場合、適切なハッシュ関数を作成するには、分布についてある程度知っておく必要があります。

于 2012-07-11T01:15:24.013 に答える