爲什麼使用布爾數組需要更長的時間？

Question

我正在爲班級作業。我應該創建一個簡單版本的康威生命遊戲。我在做一些使用布爾值數組和使用BitSet的實驗。我最終創建了這個小測試：

每次對BitSet和布爾數組運行測試後，bitset的平均值約爲6ms，而布爾數組的平均值約爲1300ms。所以我的問題是，究竟是什麼導致巨大的開銷時代與使用布爾組合使用BitSet？我期待有所不同，但不是那麼激烈。

下面是代碼：

Life.java - 使用數組

public class ArrayBoard implements Board 
{ 
    private boolean[] board; 

    public ArrayBoard(int size) 
    { 
     board = new boolean[size]; 
    } 

    @Override 
    public void set(int index, boolean value) 
    { 
     board[index] = value; 
    } 

    @Override 
    public boolean get(int index) 
    { 
     boolean output = false; 
     if (index >= 0 && index < board.length) 
      output = board[index]; 
     return output; 
    } 

    @Override 
    public int length() 
    { 
     return board.length; 
    } 
} 

使用的BitSet

public class BitBoard implements Board 
{ 
    private BitSet board; 

    public BitBoard(int size) 
    { 
     board = new BitSet(size); 
    } 

    @Override 
    public void set(int index, boolean value) 
    { 
     if (value) board.set(index); 
     else board.clear(index); 
    } 

    @Override 
    public boolean get(int index) 
    { 
     return board.get(index); 
    } 

    @Override 
    public int length() 
    { 
     return board.length(); 
    } 
} 

局實現主類

public class Life 
{ 
    private final int WIDTH = 100; 
    private final int HEIGHT = 100; 
    private Board board; 

    public static void main(String[] args) 
    { 
     new Life(); 
    } 

    public Life() 
    { 
     board = createBoard(); 

     // populate board with random data 
     Random random = new Random(); 
     for (int j = 0; j < board.length(); j++) 
     { 
      boolean b = random.nextBoolean(); 
      board.set(j, b); 
     } 
     random = null; 
     System.gc(); 


     System.out.println("Starting test..."); 
     long startTime = System.currentTimeMillis(); 

     for (int i = 0; i < 10_000; i++) 
     { 
      Board tempBoard = createBoard(); 
      for (int j = 0; j < board.length(); j++) 
      { 
       byte count = getNeighborCount(j); 
       boolean value = board.get(j); 
       boolean next = value ? count >= 2 && count <= 3 : count == 3; 
       tempBoard.set(j, next); 
      } 
      board = tempBoard; 
     } 

     long endTime = System.currentTimeMillis(); 
     System.out.format("Took %d ms", endTime - startTime); 
    } 

    public Board createBoard() 
    { 
     return new ArrayBoard(WIDTH * HEIGHT); 
     //return new BitBoard(WIDTH * HEIGHT); 
    } 

    public byte getNeighborCount(int index) 
    { 
     byte count = 0; 

     if (getRelative(index, -1, -1)) count++; 
     if (getRelative(index, -1, 0)) count++; 
     if (getRelative(index, -1, 1)) count++; 

     if (getRelative(index, 0, -1)) count++; 
     if (getRelative(index, 0, 0)) count++; 
     if (getRelative(index, 0, 1)) count++; 

     if (getRelative(index, 1, -1)) count++; 
     if (getRelative(index, 1, 0)) count++; 
     if (getRelative(index, 1, 1)) count++; 

     return count; 
    } 

    public boolean getRelative(int index, int x, int y) 
    { 
     int relativeIndex = index + (WIDTH * y) + x; 
     return board.get(relativeIndex); 
    } 
} 

執行董事會最後，Board.java

public interface Board 
{ 
    public boolean get(int index); 

    public void set(int index, boolean value); 

    public int length(); 
} 

Answer 1

您的問題無關請使用BitSet與boolean[]表現。

在你BitSetBoard，你有length()定義爲：

class BitSetBoard { 

    ... 

    @Override 
    public int length() 
    { 
     return board.length(); 
    } 

} 

你的意思是返回board.size()沒有board.length()。 BitSet.length()方法返回設置的最高位的索引，它不是而是返回總大小。因此，您的主循環實際上並沒有做任何事情，因爲length()在電路板清零時返回0。

通過此更改（並將邊界檢查添加到BitSetBoard.get()），BitSetBoard的運行時間恰好爲ArrayBoard的兩倍。

Answer 2

位集合是更多的內存比布爾[]，只是非常小的尺寸進一步澄清高效您可以閱讀

boolean[] vs. BitSet: Which is more efficient?

BitSet uses about 1 bit per boolean value, and boolean[] uses about 1 byte per boolean value. that also the case that BitSet are more efficient