1

我正在尝试编写一个布隆过滤器来存储大约 80,000 个字符串......现在我猜测每个字符串可以是 2 个单词的长度。要存储 80,000 个字符串..我需要 80,000*2 = 16kBytes？

如果我必须存储 16kB = 16*1000*8 = 128,000 位，我至少需要 2^17=131,072 的位图。这就是我现在所拥有的

int main() {

char *str = "hello world";
int c = sizeof(unsigned char);
/*
 * declare the bit array
 */
unsigned char bit_arr[128000/c];
/*
 * couple of hash functions
 */   
unsigned int bkd = bkdrhash(str, strlen(str));
unsigned int rsh = rshash(str, strlen(str));
unsigned int jsh = jshash(str, strlen(str));

/* 
 * logic to set bit 
 * Access the bitmap arr element
 * And then set the required bits in that element
 */
bit_arr[bkd/c] & (1 << (bkd%c));
bit_arr[rsh/c] & (1 << (rsh%c));
bit_arr[jsh/c] & (1 << (jsh %c));

}

有没有更好/最佳的方法来做到这一点？

谢谢

4

2 回答 2

4

你的数学是关闭的。80k * 2 = 160K。正如 Chris Dodd 所说，这些在普通台式机甚至智能手机上都相当小。如果您的应用程序是嵌入式的，或者如果您有其他大量分配，那么情况可能就不同了。iPhone 默认有 1 兆字节的堆栈和 1/2 兆字节的辅助线程。

在具有 N 位宽的总线的机器上，使用 N 位宽的整数可能有一个显着的优势。所以从字长抽象出来：

#define WORD_BYTES 4
#define BYTE_BITS 8
#define WORD_BITS (BYTE_BITS * WORD_BYTES)
#define BITSET_BITS (1u << 17)
#define BITSET_WORDS (BITSET_BITS / WORD_BITS)
typedef unsigned int WORD;
typedef WORD BITSET[BITSET_WORDS];
typedef WORD *BITSET_REF;
#define bit(N) (1u << (N))

/*  Allocate a bitset on the heap and return a reference to it. */
BITSET_REF new_bitset(void)
{
  return safe_malloc(sizeof(BITSET));
}

/* Arrange for these functions to be inlined by the compiler rather 
   than using fancy macros or open coding.  It will be better in 
   the long run. */
int is_set(BITSET_REF bitset, int n)
{
  return (bitset[n / WORD_BITS] | bit(n % WORD_BITS)) != 0;
}

void set(BITSET_REF bitset, int n) 
{
  bitset[n / WORD_BITS] |= bit(n % WORD_BITS);
}

void clear(BITSET_REF bitset, int n) 
{
  bitset[n / WORD_BITS] &= ~bit(n % WORD_BITS);
}
于 2012-10-13T00:06:20.323 回答
1

除了各种明显的拼写错误之外，在堆栈上分配大型数组（作为局部变量）通常是一个坏主意。堆栈默认不会很大（通常只有大约 8MB 左右），虽然您可以重新配置以获得更大的堆栈，但通常最好在堆上分配大对象或使用静态分配。

也就是说，128K 绝对不是“巨大的”。从许多方面来看，它甚至都不是“大”的。关于它你唯一能说的就是它并不“小”

于 2012-10-12T23:46:01.007 回答