c - C中的巨大位数组/位图声明

我试着写一个bloom过滤器，存储大约80000个字符串…现在我猜每个字符串可以有2个单词长要存储80000个字符串..我需要80000*2=16kBytes？
如果必须存储16kB=16*1000*8=128000位，则至少需要2^17=131072的位图。这就是我现在所拥有的
int主（）{

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

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

最佳答案

你的数学不好。80k*2=160K，正如克里斯·多德所说，在普通的台式机甚至智能手机上，这些都是很小的。如果您的应用程序是嵌入式的，或者您有其他大型分配，那么它可能是另一回事。默认情况下，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);
}