巨大的bitarray /位圖聲明在C

我想寫一個bloom filter來存儲約80,000個字符串...現在我猜測每個字符串可以是2個字符的長度。要存儲80,000個字符串..我需要80,000 * 2 = 16kBytes？巨大的bitarray /位圖聲明在C

如果我必須存儲16kB = 16 * 1000 * 8 = 128,000bits，那麼至少需要2^17 = 131,072的位圖。這就是我現在所擁有的

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

}

有沒有做這更好的/最佳方式？

感謝

來自各種顯而易見錯別字

來源

2012-10-12 user999755

只是說你應該說它是c的語言。 –

謝謝..我編輯了標題和標籤 – user999755

'sizeof（unsigned char）== 1'總是 - 你可能需要'0123_'的'CHAR_BIT'而不是 –

你的數學是關閉的。 80k * 2 = 160K。儘管克里斯多德表示，這些在平均臺式機甚至智能手機上都很小。如果您的應用程序已嵌入或者您擁有其他大量分配，那麼這可能是另一回事。 iPhone默認有1兆字節的堆棧，輔助線程有1兆字節。

在總線寬度爲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-13 00:06:20 Gene

更好的使用' #define WORD_BITS（sizeof（WORD）* CHAR_BIT）' –

如果您改變WORD的寬度，sizeof的優點是可以節省一些輸入字符。另一方面，至少在某些編譯器中，您不能在預處理器指令中使用sizeof。 – Gene

謝謝克里斯和基因！ – user999755

除了，在堆棧上分配大的陣列（如局部變量）通常是一個好主意。堆棧默認不是很大（通常只有大約8MB左右），雖然你可以重新配置一些東西來獲得一個更大的堆棧，但是通常在堆上分配大對象或使用靜態分配會更好。

也就是說，128K絕對不是'巨大的'。通過許多措施，它甚至不是「大」。關於你唯一可以說的是它不是'小'

來源

2012-10-12 23:46:01

巨大的bitarray /位圖聲明在C

回答

相關問題