optimize if statements checking arrays-CodePudding

I wrote some code to make a terrain generation algorithm, and it takes "forever" to run. I managed to trace the issue back to a breadth first search algorithm that I made, and more specifically, these first 4 if statements that check if the current cell's neighbors are valid spots to move to. The rest of the function is because I have multiple searches going at the same time exploring different areas and I delete one of them if two touch.

     for self.x, self.y in self.active:

   # Fix from here

        if grid[self.x][self.y-1] == 1 and (self.x,self.y-1) not in self.searched: 
            self.searched.append((self.x,self.y-1))
            self.nextActive.append((self.x,self.y-1))
        if grid[self.x 1][self.y] == 1 and (self.x 1,self.y) not in self.searched: 
            self.searched.append((self.x 1,self.y))
            self.nextActive.append((self.x 1,self.y))
        if grid[self.x][self.y 1] == 1 and (self.x,self.y 1) not in self.searched: 
            self.searched.append((self.x,self.y 1))
            self.nextActive.append((self.x,self.y 1))
        if grid[self.x-1][self.y] == 1 and (self.x-1,self.y) not in self.searched: 
            self.searched.append((self.x-1,self.y))
            self.nextActive.append((self.x-1,self.y))

    # to here    it takes 0.00359s * about 1000 cycles

    self.active = self.nextActive[:]
    self.nextActive = []
    if self.active == []: 
        self.full = True
        return
    
    for i in self.active:
        for searcher in breathClassList:
            if searcher == self: continue
            if i in searcher.searched:
                if len(self.searched) >= len(searcher.searched):
                    breathClassList.remove(searcher)
                elif self in breathClassList: breathClassList.remove(self)
                break

if anyone has any suggestions to make this run faster, I am all ears.

CodePudding user response：

It looks like self.searched is a list (as you're calling append on it). Looking for an item in a list will take time proportional to the length of the list in the worst case (that is the time complexity is O(n), where n is the length).

One thing you could do is make that list a set instead, because looking up an item happens in constant time (i.e. is constant as the number of items grows. Time complexity is O(1)). You can do this here, because you're storing tuples and those are immutable and therefore hashable.

CodePudding user response：

Along with the answer from ndc85430, I would create the deltas for the search inside a separate array and loop this array to do updates. This will avoid the code repetition nicely (note using add here instead of append to show using sets instead.).

deltas = ((0, -1), (1, 0), (-1, 0), (0, 1))

for self.x, self.y in self.active:
    for dx, dy in deltas:
        x, y = self.x   dx, self.y   dy
        if grid[x][y] == 1 and (x, y) not in self.searched: 
            self.searched.add((x, y))
            self.nextActive.add((x, y))