3
\$\begingroup\$

I have wrote some code to store all possible configurations of a set of numbers in the sliding tile puzzle but the process of doing slow is very slow.

Say, for instance, I have a sliding tile puzzle with the goal state of {1,2,3,4,5,6,7,8,9,10,11,12,13,14,15,0} where the 0 represents the blank tile which other tiles can move into.

I have performed a breadth first search from the goal configuration to find all possible configurations for the given subset of tiles:

enter image description here

The image above displays the numbers that I am storing all permutations for, so every other tile is represented by a -1, other than the 0 because I need this to move tiles. I perform the breadth-first search from the goal state because each new iteration adds one to the number of moves, so each time it looks for possible moves (neighbours) in my code it adds 1 to it.

My question is, is there any way I can speed up this process? I have currently stored 60,000 states in 15 minutes of execution time and there are a total of \$\frac{16!}{(16-6)!} = 5765760\$ states, so this will take a very long time. Also, the time will grow as I am storing the states in a seen list.

 static Set<State> SET = new HashSet<State>() {
        private static final long serialVersionUID = 1L;

        @Override
        public boolean contains(Object obj) {
            State v = (State) obj;
            for (State mad : this) {
                if (Arrays.equals(mad.getState(), v.getState())) {

                    return true;
                }
            }
            return false;
        }

    };
    static Queue<State> QUEUE = new LinkedList<>();

    public static void main(String[] args) throws SQLException {
        // TODO code application logic here

        Connection dbConnection = null;
        PreparedStatement preparedStatement = null;
        String insertTableSQL = "INSERT INTO six_six_three.six"
                + "(STATE, VALUE) VALUES"
                + "(?,?)";
    try {
                dbConnection = getDBConnection();
                preparedStatement = dbConnection.prepareStatement(insertTableSQL);
                byte[] initialState = {1, -1, -1, -1, 5, 6, -1, -1, 9, 10, -1, -1, 13, -1, -1, 0};

                State s = new State(0, initialState);
                QUEUE.add(s);
                State current = null;
                int numInserted = 0;

                while (!QUEUE.isEmpty()) {
                    numInserted++;
                    if (numInserted % 20000 == 0) {
                        System.out.println(numInserted + " " + current.getMoves());
                    }
                    current = QUEUE.remove();
                    SET.add(current);
                    preparedStatement.setBytes(1, current.getState());
                    preparedStatement.setInt(2, current.getMoves());

                    preparedStatement.executeUpdate();
                    for (State n : findNeighbours(current)) {
                        if (!SET.contains(n)) {
                            SET.add(n);
                            if (!QUEUE.contains(n)) {
                                QUEUE.add(n);
                            }
                        }
                    }
                }
                System.out.println("Recorded inserted :D");

            } catch (SQLException e) {
                System.out.println(e);
            } finally {

                if (preparedStatement != null) {
                    preparedStatement.close();
                }

                if (dbConnection != null) {
                    dbConnection.close();
                }

            }

    public static ArrayList<State> findNeighbours(State currentState) {

        byte[] state = currentState.getState();
        ArrayList<State> neighbours = new ArrayList<>();
        for (int i = 0; i < state.length; i++) {
            if (state[i] == 0) {
                if (i % 4 != 0) {
                    byte[] left = new byte[16];
                    System.arraycopy(state, 0, left, 0, left.length);
                    byte temp = left[i];
                    left[i] = left[i - 1];
                    left[i - 1] = temp;
                    State s = new State(currentState.getMoves() + 1, left);
                    neighbours.add(s);

                }
                if (i % 4 != 3) {
                    byte[] right = new byte[16];
                    System.arraycopy(state, 0, right, 0, right.length);

                    byte temp = right[i];
                    right[i] = right[i + 1];
                    right[i + 1] = temp;
                    State s = new State(currentState.getMoves() + 1, right);
                    neighbours.add(s);

                }
                if (i > 3) {

                    byte[] up = new byte[16];
                    System.arraycopy(state, 0, up, 0, up.length);
                    byte temp = up[i];
                    up[i] = up[i - 4];
                    up[i - 4] = temp;

                    State s = new State(currentState.getMoves() + 1, up);
                    neighbours.add(s);

                }
                if (i < 12) {
                    byte[] down = new byte[16];
                    System.arraycopy(state, 0, down, 0, down.length);
                    byte temp = down[i];
                    down[i] = down[i + 4];
                    down[i + 4] = temp;
                    State s = new State(currentState.getMoves() + 1, down);
                    neighbours.add(s);

                }

            }
        }
        return neighbours;
    }

    public static class State {

        int moves;
        byte[] composition;

        public State(int moves, byte[] composition) {
            this.moves = moves;
            this.composition = composition;
        }

        public int getMoves() {
            return moves;
        }

        public void setMoves(int moves) {
            this.moves = moves;
        }

        public byte[] getState() {
            return composition;
        }
    }
\$\endgroup\$
  • 2
    \$\begingroup\$ Can I ask you why do you want to store all the possible states? \$\endgroup\$ – mayo Feb 9 '17 at 2:40
  • \$\begingroup\$ Are you sure that neighbor generation is the most time-consuming part? Perhaps you have some code that tracks duplicated states \$\endgroup\$ – default locale Feb 9 '17 at 3:53
  • \$\begingroup\$ For Pattern Databases @mayo \$\endgroup\$ – Luke Garrigan Feb 9 '17 at 20:34
  • \$\begingroup\$ I've added all the code, so you might be right @defaultlocale \$\endgroup\$ – Luke Garrigan Feb 9 '17 at 20:34
  • \$\begingroup\$ Welcome to Code Review! Please do not update the code in your question to incorporate feedback from answers, doing so goes against the Question + Answer style of Code Review. This is not a forum where you should keep the most updated version in your question. Please see what you may and may not do after receiving answers. \$\endgroup\$ – Simon Forsberg Feb 9 '17 at 20:39
4
\$\begingroup\$

Prefer interfaces to implementations

public static ArrayList<State> findNeighbours(State currentState) {

Consider

public static List<State> findNeighbours(State currentState) {

This way you can change from ArrayList to another implementation at just one place: the initialization.

Remember what you know

    for (int i = 0; i < state.length; i++) {
        if (state[i] == 0) {

Note that each state knows where the empty spot is when you create it. So why iterate to find the empty spot? Just store it. Then you can get just say

    int i = state.getEmptyIndex();

That saves looping at the cost of a little more memory.

Pick your data type

You use a byte[] to store the state. That's easy to access, but it's hard to copy and store. Consider using a long instead. Each square takes four bits to hold. Determining the neighbors is a little more complicated, but not terribly so. And best of all, you can say things like

    if (!seen.contains(next)) {
        neighbours.add(next);
    }

Where seen can be a HashSet<State>.

Third time refactor

There's a rule of thumb. If you're doing something once, just write it out for that purpose. If you do it a second time, copy and paste and then modify to fit. If you do it a third time, refactor so that you're just calling one method three times with different data. This isn't an absolute rule. Sometimes it makes sense to put the code in a method the first or second time. But it almost always makes sense by the third time.

You have the same basic code written four times.

            if (i % 4 != 0) {
                byte[] left = new byte[16];
                System.arraycopy(state, 0, left, 0, left.length);
                byte temp = left[i];
                left[i] = left[i - 1];
                left[i - 1] = temp;
                State s = new State(currentState.getMoves() + 1, left);
                neighbours.add(s);

            }

You can call a method for this.

    int column = i % WIDTH;
    if (column > 0) {
        move(-1, currentState, neighbours);
    }

And define move as

private void move(int direction, State current, List<State> neighbours) {
    State next = current.move(direction);
    if (!SET.contains(next)) {
        neighbours.add(next);
    }
}

And define that move as

public State move(int direction) {
    int index = getEmptyIndex();
    long next = swapBits(composition, index, index + direction, BIT_WIDTH);
    return new State(getMoves() + 1, next, index + direction);
}

And we can get swapBits from here:

public long swapBits(long n, int from, int to, int width) {
    from *= width;
    to *= width;
    long xor = ((n >> from) ^ (n >> to)) & ((1U << width) - 1);
    return n ^ ((xor << from) | (xor << to));
}

You don't provide enough context for testing, so I haven't tried to run this. There may need to be tweaking.

This looks more complicated but it should actually use less memory.

    if (column < WIDTH - 1) {
        move(1, currentState, neighbours);
    }
    if (i >= WIDTH) {
        move(-WIDTH, currentState, neighbours);
    }
    if (i < SIZE - WIDTH) {
        move(WIDTH, currentState, neighbours);
    }

The remaining three possible moves.

Note that I also saved i % 4 as column so as not to repeat that. I also find that easier to read.

I added constants for WIDTH, which would be 4, SIZE as 16, and BIT_WIDTH as 4. Other possible triplets include 3, 9, and 4.

Performance

The hope was that a more aggressive check of the seen tracker would help here. Other than that, this shouldn't make much difference.

    @Override
    public boolean contains(Object obj) {
        State v = (State) obj;
        for (State mad : this) {
            if (Arrays.equals(mad.getState(), v.getState())) {

                return true;
            }
        }
        return false;
    }

So every time you call SET.contains or SET.add (which calls contains), you do an Arrays.equals on each and every member of the SET. You took an \$\mathcal{O}(1)\$ operation and turned it into a \$\mathcal{O}(n)\$. Why? You could have just made this a List with the same performance. Instead of overriding HashSet.contains, consider what happens if you override State.hashCode.

                current = QUEUE.remove();
                SET.add(current);

You also call SET.add ever time you remove something from the queue. And you remove every valid state from the queue. I.e. \$\mathcal{O}(n)\$ times. So now we're up to \$\mathcal{O}(n^2)\$. You only add to the queue once without adding to the set. So just move the SET.add to where you put the initial state in the queue.

                    if (!SET.contains(n)) {
                        SET.add(n);
                        if (!QUEUE.contains(n)) {
                            QUEUE.add(n);
                        }
                    }

You can trim this down.

                    if (!SET.contains(n)) {
                        SET.add(n);
                        QUEUE.add(n);
                    }

You don't need to check if it's in the QUEUE. You only add things to the QUEUE after you put them in the SET. So this will never be true and is a linear time operation.

Also, as I said earlier, I'd prefer to do that check earlier.

Example

    public static final int WIDTH = 4;
    public static final int SIZE = 16;

    private static Set<State> SET = new HashSet<>();
    private static Queue<State> QUEUE = new LinkedList<>();

    public static void main(String[] args) {
        long initial = 0x1FFF56FF9AFFDFF0L;

        State s = new State(0, initial, 0);
        SET.add(s);
        QUEUE.add(s);

        int numInserted = 0;
        while (!QUEUE.isEmpty()) {
            numInserted++;
            if (numInserted % 1024576 == 0) {
                System.out.println(numInserted + " " + QUEUE.peek().getMoves());
            }

            findNeighbours(QUEUE.remove());
        }

        System.out.println("Recorded inserted :" + SET.size());
    }

    public static void findNeighbours(State current) {
        int i = current.getEmptyIndex();
        int column = i % WIDTH;
        if (column > 0) {
            move(-1, current);
        }
        if (column < WIDTH - 1) {
            move(1, current);
        }
        if (i >= WIDTH) {
            move(-WIDTH, current);
        }
        if (i < SIZE - WIDTH) {
            move(WIDTH, current);
        }
    }

    private static void move(int direction, State current) {
        State next = current.move(direction);
        if (!SET.contains(next)) {
            SET.add(next);
            QUEUE.add(next);
        }
    }

    public static class State {

        public static final int BIT_WIDTH = 4;

        int moves;
        Long composition;
        int emptyIndex;

        public State(int moves, long composition, int emptyIndex) {
            this.moves = moves;
            this.composition = composition;
            this.emptyIndex = emptyIndex;
        }

        public int getMoves() {
            return moves;
        }

        public void setMoves(int moves) {
            this.moves = moves;
        }

        public long getState() {
            return composition;
        }

        public int getEmptyIndex() {
            return emptyIndex;
        }

        public State move(int direction) {
            int index = getEmptyIndex();
            long next = swapBits(composition, index, index + direction, BIT_WIDTH);
            return new State(getMoves() + 1, next, index + direction);
        }

        public long swapBits(long n, int from, int to, int width) {
            from *= width;
            to *= width;
            long xor = ((n >> from) ^ (n >> to)) & ((1 << width) - 1);
            return n ^ ((xor << from) | (xor << to));
        }

        @Override
        public int hashCode() {
             return composition.hashCode();
        }

        @Override
        public boolean equals(Object o) {
            if (o == this) {
                return true;
            }

            if (!(o instanceof State)) {
                return false;
            }

            State s = (State)o;
            return composition.equals(s.getState());
        }

    }

I ripped out the database parts, since I don't have access to the database. It was still slow, so I don't think that was the problem.

Because this overrides hashCode, we can just use the regular hashSet. Long.hashCode seems to work well enough.

This version does a million records in less time than the original took to do 20 thousand. And it doesn't take longer with each added element.

I tested it with output for the simple, one and two square states. I just printed out the number found for the states with more squares.

Note that your example has seven squares and 57,657,600 states, not 5 million.

In this example, I used F (15) instead of -1 to represent unknown squares. That of course stops working if 15 is one of your squares.

\$\endgroup\$
  • \$\begingroup\$ Yeah sorry, I thought I added all the code, I will do that tonight - the rest of the code is really just the breadth-first search algorithm from the goal state \$\endgroup\$ – Luke Garrigan Feb 9 '17 at 10:21
  • \$\begingroup\$ I have added the rest of the code on top \$\endgroup\$ – Luke Garrigan Feb 9 '17 at 19:35
  • \$\begingroup\$ I'm not really getting any performance gain with the updates \$\endgroup\$ – Luke Garrigan Feb 9 '17 at 19:49
  • \$\begingroup\$ Brilliant stuff, really insightful thank you! Sorry for the delay I didn't realise you'd updated your answer! \$\endgroup\$ – Luke Garrigan Feb 13 '17 at 13:33

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.