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 に答える