Optimize For loop for speed python

Question

Like pointed out, let me explain a bit of the code. I have 2 for loops because i have a board of a game called Tablut. I have to check from the pawn position (row_index and column_index) if there is an obstacle on the left and on the right. So, the first loop take the row_index of the pawn, then check for every row on the right side and stop when it finds an obstacle. Then do the same for the left side. If i use a single loop i don't have a way to stop searching in one direction if found an obstacle and start looking in the other, because the break will stop the entire for. The loop are used to generate all the possible actions that a move can do inside the board in that turn. Action(Position(....)) is one action that the pawn can make.

So, basically, i check in the right and left direction, if the next tile is empty i can move there, so i create a new action and add it to a list of all the possible moves, if there is an obstacle, since i can't jump it, i stop the loop.

i have this for loop and i would like to optimize it for speed.

for row in range(row_index - 1, -1, -1):
    if bitboard_util.get_bit(obstacle_bitboard, row, column_index) != 1:
        action = Action(Position(row_index, column_index), Position(row, column_index), color)
        all_available_moves_for_pawn.append(action)
    else:
        break
for row in range(row_index + 1, 9):
    if bitboard_util.get_bit(obstacle_bitboard, row, column_index) != 1:
        action = Action(Position(row_index, column_index), Position(row, column_index), color)
        all_available_moves_for_pawn.append(action)
    else:
        break

Comprehensions have practically the same performance as loops; only very few ByteCode instructions are saved which are negligible for such complex payloads. Are you sure the comprehension is faster? Is there a reason why the "loop code" has *two* for loops, but the "comprehension code" has only one? — MisterMiyagi, May 12 '20 at 09:19
You could have a look at this? https://stackoverflow.com/questions/9572833/break-list-comprehension Edit: You could have a look at multiprocessing to solve your time issues if the loops are long but without further insight in what the loops are meant to be doing its hard for me to recommend anything. — Jason Chia, May 12 '20 at 09:19
I have updated the question and explain a bit of the code. PS: Now that i have explained the code i see that the list code is wrong :P — Fanto, May 12 '20 at 09:33
There isn't much (if anything) that can be done about the ``for`` loop itself. The various functions likely can be optimised, but it is impossible to tell. At a glance, constructing the ``Action`` is likely costly as three instances are created (I'm assuming all instances being equal is a bug and should not be optimized). Actions on the board also seem unnecessarily complex, I'd just expect ``if game_board[row, column_index]:`` instead of lookup, call and comparison. Ideally though, profile your code – we can't do that for you. — MisterMiyagi, May 12 '20 at 09:54

Alain T. · Accepted Answer · 2020-05-12T11:43:47.953

You could optimize this a little by preparing a structure based on your obstacle bits that will give the range of available "moves" for each position. You can prepare that structure once and reuse it multiple times to obtain the move lists directly for all column_index/row_index afterward.

from itertools import accumulate
rowCount = 9
colCount = 9
obstacleRanges = []
for col in range(colCount):
    obstacles     = [-1] + [ row*(bitboard_util.get_bit(obstacle_bitboard, row, col) == 1) for row in range(rowCount) ] + [rowCount]
    prevObstacle  = [*accumulate(obstacles,max)]
    nextObstacle  = [*accumulate(obstacles[::-1],lambda p,o:[p,o][o>0])][::-1]
    obstacleRanges.append([*zip(prevObstacle[1:-1],nextObstacle[1:-1])])

obstacleRanges will contain tuples with the position (row) of the previous and next obstacles for every position on the board. This is computed once for the whole board and allows you to find the range of moves directly without additional calls to get_bit

usage:

prevObstacle,nextObstacle = obstacleRanges[column_index,row_index]
for moveRow in range(prevObstacle+1, nextObstacle):
    action = Action(Position(row_index, column_index), Position(moveRow, column_index), color)
    all_available_moves_for_pawn.append(action)

Note that this may or may not improve performance depending on the distribution and number of you pawns and also on how many times you query the actions with the same obstacle layout. For example, if your pawns ARE the obstacles and they are moving, it would be preferable to update the structure with the effect of pawn movements rather than recalculate it completely.

Optimize For loop for speed python

1 Answers1