How can i make this python code quicklier?-CodePudding

How can i make this code more quicklier?

def add_may_go(x,y):
    counter = 0
    for i in range(-2,3):
        cur_y = y   i 
        if cur_y < 0 or cur_y >= board_order:
            continue
        for j in range(-2,3):
            cur_x = x j
            if (i == 0 and j == 0) or cur_x < 0 or cur_x >= board_order or [cur_y,cur_x] in huge_may_go:
                continue
            if not public_grid[cur_y][cur_x]:
                huge_may_go.append([cur_y,cur_x])
                counter  = 1
    return counter

It runs toooooooo slowy now. This function is gonna run for hundreds time. Any possible suggestions is ok!

I have tried numpy. But numpy make it more slowly! Please help

CodePudding user response：

I want to highlight 2 place which need special attention.

if (...) [cur_y,cur_x] in huge_may_go:

Unlike reset condition, this is not arithmetic condition, but contains check, if huge_may_go is list it does take O(n) time or speaking simply is proportional to number of elements in list.

huge_may_go.append([cur_y,cur_x])

PythonWiki described .append method of list as O(1) but with disclaimer that Individual actions may take surprisingly long, depending on the history of the container. You might use collections.deque as replacement for list which was designed with performance of insert (at either end) in mind.

If huge_may_go must not contain duplicates and you do not care about order, then you might use set rather than list and use it for keeping tuples of y,x (set is unable to hold lists). When using .add method of set you might skip contains check, as adding existing element will have not any effect, consider that

s = set()
s.add((1,2))
s.add((3,4))
s.add((1,2))
print(s)

gives output

{(1, 2), (3, 4)}

If you would then need some contains check, set contains check is O(1).

CodePudding user response：

It is difficult to provide a definitive improvement without sample data and a bit more context. Using numpy would be beneficial if you can manage to perform all the calls (i.e. all (x,y) coordinate values) in a single operation. There are also strategies based on sets that could work but you would need to maintain additional data structures in parallel with the public_grid.

Based only on that piece of code, and without changing the rest of the program, there are a couple of things you could do that will provide small performance improvements:

loop only on eligible coordinates rather than skip invalid ones (outside of board)
only compute the curr_x, curr_y values once (track them in a dictionary for each x,y pairs). This is assuming that the same x,y coordinates are used in multiple calls to the function.
use comprehensions when possible

hugeCoord = dict() # keep track of the offset coordinates
def add_may_go(x,y):
    if (x,y) not in hugeCoord: # compute coordinates only once (the first time)
        hugeCoord[x,y] = [(cx,cy) 
                          for cx in range(max(0,x-2),min(board_order,x 3))
                          for cy in range(max(0,y-2),min(board_order,y 3))]
    # get the resulting list of coordinates using a comprehension
    fit = {[cy,cx] for cx,cy in hugeCoord[x,y] if not public_grid[cy][cx]}
    huge_may_go.extend(fit.difference(huge_may_go))
    return len(fit)

Note that, if huge_may_go was a set instead of a list, adding to it without repetitions would be more efficient because you would not need fit to be a set and you could use huge_may_go.update(fit) (the performance difference may be marginal but the code would be easier to read)

CodePudding user response：

if (i == 0 and j == 0)...: continue

Small improvement; reduce the number of iterations by not making those.

for i in (1,2):
    do stuff with i and -i
    for j in (1,2):
        do stuff with j and -j

from itertools import product
for (i,j) in product((1,2), repeat=2):
    do stuff with i,-i,j,-j