Если я вас понимаю:
- Каждый фильтр Блума будет реализован как растровое изображение размера N.
- Вы принимаете хеш-функцию, которая равномерно распределяет элементы.
Если у вас ~ 1000 элементов, вы бы измерили размер набора битов фильтра Блюма, чтобы были установлены только некоторые допустимые коэффициенты загрузки, например, в среднем 1 к 8, чтобы поддерживать низкий уровень ложных срабатываний пересечения. Тем не менее, вы всегда можете получить некоторые ложные срабатывания. Например, при пересечении набора фильтров Блума вы можете получить некоторые ложные срабатывания, когда set1 = { e1 } и set2 = { e2 }, e1 != e2, что set1 intersect set2 = { }, но bf(set1) interesect bf(set2) <> {}. Обратите внимание, что вы никогда не получите ложных негативов - если bf(set1) intersect bf(set2) = {}, то обязательно set1 intersect set2 = {}.
Я думаю, что ваш алгоритм должен формировать BF для R и W, а затем пересекать их как можно больше битов, как показано в варианте 2 ниже.
Быстрый взлом, ржавый C:
const unsigned N = 1024 * 8;
const unsigned BPW = 8 * sizeof ulong;
typedef unsigned long ulong;
typedef struct BF { ulong bits[N/BPW]; } BF;
unsigned hash(ulong e) { return foo(e) % N; }
void clear(BF* pbf) { memset(pbf->bits, 0, sizeof(pbf->bits)); }
void add(BF* pbf, ulong e) { unsigned h = hash(e); bf.bits[h/BPW] |= 1 << (h%BPW); }
bool hit(BF* pbf, ulong e) { unsigned h = hash(e); return (bf.bits[h/BPW]>>(h%BPW)) & 1; }
bool intersect(BF* pbfResult, BF* pbf1, BF* pbf2) {
bool empty = TRUE;
for (unsigned i = 0; i < N/BPW; i++)
if ((pbfResult->bits[i] = pbf1->bits[i] & pbf2->bits[i]) != 0)
empty = FALSE;
return !empty;
}
void intersectRW(unsigned nr, ulong* r, unsigned nw, ulong* w) {
BF bfR, bfW, bfIntesection;
unsigned i;
clear(&bfR);
for (i = 0; i < nr; i++)
add(&bfR, r[i]);
// variant 1: enumerate elements of W that hit in BF(R)
for (i = 0; i < nw; i++)
if (hit(&bfR, w[i]))
... w[i] ...
// variant 2: determine if intersection of BFs is empty and get intersection BF
clear(&bfW);
for (i = 0; i < nw; i++)
add(&bfW, w[i]);
bool any = intersect(&bfIntersection, &bfR, &bfW);
...
}
Ожидаемое время выполнения?
- Каждый вызов инициализирует 3 BF по 1 КБ, например. 128 ulongs, и эти маленькие растровые изображения находятся на TOS и должны легко вписываться в L1 $, и, во всяком случае, иметь большую пространственную локализацию;
- добавляет 100-1000 элементов к BFR, например. ~ 1000 встроенных вызовов add, некоторых сдвигов и хранилищ;
- проверяет попадание 100-1000 элементов BFR, например ~ 1000 встроенных вызовов попаданий, некоторых битовых сдвигов, масок, тестов;
- или вариант 2, выполняет поэлементное И только для ~ 128 пар улонгов
(Обратите внимание, что все / и% в приведенном выше коде оптимизированы для смен и масок.)
В общей сложности это может быть несколько десятков тысяч инструкций и несколько тысяч попаданий в кэш L1 или L2; с машиной времени цикла 2 ГГц я был бы удивлен, если бы разогрев занял более нескольких мс.
Что касается хеш-функций, вы не сказали нам о распределении этих 64-битных элементов. Если они уже хорошо распределены, вы можете просто сложить 64-битные версии до 16-битных с помощью пары смен, xors и маски.
* Сегодняшний любопытный факт - мелкозернистая функция «минимальной перестройки» в MS VC ++ 4.0 (http://msdn.microsoft.com/en-us/library/kfz8ad09(VS.80).aspx) зависит от большого количества фильтров блума - но мы никогда не слышали о фильтрах Блума в то время. Скорее мы Мы подумали, что мы изобрели новый набор данных со структурой данных вероятностного теста на членство ... *
Что ты думаешь?
Счастливого взлома!
Подождите, я забыл упомянуть:
- Избыток, но вы можете ускорить очистку и операцию пересечения, используя векторные SIMD-инструкции (например, SSE).
- Возможно, вы сможете воспользоваться другими свойствами данных. Например, если есть какое-то сходство между массивами R и W каждого вызова, вы можете превратить алгоритм грубой силы в инкрементальный алгоритм, хотя вам, возможно, придется использовать счетные фильтры Блума.
- В зависимости от коэффициента загрузки и повторяемости самих элементов вам может не потребоваться очищать растровые изображения на каждой итерации. Вам нужно очистить их, только когда вы, наконец, получите непустое пересечение (затем повторно запустите add () и intersect ().)
- Размер вашей проблемы здесь не нужен, но если у вас есть миллионы элементов, вы можете разделить входные списки R и W на подсписки, раздать их нескольким ядрам, создать частные копии BF для R и W, затем сложите (ИЛИ) BF (R) s и BF (W) s вместе.