알고리즘 방식으로 키 공간을 분할하는 방법은 무엇입니까?

Question

이것은 일관된 해싱과 관련이 있으며 내가해야 할 일을 개념적으로 이해하는 동안이 문제를 코드로 변환하는 데 어려움이 있습니다.

주어진 키 공간 (예 : 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); 

    // ... 

} 

편집 :

내가 이런 말을하는 또 다른 방법은 가정 : 문제가 2^128 물론

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

가 매우 많은 수이며 수 없습니다 수학을 수행하는 C의 단일 정수 변수에 포함될 수 있습니다 (따라서 char [16] 구조체).

정말 많은 수의 라이브러리 (또는 라이브러리)를 사용하고 싶지 않습니다.

편집 :

실제로 내가 찾고 숫자는, 비록 :

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

Answer 1

: n 개의 요소와 일부 공간 A의 일부 같은 크기 K 파티션을 추구 할 때

---

당신이 표현할 수있는 키가 있다면 ... 그러나

,이 같은 문제를 접근하는 것

특정 파티션의 가장 높은 키는 분명히 모든 1 비트로 구성됩니다.키가 낮은 n 비트이고 파티션 ID가 m 비트 인 경우 m 비트 카운터를 실행하고 n 비트 카운터를 연결하기 만하면됩니다. .

00 111111 
01 111111 
10 111111 
11 111111 

물 :
는 8 비트 격벽 (그래서 num_partitions = 2^2 = 4 대한 상위 2 비트 KEYSPACE, 6 하부가 키에 대한 각 파티션의 가장 핵심이 네 것을 가정 설명하기 를 생성하기 위해, 당신이 할 필요는 다음과 같습니다. 물론

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

,이 num_partitions 두 가지의 힘 가정

물론, 키 - 공간을 큰 당신로는하지 않습니다 심플하다. 모든 변수를 하나의 변수에 넣을 수는 없으므로 위의 것과 같습니다. 여전히 원칙은 동일합니다. num_partitions이 충분히 작 으면 카운터를 일반 int 변수에 맞춰서 상위 비트에 복사 한 다음 나머지 비트를 1로 채울 수 있습니다.

Answer 2

나는 당신의 질문의 맥락을 이해 확실하지 않다 - 나는 일관 공부 적이 없다를 해싱.

---

문제는 거의 금액, "어떻게 정렬 할 수 있습니다 일종의없이".

또 다른 방법은이 작업을 수행 할 수 있습니다 :

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

이 선형 시간입니다. 그러나 다음 순서에 따라 순서가 있다는 점을 제외하고는 키 공간에 대한 사전 지식이 필요하지 않습니다.

[0, 2^128] -> {값}을 파티셔닝하는 경우 (예 : 일부 분산 컴퓨팅을 수행하거나 자만하게하는 경우) 정수가 체계적으로 구성되어 있으므로 훨씬 더 운이 좋습니다.

4 개의 32 비트 정수를 구조체에 넣고 자신이 해결해야하는 문제를 해결하는 bigint 루틴을 작성한다는 약간 바보 같은 생각을 제안합니다.

이 아닌 경우 C++를 사용하는 경우 Common Lisp에 bigint가 내장되어 있습니다. 편리한 것으로 나타났습니다.

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. 
} 

Answer 3

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; 
}