0

これはコンシステントハッシュ法に関連しており、私は概念的に何をする必要があるかを理解していますが、これをコードに変換するのに苦労しています。

特定のキースペース（たとえば、128ビット）を同じサイズのパーティションに分割しようとしています。各パーティションの上限（最高のキー）が必要です。

基本的に、これをどのように完了しますか？

#define KEYSPACE_BYTE_SIZE  16
#define KEYSPACE_BIT_SIZE   (KEYSPACE_BYTE_SIZE * 8)

typedef struct _key
{ 
    char byte[KEYSPACE_BYTE_SIZE];
} key;

key * partition_keyspace( int num_partitions )
{
    key * partitions = malloc( sizeof(key) * num_partitions );

    // ...

}

編集：

私はこれを別の言い方で言うと思います：

for (i = 0; i < num_partitions; i++)
{
    partitions[i] = ((2 ^ KEYSPACE_BIT_SIZE) / num_partitions) * i;
}

もちろん、問題は2 ^ 128は非常に大きな数であり、数学を実行するCの単一の整数変数に含めることができないことです（したがって、char [16]構造体）。

私は本当にこれに多数のライブラリ（または任意のライブラリ）を使用したくありません。

編集：

しかし、実際には私が探している数字は次のとおりです。

for (i = 0; i < num_partitions; i++)
{
    partitions[i] = (((2 ^ KEYSPACE_BIT_SIZE) / num_partitions) * (i + 1)) - 1;
}
4

3 に答える 3

2

特定のパーティションの最上位のキーは、明らかにすべての1ビットで構成されます。nキーの下位ビットとmパーティションIDの上位ビットがある場合は、mビットカウンターを実行し、それを1と連結するだけnです。
説明のために、パーティションの上位2ビット（num_partitions = 2^2 = 4つまり、キーの下位6ビット）を持つ8ビットのキースペースを想定します。各パーティションの最上位のキーは次の4つになります。

00 111111
01 111111
10 111111
11 111111

それらを生成するためにあなたがする必要があるのは：

for (int i = 0; i < num_partitions; i++)
    highest_key = (i << 6) | 0x3f // where 6 is key_bits and 0x3f is six ones.

もちろん、これはnum_partitions2の累乗であると想定しています。

当然、自分のキースペースと同じ大きさのキースペースの場合、すべてを1つの変数に収めることができないため、上記のように単純になることはありません。それでも、原則は同じままです。num_partitionsが十分に小さい限り、カウンターを通常のint変数に適合させ、それを上位ビットにコピーして、残りを1で埋めることは簡単です。

于 2010-05-28T21:04:49.360 に答える
0

tzamanの答えに基づいて、これが私の解決策です。最大255のパーティションを許可します（ただし、これは変更できます）。2 num_partitionsの累乗は必要ありません...最後のパーティションに、残っているものをすべて使用させるだけです。

バグがあれば教えてください...:)

key * partition_keyspace( unsigned int num_partitions )
{
    assert( num_partitions > 0 );
    assert( num_partitions < 0xFF );

    key * partitions = (key *) malloc( sizeof(key) * num_partitions );

    // fill every bit
    memset( partitions, 0xFF, sizeof(key) * num_partitions );

    // calculate how many bits of the top byte needs to be filled by 1's
    unsigned char fill_bits = 0;
    while (num_partitions > (1 << fill_bits)) fill_bits++;
    fill_bits = 8 - fill_bits;

    // fill the top byte with the base number of 1's
    unsigned char fill_part = 0;
    for (unsigned int i = 0; i < fill_bits; i++) fill_part |= 1 << i;

    // last partition takes up whatever remains, so don't process it (hence the -1)
    for (unsigned char i = 0; i < num_partitions - 1; i++)
    {
        partitions[i].byte[0] = fill_part | (i << fill_bits);
    }

    return partitions;
}
于 2010-05-28T22:02:58.943 に答える
0

私はあなたの質問の文脈を理解しているかどうかわかりません-私はコンシステントハッシュを研究していません。

質問は、「ソートせずにどのようにソートできるか」にほぼ相当します。

別のアプローチはこれを行うことかもしれません：

iter = seed() #initialize to the bottom of the hash keys
for(i = 0 to partitionbound)
{
   iter = nextIter(iter);
}

これは線形時間です。ただし、nextIterが従う順序があることを除いて、キースペースの事前知識は必要ありません。

[0、2 ^ 128]-> {values}を分割している場合、たとえば、分散コンピューティングを実行している場合、または整数が適切に構造化されているため、幸運がはるかに高くなります。

構造体に4つの32ビットintを入れ、解決する必要のあるものを解決する独自のbigintルーチンを作成するという少しばかげたアイデアをお勧めします。

C ++を使用しない自由がある場合、CommonLispにはbigintsが組み込まれています。これは便利です。

表現可能なキーがある場合...

ただし、n個の要素を持ついくつかのスペースaで同じサイズのk個のパーティションを探す場合、次のような問題にアプローチします。

if( n % k)
{
   return "not equal-sized partition!"
}
//could be forking/threading, whatever.
for(int i = 0; i < n; i+=k)
{
   process(i, i+k-1);
}


process(bottom, top)
{
   sort(a[bottom], a[top]);
   return a[top]; //you'll have to figure out where to dump the results.
}
于 2010-05-28T20:28:16.153 に答える