java - 为什么使用 boolean 数组需要这么长的时间？

Question

我正在做类作业。我应该创建一个简单版本的康威生命游戏。我在使用 boolean 值数组和使用 BitSet 之间做了一些实验。我最终创建了这个小测试:

每次对 BitSet 和 boolean 数组运行测试后，bitset 的平均时间约为 6ms，而 boolean 数组的平均时间约为 1300ms。所以我的问题是，究竟是什么导致了使用 boolean 值而不是使用 BitSet 时的巨大开销？我预计会有所不同，但没有这么大。

代码如下:

Life.java - 主类

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

使用 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 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;
    }
}

最后是 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 的两倍对我来说。