Как алгоритмически разделить пространство ключей? - PullRequest
Новая
       28

Как алгоритмически разделить пространство ключей?

0 голосов
/ 29 мая 2010

Это связано с последовательным хешированием, и, хотя я концептуально понимаю, что мне нужно сделать, мне трудно перевести это в код.

Я пытаюсь разделить данное пространство ключей (скажем, 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 );

    // ...

}

* * 1008 Edit: * * 1010

Полагаю, можно сказать по-другому: 

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

Конечно, проблема в том, что 2 ^ 128 имеет очень большое число и не может содержаться ни в одной целочисленной переменной в C, с которой нужно выполнять математику (отсюда структура char [16]) .

Я действительно не хочу использовать для этого библиотеку большого числа (или любую другую библиотеку).

Edit:

Хотя в действительности числа, которые я ищу, это: 

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

Ответы [ 3 ]

2 голосов
/ 29 мая 2010

Старший ключ в любом конкретном разделе, очевидно, будет состоять из всех 1 -бит. Если у вас есть младшие n биты для ваших ключей и верхние m биты для ваших идентификаторов разделов, то все, что вам нужно сделать, это запустить m -битовый счетчик и объединить его с n .
Для иллюстрации предположим, что 8-битное пространство ключей с двумя верхними битами для разделов (таким образом, num_partitions = 2^2 = 4, и нижние 6 для ключей. Старшим ключом в каждом разделе будут эти четыре: 

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_partitions является степенью двойки.

Естественно, для пространства ключей, такого же большого, как ваше, это будет не так просто, как указано выше, поскольку вы не можете уместить все в одну переменную. Тем не менее, принцип остается прежним. Пока ваш num_partitions достаточно мал, вы можете поместить счетчик в обычную переменную int, скопировать ее в верхние биты, а затем заполнить остальные единицами - тривиально.

0 голосов
/ 29 мая 2010

Исходя из ответа Цамана, вот мое решение. Это позволяет до 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;
}
0 голосов
/ 29 мая 2010

Я не уверен, что понимаю контекст вашего вопроса - я не изучал последовательное хеширование.

Вопрос почти сводится к тому, «как сортировать без сортировки».

Другой подход может быть следующим: 

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-битных целых числа в структуре и написать свою собственную подпрограмму bigint, которая решает, что вам нужно решить.

Если у вас есть свобода не использовать C ++, в Common Lisp есть встроенные bigints. Я нашел это удобным.

Если у вас есть представимые ключи ...

Тем не менее, при поиске некоторых равных по размеру k разделов в некотором пространстве a с n элементами я подхожу к такой проблеме: 

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