高效的方式

Question

這是我當前的問題，我有一些布隆過濾器，我想構建成一個矩陣，說：

[0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 1, 0, 1] 
[1, 1, 1, 0, 0, 0, 1, 0, 0, 0, 1, 0, 0] 
... 
[1, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 0, 0] 

每列將派生從BitSet中，除了循環所有行和比較每個索引之外，是否有更高效的方式來查找所有具有位設置爲1的列？

是否有任何數據結構可以幫助我呢？

Answer 1

假設你正在尋找這列包含那些現在每列有多少那些包含，通過他們的循環似乎是最好的主意。

如果你用一些短路邏輯實現你的循環，那麼你會得到更好的平均運行時間。

喜歡的東西：

for (int column = 0; column < width; column++) { 
    for (int row = 0; row < height; row++) { 
     if (array[column][row] == 1) { 
      list.append(column); 
      break; // move on to the next column because we don't care what's 
        // left in this column as we already found our '1' 

有了這個代碼，你會得到一個最壞情況（如果每個bit是0）上運行的n時間（n是的bits總數），這是非常好。

但是，除非你非常不走運，否則由於邏輯上的短路會得到更好的運行時間。

上面的作品爲位數組，但是，BitSets有他們自己的一些有用的功能。

甲BitSet所包含的功能：其length()與一組返回指數最高位+ 1（或0如果沒有設置位）和nextSetBit(index)返回下一組比特的從index -> end包容的索引。

所以你的代碼很容易被這樣的：

int index = 0; 

while (index < BitSet.length()) { 
    index = BitSet.nextSetBit(index); 
    list.append(index); 
    index++; 
}