6
\$\begingroup\$

Disclaimer: This is a competition (Halite 2) where the rules are lenient about taking help from outside and even promote creating a new pathfinding function/algorithm.

Read 'A Journey of a Thousand Li Starts Beneath One’s Feet'.

Read 'Community Policies'

I am trying to get this code to execute in under 2 seconds (as less time as possible) due to limitations in the competition so that I can relay my pathfinding to the bot. Each grid in the competition will be a max of (WxH 360x240). This code generates the steps required for a ship to move in. The dijkstra function loops through the entire grid and then sets each coordinate a cost - derived by travel from the goal. The implementation function just checks the closest and least costly point and gives out an angle. The grid class just makes a dictionary of coordinates to their cost/angle (depending on the function setting it).

I am running on a macbook pro mid 2012 retina display model so I am uncertain if I am being withheld by my computer however I have no means of checking.

import heapq
import cProfile
# I tried using @jit() for functions but it just seemed to slow it down even more
from numba import jit

class PriorityQueue:
    def __init__(self):
        self.elements = []

    def empty(self):
        return len(self.elements) == 0

    def put(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def get(self):
        return heapq.heappop(self.elements)[1]

class Grid:

    def __init__(self, width, height, obstacles=[]):
        self.width = width
        self.height = height
        self.obstacles_symbol = '#'
        self.reset_int = -2

        self.obstacles = obstacles
        self.coords = self.reset_values()


    def reset_values(self):
        points = {}
        for y in range(self.height):
            for x in range(self.width):
                if (x,y) in self.obstacles:
                    points[(x,y)] = self.obstacles_symbol
                else:
                    points[(x,y)] = self.reset_int

        return points

    def passable(self, id):
        return id not in self.coords

    def in_bounds(self, list):
        allowed = []
        for (x,y) in list:
            if 0 <= x < self.width and 0 <= y < self.height:
                allowed.append((x,y))
        return allowed

    def get_neighbours(self, id, no_horizontal=False):
        (x, y) = id

        if not no_horizontal:
            results = [
                (x-1, y+1), (x, y+1), (x+1, y+1),
                (x-1, y),               (x+1, y),
                (x-1, y-1), (x, y-1), (x+1, y-1),
            ]
        else:
            results = [
                            (x, y+1),
                (x-1, y),               (x+1, y),
                            (x, y-1)
            ]


        # results = filter(self.in_bounds, results)
        results = self.in_bounds(results)
        # results = filter(self.passable, results)
        return results

    def _set_value_at(self, coordinate, value):
        self.coords[coordinate] = value

    def _get_value_at(self, coordinate):
        return self.coords[coordinate]



class FlowField(Grid):

    def __init__(self, width, height, obstacles=[]):
        self.width = width
        self.height = height
        self.obstacles_symbol = '#'
        self.reset_int = -1

        self.obstacles = obstacles
        self.coords = self.reset_values()


    def reset_values(self):
        points = {}
        for y in range(self.height):
            for x in range(self.width):
                if (x,y) in self.obstacles:
                    points[(x,y)] = self.obstacles_symbol
                else:
                    points[(x,y)] = self.reset_int

        return points


    def get_direction(self, from_node, to_node, no_horizontal=False):
        (x, y) = from_node

        if not no_horizontal:
            results = {
                (x-1, y+1):225,   (x, y+1):180,  (x+1, y+1):135,
                (x-1, y):270,                    (x+1, y):90,
                (x-1, y-1):315, (x, y-1):0, (x+1, y-1):45,
            }

        else:
            results = {
                              (x, y+1):360,
                (x-1, y):270,               (x+1, y):90,
                              (x, y-1):180,
            }

        try:
            return results[to_node]
        except Exception as e:
            print(e)
            return 0



    def _set_value_at(self, coordinate, value):
        self.coords[coordinate] = value

    def _get_value_at(self, coordinate):
        return self.coords[coordinate]


def IntegrationField(start, dijkstra_grid):

    grid = FlowField(dijkstra_grid.width, dijkstra_grid.height, obstacles=dijkstra_grid.obstacles)

    for y in range(grid.height):
        for x in range(grid.width):

            if dijkstra_grid._get_value_at((x,y)) == grid.obstacles_symbol:
                continue

            neighbours = grid.get_neighbours((x,y))

            minimum = -1
            min_dist = 0

            for n in neighbours:
                if grid._get_value_at(n) == grid.obstacles_symbol:
                    continue
                else:
                    dist = dijkstra_grid._get_value_at(n) - dijkstra_grid._get_value_at((x,y))

                    if dist < min_dist:
                        minimum = n
                        min_dist = dist

            if minimum != -1:
                grid._set_value_at((x, y), grid.get_direction((x,y), minimum))
    return grid




def dijkstra(goal, width=10, height=10, grid=None):
    if not grid:
        grid = Grid(width, height)

    distance = 0
    grid.coords[goal] = distance

    to_visit = [goal]

    for i in to_visit:
        neighbours = grid.get_neighbours(i, no_horizontal=True)

        for n in neighbours:
            if grid._get_value_at(n) == grid.reset_int:
                grid._set_value_at(n, grid._get_value_at(i) + 1)
                to_visit.append(n)

    return grid

def main():
    obstacles = [(1,1), (3,6)]

    map1 = Grid(360, 240, obstacles=obstacles)
    map1 = dijkstra((2,2), grid=map1)
    map2 = IntegrationField((2,2), map1)


    # Code from here is optional and doesn't count towards the timing.
    # It just displays the 2 grids
    for y in range(map1.height):
        for x in range(map1.width):
            try:
                if map1.coords[(x,y)] < 10:
                    print(map1.coords[(x,y)], end='   ')
                else:
                    print(map1.coords[(x,y)], end='  ')
            except Exception:
                print(map1.coords[(x,y)], end='   ')
        print()

    print()
    for y in range(map2.height):
        for x in range(map2.width):
            try:
                if map2.coords[(x,y)] < 10:
                    print(map2.coords[(x,y)], end='    ')
                elif map2.coords[(x,y)]  >= 10 and map2.coords[(x,y)] < 100:
                    print(map2.coords[(x,y)], end='   ')
                else:
                    print(map2.coords[(x,y)], end='  ')
            except Exception:
                print(map2.coords[(x,y)], end='    ')
        print()

if __name__ == '__main__':
    # I used cProfile to measure timings -- shown later
    cProfile.run('main()')

The cProfile output (doesn't count the prints):

             4303091 function calls in 3.506 seconds

   Ordered by: standard name

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        1    0.011    0.011    3.506    3.506 <string>:1(<module>)
    86397    0.163    0.000    0.163    0.000 lel.py:107(get_direction)
    86397    0.033    0.000    0.033    0.000 lel.py:132(_set_value_at)
   687588    0.220    0.000    0.220    0.000 lel.py:135(_get_value_at)
        1    1.025    1.025    2.562    2.562 lel.py:139(IntegrationField)
        1    0.288    0.288    0.857    0.857 lel.py:171(dijkstra)
        1    0.003    0.003    3.495    3.495 lel.py:190(main)
        1    0.000    0.000    0.073    0.073 lel.py:22(__init__)
        1    0.073    0.073    0.073    0.073 lel.py:32(reset_values)
   172796    0.643    0.000    0.782    0.000 lel.py:46(in_bounds)
   172796    0.243    0.000    1.025    0.000 lel.py:53(get_neighbours)
    86397    0.030    0.000    0.030    0.000 lel.py:75(_set_value_at)
  1892333    0.565    0.000    0.565    0.000 lel.py:78(_get_value_at)
        1    0.000    0.000    0.060    0.060 lel.py:85(__init__)
        1    0.060    0.060    0.060    0.060 lel.py:95(reset_values)
        1    0.000    0.000    3.506    3.506 {built-in method builtins.exec}
  1118377    0.150    0.000    0.150    0.000 {method 'append' of 'list' objects}
        1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}

EDIT:

Ok, after implementing the suggested ideas, I would like - once again - to be reviewed on how well I have implemented it. This is because I notice a performance drop after I went off and did the changes and tweaking which surprised me. Oh and also the no_horizontal is supposed to be no_diagonal and I have fixed my mistake. The reason it was implemented (now only used for Grid) is because the path could either be only N,E,S,W or N,NE,NW etc. I wanted to try both. I didn't need it for the FlowField class so I have now removed it. This is because I need the direction in all cases.

My edited code:

import heapq
import cProfile
# I tried using @jit() for functions but it just seemed to slow it down even more
# from numba import jit


class PriorityQueue:
    def __init__(self):
        self.elements = []

    def empty(self):
        return len(self.elements) == 0

    def put(self, item, priority):
        heapq.heappush(self.elements, (priority, item))

    def get(self):
        return heapq.heappop(self.elements)[1]


class Grid:
    def __init__(self, width, height, obstacles=[]):
        self.width = width
        self.height = height
        self.obstacles_symbol = '#'
        self.reset_int = -2

        self.obstacles = obstacles
        self.coords, self.neighbours = self.reset_values()

    def reset_values(self, no_diagonal=True):
        points = {}
        neighbours = {}
        for y in range(self.height):
            for x in range(self.width):
                point = (x, y)
                if point in self.obstacles:
                    points[point] = self.obstacles_symbol
                else:
                    points[point] = self.reset_int

                if not no_diagonal:
                    neighbours[point] = list(filter(self.in_bounds, [
                        (x - 1, y + 1), (x, y + 1), (x + 1, y + 1),
                        (x - 1, y),                     (x + 1, y),
                        (x - 1, y - 1), (x, y - 1), (x + 1, y - 1),
                    ]))
                else:
                    neighbours[point] = list(filter(self.in_bounds, [
                                    (x, y + 1),
                        (x - 1, y),            (x + 1, y),
                                    (x, y - 1)
                    ]))

        return points, neighbours

    def empty(self, id):
        return self.coords[id] == self.reset_int

    def not_obstacle(self, id):
        return self.coords[id] != self.obstacles_symbol

    def in_bounds(self, id):
        (x, y) = id
        return 0 <= x < self.width and 0 <= y < self.height

    def get_neighbours(self, id, empty=False, not_obstacle=False):
        if not empty and not not_obstacle:
            return self.neighbours[id]
        elif empty and not not_obstacle:
            return list(filter(self.empty, self.neighbours[id]))
        elif not empty and not_obstacle:
            return list(filter(self.not_obstacle, self.neighbours[id]))
        else:
            return list(filter(self.not_obstacle, list(filter(self.empty, self.neighbours[id]))))




class FlowField(Grid):
    def __init__(self, width, height, obstacles=[]):
        self.width = width
        self.height = height
        self.obstacles_symbol = '#'
        self.reset_int = -1

        self.obstacles = obstacles
        self.coords, self.directions, self.neighbours = self.reset_values()

    def reset_values(self):
        points = {}
        directions = {}
        neighbours = {}
        for y in range(self.height):
            for x in range(self.width):
                point = (x, y)
                if point in self.obstacles:
                    points[point] = self.obstacles_symbol
                else:
                    points[point] = self.reset_int

                directions[point] = {
                    (x - 1, y + 1): 225, (x, y + 1): 180, (x + 1, y + 1): 135,
                    (x - 1, y): 270,                           (x + 1, y): 90,
                    (x - 1, y - 1): 315, (x, y - 1): 0,   (x + 1, y - 1): 45,
                }
                neighbours[point] = list(filter(self.in_bounds, directions[point].keys()))


        return points, directions, neighbours

    def get_direction(self, from_node, to_node):
        try:
            return self.directions[from_node][to_node]
        except Exception:
            return None

    def all_passable_points(self):
        points = list(filter(self.not_obstacle, self.coords.keys()))
        return points



def IntegrationField(dijkstra_grid):
    grid = FlowField(dijkstra_grid.width, dijkstra_grid.height, obstacles=dijkstra_grid.obstacles)

    for xy in grid.all_passable_points():
        # Avg loses by ~0.4
        neighbours = grid.get_neighbours(xy, not_obstacle=True)

        best_nbr = min(neighbours, key=lambda n: dijkstra_grid.coords[n] - dijkstra_grid.coords[xy])

        grid.coords[xy] = grid.get_direction(xy, best_nbr)

        # Avg winner by ~0.4
        # neighbours = grid.get_neighbours(xy, not_obstacle=True)
        # minimum = -1
        # min_dist = 0
        #
        # for n in neighbours:
        #     dist = dijkstra_grid.coords[n] - dijkstra_grid.coords[xy]
        #
        #     if dist < min_dist:
        #         minimum = n
        #         min_dist = dist
        #
        # if minimum != -1:
        #     grid.coords[xy] = grid.get_direction(xy, minimum)
    return grid


def dijkstra(goal, width=10, height=10, grid=None):
    if not grid:
        grid = Grid(width, height)

    distance = 0
    grid.coords[goal] = distance

    to_visit = [goal]

    for xy in to_visit:
        # Avg loses by ~0.2
        cost = grid.coords[xy] + 1
        empty_neighbours = grid.get_neighbours(xy, empty=True)
        to_visit.extend(empty_neighbours)
        grid.coords.update({p:cost for p in empty_neighbours})

        # Avg winner by ~0.2
        # neighbours = grid.get_neighbours(xy, empty=True)
        # for n in neighbours:
        #
        #     # if grid.coords[n] == grid.reset_int:
        #     grid.coords[n] = grid.coords[xy] + 1
        #     to_visit.append(n)

    return grid


def main():
    obstacles = [(1, 1), (3, 6)]

    map1 = Grid(360, 240, obstacles=obstacles)
    map1 = dijkstra((2, 2), grid=map1)
    map2 = IntegrationField(map1)

    # Code from here is optional and doesn't count towards the timing.
    # It just displays the 2 grids
    # for y in range(map1.height):
    #     for x in range(map1.width):
    #         try:
    #             if map1.coords[(x, y)] < 10:
    #                 print(map1.coords[(x, y)], end='   ')
    #             else:
    #                 print(map1.coords[(x, y)], end='  ')
    #         except Exception:
    #             print(map1.coords[(x, y)], end='   ')
    #     print()
    #
    # print()
    # for y in range(map2.height):
    #     for x in range(map2.width):
    #         try:
    #             if map2.coords[(x, y)] < 10 and map2.coords[(x, y)] > 0:
    #                 print(map2.coords[(x, y)], end='    ')
    #             elif map2.coords[(x, y)] >= 10 and map2.coords[(x, y)] < 100:
    #                 print(map2.coords[(x, y)], end='   ')
    #             elif map2.coords[(x, y)] > 100:
    #                 print(map2.coords[(x, y)], end='  ')
    #             else:
    #                 print(map2.coords[(x, y)], end='   ')
    #         except Exception:
    #             print(map2.coords[(x, y)], end='    ')
    #     print()


if __name__ == '__main__':
    # I used cProfile to measure timings -- shown later
    cProfile.run('main()')

I have included some time issues found by me in comments at the dijkstra_grid and IntegrationField. The new cProfile (unordered and as it is printed out) I ran it a couple of times and it averages out to this roughly:

         3533950 function calls in 4.341 seconds

Ordered by: standard name

ncalls  tottime  percall  cumtime  percall filename:lineno(function)
    1    0.097    0.097    4.341    4.341 <string>:1(<module>)
86398    0.069    0.000    0.069    0.000 lel.py:110(get_direction)
    1    0.031    0.031    0.060    0.060 lel.py:116(all_passable_points)
    1    0.147    0.147    2.918    2.918 lel.py:122(IntegrationField)
687572   0.379    0.000    0.379    0.000 lel.py:129(<lambda>)
    1    0.185    0.185    0.654    0.654 lel.py:150(dijkstra)
86398    0.033    0.000    0.033    0.000 lel.py:164(<dictcomp>)
    1    0.002    0.002    4.244    4.244 lel.py:177(main)
    1    0.000    0.000    0.671    0.671 lel.py:22(__init__)
    1    0.529    0.529    0.671    0.671 lel.py:31(reset_values)
344392   0.142    0.000    0.142    0.000 lel.py:56(empty)
773988   0.308    0.000    0.308    0.000 lel.py:59(not_obstacle)
1036800  0.403    0.000    0.403    0.000 lel.py:62(in_bounds)
172796   0.606    0.000    1.027    0.000 lel.py:66(get_neighbours)
    1    0.000    0.000    1.331    1.331 lel.py:80(__init__)
    1    1.055    1.055    1.331    1.331 lel.py:89(reset_values)
    1    0.000    0.000    4.341    4.341 {built-in method builtins.exec}
86398    0.294    0.000    0.672    0.000 {built-in method builtins.min}
    1    0.000    0.000    0.000    0.000 {method 'disable' of '_lsprof.Profiler' objects}
86398    0.015    0.000    0.015    0.000 {method 'extend' of 'list' objects}
86401    0.015    0.000    0.015    0.000 {method 'keys' of 'dict' objects}
86398    0.034    0.000    0.034    0.000 {method 'update' of 'dict' objects}

EDIT 2:

I have tried to make my code faster by using @jit decorators and this is my new code.

@njit
def get_neighbours(point, rows, cols):

    (x,y) = point
    results = [
                            (x, y + 1),
                 (x - 1, y),            (x + 1, y),
                            (x, y - 1)
              ]

    return [r for r in results if r[0] <= rows and r[0] >= 0 and r[1] <= cols and r[1] >= 0 ]

@jit
def get_direction(point, rows, cols):
    (x, y) = point
    directions = {
        (x - 1, y + 1): 225, (x, y + 1): 180, (x + 1, y + 1): 135,
        (x - 1, y): 270,                       (x + 1, y): 90,
        (x - 1, y - 1): 315, (x, y - 1): 0,    (x + 1, y - 1): 45,
    }

    delete = []
    for k in directions.keys():
        if k[0] >= rows or k[0] < 0 or k[1] >= cols or k[1] < 0:
            delete.append(k)

    for i in delete:
        del directions[i]

    return directions


@njit
def init(rows, cols, obstacles=[], dtype=np.int32):
    dmask = np.zeros((rows, cols), dtype=dtype)
    for xy in obstacles:
        dmask[xy] = 900
    inarray = np.zeros((rows, cols), dtype=dtype)
    return dmask, inarray

@njit
def explore_point(point_to_explore, rows, cols, inarray, dmask):
    neighbours = get_neighbours(point_to_explore, rows, cols)
    unexplored = []

    for n in neighbours:
        if dmask[n] == 0:
            inarray[n] += (inarray[point_to_explore] + 1)
            dmask[n] += 1
            unexplored.append(n)
        elif dmask[n] == 900:
            inarray[n] = 900

    return unexplored

@njit
def jitfront(inarray, goal, dmask, r, c):
    pointstoexplore = []
    pointstoexplore.append(goal)
    while pointstoexplore:
        epoint = pointstoexplore[0]
        pointstoexplore.pop(0)
        for nextoexplore in explore_point(epoint, r, c, inarray, dmask):
           pointstoexplore.append(nextoexplore)


    inarray[goal] = 0
    return inarray


def vectorfield(inarray, goal, r, c):
    vectorarray = np.zeros((r,c), dtype=np.int32)
    for y in range(0,c):
        for x in range(0,r):
            xy = (x,y)
            neighbours = get_direction(xy, r, c)
            best_nbr = min(neighbours.keys(), key=lambda n: inarray[n])
            vectorarray[xy] = neighbours[best_nbr]

    vectorarray[goal] = -1
    return vectorarray

def main():

    w, h = 10, 9
    obstacles = [(2,2), (0,0)]
    dmask, inarray = init(w, h, obstacles=obstacles)

    inarray = jitfront(inarray, (0,1), dmask, w, h)
    inarray = vectorfield(inarray, (0,1), w, h)

    # Similarly to my last code, this doesn't count towards timing
    for x in range(h):
        for y in range(w):
            if inarray[(y,x)] < 10 and inarray[(y,x)] >= 0:
                print(inarray[(y,x)], end='   ')
            elif inarray[(y,x)] >= 10 and inarray[(y,x)] < 100:
                print(inarray[(y,x)], end='  ')
            elif inarray[(y,x)] > 100:
                print(inarray[(y,x)], end=' ')
            else:
                print(inarray[(y,x)], end='  ')


        print()


cProfile.run('main()')

The cProfile timings are HUGELY FASTER but still not fast enough sadly (however I notice that the first time it runs is like 3.2 and then if run again it comes back down to 2.2-2.5). Also there were more function calls but they all were 0 time so I discluded them:

200307 function calls (195348 primitive calls) in 2.398 seconds

   Ordered by: cumulative time

   ncalls  tottime  percall  cumtime  percall filename:lineno(function)
        5    0.000    0.000    2.684    0.537 __init__.py:3(<module>)
    329/1    0.026    0.000    2.399    2.399 {built-in method builtins.exec}
        1    0.000    0.000    2.399    2.399 lel1.py:1(<module>)
    338/3    0.004    0.000    2.366    0.789 <frozen importlib._bootstrap>:966(_find_and_load)
    338/3    0.003    0.000    2.366    0.789 <frozen importlib._bootstrap>:936(_find_and_load_unlocked)
    323/3    0.003    0.000    2.365    0.788 <frozen importlib._bootstrap>:651(_load_unlocked)
    286/3    0.002    0.000    2.365    0.788 <frozen importlib._bootstrap_external>:672(exec_module)
    481/3    0.001    0.000    2.341    0.780 <frozen importlib._bootstrap>:211(_call_with_frames_removed)
   402/19    0.001    0.000    2.249    0.118 {built-in method builtins.__import__}
  1488/82    0.003    0.000    2.245    0.027 <frozen importlib._bootstrap>:997(_handle_fromlist)
       15    0.001    0.000    2.117    0.141 __init__.py:1(<module>)
      286    0.006    0.000    1.500    0.005 <frozen importlib._bootstrap_external>:743(get_code)
      286    0.030    0.000    1.407    0.005 <frozen importlib._bootstrap_external>:830(get_data)
      286    1.377    0.005    1.377    0.005 {method 'read' of '_io.FileIO' objects}
        1    0.000    0.000    0.772    0.772 __init__.py:106(<module>)
        1    0.000    0.000    0.615    0.615 add_newdocs.py:10(<module>)
        1    0.000    0.000    0.475    0.475 type_check.py:3(<module>)
        1    0.000    0.000    0.442    0.442 special.py:1(<module>)
        1    0.000    0.000    0.442    0.442 config.py:1(<module>)
  322/320    0.001    0.000    0.436    0.001 <frozen importlib._bootstrap>:564(module_from_spec)
    31/30    0.000    0.000    0.420    0.014 <frozen importlib._bootstrap_external>:919(create_module)
    31/30    0.403    0.013    0.419    0.014 {built-in method _imp.create_dynamic}
        1    0.000    0.000    0.392    0.392 parfor.py:14(<module>)
        1    0.000    0.000    0.363    0.363 decorators.py:3(<module>)
        3    0.000    0.000    0.362    0.121 registry.py:1(<module>)
        1    0.000    0.000    0.293    0.293 array_analysis.py:6(<module>)
        3    0.000    0.000    0.256    0.085 __init__.py:7(<module>)
        1    0.000    0.000    0.227    0.227 extending.py:2(<module>)
        1    0.000    0.000    0.193    0.193 decorators.py:15(<module>)
        1    0.000    0.000    0.185    0.185 dylib.py:1(<module>)
        1    0.000    0.000    0.183    0.183 cpu.py:1(<module>)
        1    0.000    0.000    0.176    0.176 utils.py:4(<module>)
        1    0.000    0.000    0.155    0.155 dispatcher.py:3(<module>)
        1    0.000    0.000    0.130    0.130 ffi.py:1(<module>)
        1    0.000    0.000    0.127    0.127 pythonapi.py:1(<module>)
        3    0.000    0.000    0.126    0.042 __init__.py:332(__init__)
        3    0.125    0.042    0.125    0.042 {built-in method _ctypes.dlopen}
        1    0.000    0.000    0.097    0.097 shutil.py:5(<module>)
        2    0.000    0.000    0.093    0.046 analysis.py:3(<module>)
        3    0.000    0.000    0.086    0.029 context.py:1(<module>)
      332    0.005    0.000    0.081    0.000 <frozen importlib._bootstrap>:870(_find_spec)
        1    0.000    0.000    0.078    0.078 abstract.py:1(<module>)
        1    0.000    0.000    0.076    0.076 compiler.py:1(<module>)
      327    0.001    0.000    0.073    0.000 <frozen importlib._bootstrap_external>:1149(find_spec)
      327    0.003    0.000    0.072    0.000 <frozen importlib._bootstrap_external>:1117(_get_spec)
        2    0.000    0.000    0.064    0.032 utils.py:1(<module>)
      286    0.002    0.000    0.064    0.000 <frozen importlib._bootstrap_external>:485(_compile_bytecode)
        2    0.000    0.000    0.063    0.031 base.py:1(<module>)
        1    0.000    0.000    0.061    0.061 platform.py:10(<module>)
      286    0.060    0.000    0.060    0.000 {built-in method marshal.loads}
      518    0.010    0.000    0.059    0.000 <frozen importlib._bootstrap_external>:1233(find_spec)
1161/1158    0.033    0.000    0.059    0.000 {built-in method builtins.__build_class__}
        2    0.000    0.000    0.058    0.029 __init__.py:15(<module>)
        1    0.000    0.000    0.057    0.057 tempfile.py:24(<module>)
        2    0.000    0.000    0.054    0.027 __init__.py:45(<module>)
        1    0.000    0.000    0.052    0.052 random.py:38(<module>)
        1    0.000    0.000    0.051    0.051 subprocess.py:42(<module>)
        1    0.000    0.000    0.043    0.043 _internal.py:6(<module>)
        5    0.000    0.000    0.041    0.008 decorators.py:41(jit)
        5    0.000    0.000    0.041    0.008 decorators.py:182(wrapper)
        5    0.000    0.000    0.041    0.008 dispatcher.py:455(__init__)
        4    0.000    0.000    0.041    0.010 decorators.py:221(njit)
      3/2    0.000    0.000    0.040    0.020 utils.py:280(__get__)
        5    0.000    0.000    0.040    0.008 registry.py:45(target_context)
        1    0.000    0.000    0.040    0.040 registry.py:35(_toplevel_target_context)
        1    0.000    0.000    0.040    0.040 base.py:222(__init__)
        1    0.000    0.000    0.040    0.040 hashlib.py:54(<module>)
        1    0.000    0.000    0.039    0.039 reduction.py:10(<module>)
        1    0.000    0.000    0.039    0.039 cpu.py:40(init)
        1    0.000    0.000    0.036    0.036 __init__.py:10(<module>)
        1    0.000    0.000    0.036    0.036 inspect.py:27(<module>)
     18/5    0.000    0.000    0.036    0.007 llvmthreadsafe.py:27(wrapped)
        1    0.000    0.000    0.035    0.035 nrt.py:19(initialize)
        1    0.000    0.000    0.035    0.035 nrtdynmod.py:194(compile_nrt_functions)
        1    0.000    0.000    0.035    0.035 py3k.py:4(<module>)
     1252    0.001    0.000    0.034    0.000 <frozen importlib._bootstrap_external>:75(_path_stat)
        1    0.000    0.000    0.034    0.034 inline_closurecall.py:1(<module>)
        1    0.000    0.000    0.034    0.034 rules.py:1(<module>)
     1271    0.033    0.000    0.033    0.000 {built-in method posix.stat}
        1    0.000    0.000    0.033    0.033 lowering.py:1(<module>)
        1    0.000    0.000    0.033    0.033 codegen.py:1(<module>)
        1    0.000    0.000    0.033    0.033 postproc.py:1(<module>)
        1    0.000    0.000    0.032    0.032 rules.py:16(_init_casting_rules)
       40    0.000    0.000    0.032    0.001 castgraph.py:122(insert_rule)
       40    0.007    0.000    0.031    0.001 castgraph.py:95(propagate)
       41    0.002    0.000    0.031    0.001 __init__.py:357(namedtuple)
        1    0.000    0.000    0.030    0.030 polynomial.py:4(<module>)
        1    0.000    0.000    0.028    0.028 lzma.py:9(<module>)
        1    0.000    0.000    0.027    0.027 bz2.py:5(<module>)
      140    0.001    0.000    0.027    0.000 re.py:286(_compile)
       38    0.000    0.000    0.027    0.001 re.py:231(compile)
        1    0.000    0.000    0.026    0.026 dis.py:1(<module>)
        1    0.000    0.000    0.026    0.026 __init__.py:88(<module>)
       35    0.000    0.000    0.026    0.001 sre_compile.py:557(compile)
        1    0.000    0.000    0.024    0.024 pathlib.py:1(<module>)
        1    0.000    0.000    0.023    0.023 containers.py:1(<module>)
        1    0.000    0.000    0.023    0.023 index_tricks.py:1(<module>)
        1    0.000    0.000    0.022    0.022 linalg.py:10(<module>)
       21    0.000    0.000    0.022    0.001 castgraph.py:134(unsafe)
        1    0.000    0.000    0.022    0.022 socket.py:47(<module>)
        1    0.000    0.000    0.021    0.021 numeric.py:1(<module>)
      448    0.001    0.000    0.021    0.000 <frozen importlib._bootstrap_external>:85(_path_is_mode_type)
      416    0.001    0.000    0.021    0.000 <frozen importlib._bootstrap_external>:94(_path_isfile)
        1    0.000    0.000    0.020    0.020 scalars.py:1(<module>)
        1    0.000    0.000    0.020    0.020 datetime.py:5(<module>)
        1    0.000    0.000    0.019    0.019 misc.py:1(<module>)
        1    0.000    0.000    0.019    0.019 arrayprint.py:5(<module>)
        1    0.000    0.000    0.018    0.018 values.py:4(<module>)
        9    0.000    0.000    0.017    0.002 typeconv.py:85(safe_unsafe)
        1    0.000    0.000    0.016    0.016 ir_utils.py:6(<module>)
        1    0.000    0.000    0.016    0.016 serialize.py:3(<module>)
        1    0.000    0.000    0.015    0.015 arrayobj.py:4(<module>)
        1    0.000    0.000    0.015    0.015 __init__.py:2(<module>)
        1    0.000    0.000    0.015    0.015 codegen.py:206(finalize)
        2    0.000    0.000    0.015    0.007 decorators.py:1(<module>)
        1    0.000    0.000    0.014    0.014 opcode.py:5(<module>)
       35    0.000    0.000    0.014    0.000 sre_compile.py:542(_code)
        1    0.000    0.000    0.014    0.014 case.py:1(<module>)
        1    0.000    0.000    0.014    0.014 npyio.py:1(<module>)
        1    0.000    0.000    0.014    0.014 nrtdynmod.py:170(create_nrt_module)
      322    0.003    0.000    0.013    0.000 <frozen importlib._bootstrap>:504(_init_module_attrs)
        1    0.000    0.000    0.013    0.013 errors.py:3(<module>)
        1    0.000    0.000    0.013    0.013 uuid.py:45(<module>)
        1    0.000    0.000    0.013    0.013 type_annotations.py:1(<module>)
15008/14989    0.008    0.000    0.012    0.000 abstract.py:110(__hash__)
   263/35    0.002    0.000    0.012    0.000 sre_compile.py:64(_compile)
        1    0.000    0.000    0.012    0.012 transforms.py:3(<module>)
     2785    0.004    0.000    0.011    0.000 <frozen importlib._bootstrap_external>:57(_path_join)
       35    0.000    0.000    0.011    0.000 sre_parse.py:844(parse)
        1    0.000    0.000    0.011    0.011 nrtdynmod.py:154(_define_nrt_unresolved_abort)
        1    0.000    0.000    0.011    0.011 callconv.py:333(return_user_exc)
      286    0.008    0.000    0.011    0.000 <frozen importlib._bootstrap_external>:430(_validate_bytecode_header)
      146    0.003    0.000    0.010    0.000 abc.py:132(__new__)
        1    0.000    0.000    0.010    0.010 __init__.py:41(<module>)
        1    0.000    0.000    0.010    0.010 base.py:861(get_python_api)
        1    0.000    0.000    0.010    0.010 pythonapi.py:143(__init__)
        1    0.000    0.000    0.010    0.010 npydecl.py:1(<module>)
        1    0.000    0.000    0.010    0.010 selectors.py:5(<module>)
      590    0.001    0.000    0.010    0.000 <frozen importlib._bootstrap_external>:1080(_path_importer_cache)
   122/37    0.001    0.000    0.010    0.000 sre_parse.py:407(_parse_sub)
   132/40    0.003    0.000    0.009    0.000 sre_parse.py:470(_parse)
     2032    0.003    0.000    0.009    0.000 castgraph.py:42(insert)
        1    0.000    0.000    0.009    0.009 codegen.py:236(_finalize_final_module)
        1    0.000    0.000    0.009    0.009 codegen.py:464(_finalize_specific)
        1    0.008    0.008    0.008    0.008 executionengine.py:100(finalize_object)
        8    0.000    0.000    0.008    0.001 typeconv.py:78(promote_unsafe)
      572    0.004    0.000    0.008    0.000 <frozen importlib._bootstrap_external>:263(cache_from_source)
       11    0.000    0.000    0.008    0.001 castgraph.py:131(safe)
      338    0.001    0.000    0.007    0.000 <frozen importlib._bootstrap>:147(__enter__)
        1    0.000    0.000    0.007    0.007 threading.py:1(<module>)
      603    0.001    0.000    0.007    0.000 <frozen importlib._bootstrap>:403(cached)
      286    0.001    0.000    0.007    0.000 <frozen importlib._bootstrap_external>:840(path_stats)
        1    0.000    0.000    0.007    0.007 codegen.py:177(add_ir_module)
      275    0.002    0.000    0.007    0.000 function_base.py:4519(add_newdoc)
        1    0.000    0.000    0.007    0.007 typeof.py:1(<module>)
        1    0.000    0.000    0.007    0.007 main.py:1(<module>)
      317    0.001    0.000    0.006    0.000 <frozen importlib._bootstrap_external>:361(_get_cached)
      734    0.004    0.000    0.006    0.000 <frozen importlib._bootstrap>:157(_get_module_lock)
      396    0.001    0.000    0.006    0.000 <frozen importlib._bootstrap>:194(_lock_unlock_module)
        1    0.000    0.000    0.006    0.006 codegen.py:119(_optimize_final_module)
        8    0.000    0.000    0.006    0.001 typeconv.py:66(unsafe)
        2    0.000    0.000    0.006    0.003 typeconv.py:92(unsafe_unsafe)
        2    0.000    0.000    0.006    0.003 util.py:1(<module>)
        1    0.000    0.000    0.006    0.006 traceback.py:1(<module>)
     2785    0.004    0.000    0.006    0.000 <frozen importlib._bootstrap_external>:59(<listcomp>)
     1747    0.001    0.000    0.006    0.000 enum.py:265(__call__)
     5838    0.005    0.000    0.006    0.000 {built-in method builtins.getattr}
      317    0.001    0.000    0.006    0.000 <frozen importlib._bootstrap_external>:1228(_get_spec)
     4765    0.005    0.000    0.005    0.000 {built-in method builtins.hasattr}
      145    0.005    0.000    0.005    0.000 {built-in method posix.getcwd}
       92    0.000    0.000    0.005    0.000 sre_compile.py:223(_compile_charset)
      318    0.005    0.000    0.005    0.000 {built-in method __new__ of type object at 0x1007e4d78}
        1    0.000    0.000    0.005    0.005 linecache.py:6(<module>)
        1    0.005    0.005    0.005    0.005 passmanagers.py:94(run)
      784    0.002    0.000    0.005    0.000 enum.py:801(__and__)
       92    0.004    0.000    0.005    0.000 sre_compile.py:250(_optimize_charset)
       32    0.000    0.000    0.004    0.000 <frozen importlib._bootstrap_external>:1281(_fill_cache)
      322    0.003    0.000    0.004    0.000 <frozen importlib._bootstrap>:318(__exit__)
        2    0.000    0.000    0.004    0.002 module.py:1(<module>)
     2032    0.001    0.000    0.004    0.000 castgraph.py:51(get)
      734    0.004    0.000    0.004    0.000 <frozen importlib._bootstrap>:78(acquire)
        1    0.000    0.000    0.004    0.004 tokenize.py:21(<module>)
     3335    0.002    0.000    0.004    0.000 {method 'get' of 'dict' objects}
      317    0.003    0.000    0.004    0.000 <frozen importlib._bootstrap_external>:524(spec_from_file_location)
        1    0.000    0.000    0.004    0.004 string.py:15(<module>)
        7    0.000    0.000    0.004    0.001 enum.py:602(_convert)
        1    0.000    0.000    0.004    0.004 pickle.py:24(<module>)
 1095/981    0.003    0.000    0.004    0.000 {method 'format' of 'str' objects}
       79    0.000    0.000    0.004    0.000 npydecl.py:307(_numpy_ufunc)
3721/3720    0.002    0.000    0.004    0.000 {method 'join' of 'str' objects}
       14    0.001    0.000    0.004    0.000 enum.py:124(__new__)
        1    0.000    0.000    0.004    0.004 string.py:65(__init__)
        1    0.000    0.000    0.003    0.003 dufunc.py:1(<module>)
  196/193    0.001    0.000    0.003    0.000 abstract.py:54(__call__)
        1    0.000    0.000    0.003    0.003 codegen.py:198(add_llvm_module)
        1    0.000    0.000    0.003    0.003 numerictypes.py:82(<module>)
       32    0.003    0.000    0.003    0.000 {built-in method posix.listdir}
        1    0.000    0.000    0.003    0.003 parse.py:28(<module>)
        1    0.000    0.000    0.003    0.003 dyld.py:3(<module>)
        1    0.000    0.000    0.003    0.003 numpy_support.py:1(<module>)
     2997    0.001    0.000    0.003    0.000 {method 'add' of 'set' objects}
        1    0.000    0.000    0.003    0.003 caching.py:3(<module>)
        1    0.000    0.000    0.003    0.003 executionengine.py:1(<module>)
      734    0.003    0.000    0.003    0.000 <frozen importlib._bootstrap>:103(release)
        1    0.000    0.000    0.003    0.003 builder.py:1(<module>)
        1    0.000    0.000    0.003    0.003 core.py:21(<module>)
        1    0.000    0.000    0.003    0.003 codegen.py:528(__init__)
       32    0.001    0.000    0.003    0.000 <frozen importlib._bootstrap_external>:1067(_path_hooks)
    17601    0.003    0.000    0.003    0.000 abstract.py:88(key)
     2044    0.001    0.000    0.003    0.000 castgraph.py:68(__getitem__)
     2213    0.001    0.000    0.003    0.000 abstract.py:116(__ne__)
        1    0.000    0.000    0.003    0.003 models.py:1(<module>)
        1    0.000    0.000    0.003    0.003 nrt.py:1(<module>)
     3004    0.003    0.000    0.003    0.000 <frozen importlib._bootstrap>:222(_verbose_message)
      338    0.001    0.000    0.003    0.000 <frozen importlib._bootstrap>:151(__exit__)
        7    0.000    0.000    0.003    0.000 enum.py:364(_create_)
       41    0.000    0.000    0.003    0.000 templates.py:675(decorator)
        3    0.000    0.000    0.003    0.001 module.py:215(__repr__)
       41    0.000    0.000    0.003    0.000 templates.py:653(decorate)
        2    0.001    0.000    0.002    0.001 six.py:1(<module>)
        8    0.000    0.000    0.002    0.000 typeconv.py:60(promote)
        1    0.000    0.000    0.002    0.002 codegen.py:539(_init)
        8    0.000    0.000    0.002    0.000 castgraph.py:128(promote)
     5725    0.002    0.000    0.002    0.000 {built-in method builtins.isinstance}
        3    0.000    0.000    0.002    0.001 module.py:189(_get_body_lines)
        3    0.000    0.000    0.002    0.001 module.py:194(<listcomp>)
        1    0.000    0.000    0.002    0.002 polynomial.py:56(<module>)
15029/15010    0.002    0.000    0.002    0.000 {built-in method builtins.hash}
        1    0.000    0.000    0.002    0.002 ufuncbuilder.py:2(<module>)
        2    0.000    0.000    0.002    0.001 nrtopt.py:149(remove_redundant_nrt_refct)
     6203    0.002    0.000    0.002    0.000 {method 'rstrip' of 'str' objects}
        1    0.000    0.000    0.002    0.002 result.py:1(<module>)
        1    0.000    0.000    0.002    0.002 interpreter.py:1(<module>)
      572    0.001    0.000    0.002    0.000 <frozen importlib._bootstrap_external>:52(_r_long)
        1    0.000    0.000    0.002    0.002 codegen.py:105(_optimize_functions)
        1    0.000    0.000    0.002    0.002 value.py:2(<module>)
       14    0.000    0.000    0.002    0.000 hashlib.py:116(__get_openssl_constructor)
        8    0.000    0.000    0.002    0.000 values.py:654(__str__)
        8    0.000    0.000    0.002    0.000 values.py:647(descr)
        1    0.000    0.000    0.002    0.002 signal.py:1(<module>)
        1    0.000    0.000    0.002    0.002 fftpack.py:32(<module>)
        8    0.000    0.000    0.002    0.000 hashlib.py:73(__get_builtin_constructor)
   180/88    0.000    0.000    0.002    0.000 _utils.py:40(__str__)
     1740    0.001    0.000    0.002    0.000 enum.py:515(__new__)
       32    0.000    0.000    0.002    0.000 <frozen importlib._bootstrap_external>:1322(path_hook_for_FileFinder)
        1    0.000    0.000    0.002    0.002 funcdesc.py:3(<module>)
2261/2256    0.001    0.000    0.002    0.000 abstract.py:113(__eq__)
        1    0.000    0.000    0.002    0.002 npytypes.py:1(<module>)
     1252    0.001    0.000    0.002    0.000 sre_parse.py:253(get)
        1    0.000    0.000    0.002    0.002 cProfile.py:15(run)
        1    0.000    0.000    0.002    0.002 profile.py:52(run)
        1    0.000    0.000    0.002    0.002 cProfile.py:92(run)
        1    0.000    0.000    0.002    0.002 cProfile.py:97(runctx)
        1    0.002    0.002    0.002    0.002 {method 'enable' of '_lsprof.Profiler' objects}
     2808    0.002    0.000    0.002    0.000 {method 'rpartition' of 'str' objects}
        1    0.000    0.000    0.002    0.002 codegen.py:590(_module_pass_manager)
        1    0.000    0.000    0.002    0.002 fromnumeric.py:3(<module>)
        2    0.000    0.000    0.002    0.001 function_base.py:1(<module>)
        1    0.000    0.000    0.002    0.002 defmatrix.py:1(<module>)
        1    0.000    0.000    0.002    0.002 quicksort.py:2(<module>)
        2    0.000    0.000    0.002    0.001 transforms.py:101(populate)
        1    0.000    0.000    0.002    0.002 types.py:3(<module>)
        1    0.000    0.000    0.002    0.002 nrtopt.py:3(<module>)
       37    0.000    0.000    0.002    0.000 values.py:210(_to_string)
        4    0.000    0.000    0.001    0.000 warnings.py:119(filterwarnings)
      449    0.001    0.000    0.001    0.000 _weakrefset.py:36(__init__)
        6    0.000    0.000    0.001    0.000 llvmthreadsafe.py:57(wrapper)
      335    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:58(__init__)
        1    0.001    0.001    0.001    0.001 transforms.py:95(_populate_module_pm)
        6    0.001    0.000    0.001    0.000 module.py:11(parse_assembly)
        1    0.000    0.000    0.001    0.001 ntpath.py:6(<module>)
      741    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:416(parent)
     1425    0.001    0.000    0.001    0.000 {built-in method builtins.setattr}
      196    0.000    0.000    0.001    0.000 abstract.py:42(_intern)
        7    0.000    0.000    0.001    0.000 values.py:640(descr_body)
       13    0.000    0.000    0.001    0.000 values.py:736(descr)
        8    0.001    0.000    0.001    0.000 passmanagers.py:123(run)
  453/225    0.001    0.000    0.001    0.000 sre_parse.py:173(getwidth)
      335    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:176(cb)
     1641    0.001    0.000    0.001    0.000 sre_parse.py:232(__next)
      572    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap_external>:63(_path_split)
        1    0.000    0.000    0.001    0.001 callconv.py:3(<module>)
      146    0.000    0.000    0.001    0.000 abc.py:135(<setcomp>)
        1    0.000    0.000    0.001    0.001 utils.py:288(inner)
        1    0.000    0.000    0.001    0.001 base.py:151(_load_global_helpers)
  592/579    0.000    0.000    0.001    0.000 {built-in method builtins.issubclass}
      128    0.001    0.000    0.001    0.000 functools.py:44(update_wrapper)
      176    0.000    0.000    0.001    0.000 typeconv.py:99(_cb_update)
       13    0.000    0.000    0.001    0.000 values.py:738(<listcomp>)
      342    0.001    0.000    0.001    0.000 {built-in method builtins.any}
        1    0.000    0.000    0.001    0.001 setobj.py:3(<module>)
        1    0.000    0.000    0.001    0.001 framework.py:3(<module>)
        5    0.000    0.000    0.001    0.000 six.py:784(wrapper)
        1    0.000    0.000    0.001    0.001 pathlib.py:382(_NormalAccessor)
     1125    0.001    0.000    0.001    0.000 sre_parse.py:163(__getitem__)
       35    0.000    0.000    0.001    0.000 sre_compile.py:482(_compile_info)
        1    0.000    0.000    0.001    0.001 instructions.py:3(<module>)
        2    0.000    0.000    0.001    0.001 nrtopt.py:15(_remove_redundant_nrt_refct)
        1    0.001    0.001    0.001    0.001 selectors.py:290(SelectSelector)
       11    0.001    0.000    0.001    0.000 pathlib.py:384(_wrap_strfunc)
      173    0.001    0.000    0.001    0.000 enum.py:70(__setitem__)
      136    0.000    0.000    0.001    0.000 __init__.py:358(__getattr__)
        1    0.000    0.000    0.001    0.001 cgutils.py:3(<module>)
        1    0.000    0.000    0.001    0.001 loader.py:1(<module>)
      272    0.001    0.000    0.001    0.000 dylib.py:16(add_symbol)
        7    0.000    0.000    0.001    0.000 enum.py:623(<listcomp>)
      135    0.001    0.000    0.001    0.000 functions.py:11(__init__)
      286    0.001    0.000    0.001    0.000 {built-in method _imp._fix_co_filename}
        1    0.000    0.000    0.001    0.001 difflib.py:27(<module>)
        1    0.000    0.000    0.001    0.001 imputils.py:3(<module>)
  146/141    0.000    0.000    0.001    0.000 abc.py:194(__subclasscheck__)
        1    0.000    0.000    0.001    0.001 controlflow.py:1(<module>)
     1004    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:847(__exit__)
     2605    0.001    0.000    0.001    0.000 {built-in method builtins.min}
3860/3726    0.001    0.000    0.001    0.000 {built-in method builtins.len}
        1    0.000    0.000    0.001    0.001 getlimits.py:3(<module>)
        1    0.000    0.000    0.001    0.001 dylib.py:3(<module>)
        1    0.000    0.000    0.001    0.001 io_support.py:1(<module>)
        1    0.000    0.000    0.001    0.001 bytecode.py:4(<module>)
        1    0.000    0.000    0.001    0.001 typeconv.py:1(<module>)
      176    0.000    0.000    0.001    0.000 typeconv.py:31(set_compatible)
       17    0.000    0.000    0.001    0.000 ffi.py:9(_make_opaque_ref)
      572    0.001    0.000    0.001    0.000 {built-in method from_bytes}
     5361    0.001    0.000    0.001    0.000 {method 'append' of 'list' objects}
       14    0.000    0.000    0.001    0.000 nrtopt.py:37(_process_function)
        1    0.000    0.000    0.001    0.001 smartarray.py:1(<module>)
        3    0.001    0.000    0.001    0.000 npydecl.py:187(install_operations)
     2091    0.001    0.000    0.001    0.000 {built-in method builtins.max}
       43    0.000    0.000    0.001    0.000 core.py:143(get_object_signature)
       86    0.000    0.000    0.001    0.000 enum.py:795(__or__)
        1    0.000    0.000    0.001    0.001 ir.py:1(<module>)
      136    0.001    0.000    0.001    0.000 __init__.py:365(__getitem__)
     1004    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:843(__enter__)
        1    0.000    0.000    0.001    0.001 itanium_mangler.py:29(<module>)
     2073    0.001    0.000    0.001    0.000 {built-in method _imp.release_lock}
        1    0.001    0.001    0.001    0.001 npytypes.py:345(SmartArrayType)
     2073    0.001    0.000    0.001    0.000 {built-in method _imp.acquire_lock}
        1    0.000    0.000    0.001    0.001 numbers.py:6(<module>)
        1    0.000    0.000    0.001    0.001 rangeobj.py:3(<module>)
      333    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:369(__init__)
        1    0.000    0.000    0.001    0.001 argparse.py:62(<module>)
      286    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap_external>:393(_check_name_wrapper)
       78    0.000    0.000    0.001    0.000 registry.py:11(wraps)
  111/109    0.000    0.000    0.001    0.000 _utils.py:50(get_reference)
       32    0.000    0.000    0.001    0.000 <frozen importlib._bootstrap_external>:1196(__init__)
       81    0.000    0.000    0.001    0.000 manager.py:18(register)
        1    0.000    0.000    0.001    0.001 functions.py:1(<module>)
       26    0.000    0.000    0.001    0.000 core.py:6493(__init__)
       43    0.001    0.000    0.001    0.000 {built-in method _ctypes.POINTER}
        1    0.000    0.000    0.001    0.001 __init__.py:24(<module>)
  229/223    0.000    0.000    0.001    0.000 {built-in method builtins.next}
       32    0.000    0.000    0.001    0.000 <frozen importlib._bootstrap_external>:99(_path_isdir)
        1    0.000    0.000    0.001    0.001 bisect.py:1(<module>)
        1    0.000    0.000    0.001    0.001 typeinfer.py:13(<module>)
        1    0.000    0.000    0.001    0.001 runner.py:1(<module>)
      286    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:35(_new_module)
       26    0.000    0.000    0.001    0.000 core.py:6498(getdoc)
      119    0.000    0.000    0.001    0.000 typeconv.py:42(set_unsafe_convert)
        1    0.000    0.000    0.001    0.001 nrtdynmod.py:65(_define_nrt_decref)
       64    0.000    0.000    0.001    0.000 sre_parse.py:96(closegroup)
      327    0.000    0.000    0.001    0.000 <frozen importlib._bootstrap>:780(find_spec)
       35    0.000    0.000    0.001    0.000 sre_parse.py:828(fix_flags)
        6    0.000    0.000    0.001    0.000 builder.py:186(if_then)
     1883    0.001    0.000    0.001    0.000 {method 'startswith' of 'str' objects}
       82    0.000    0.000    0.001    0.000 values.py:203(__init__)
       14    0.000    0.000    0.001    0.000 npydecl.py:372(_numpy_redirect)
        1    0.000    0.000    0.001    0.001 builder.py:87(IRBuilder)
        1    0.000    0.000    0.001    0.001 externals.py:3(<module>)
      274    0.001    0.000    0.001    0.000 {method 'strip' of 'str' objects}
        1    0.000    0.000    0.001    0.001 nrtdynmod.py:44(_define_nrt_incref)
      6/3    0.000    0.000    0.001    0.000 contextlib.py:79(__enter__)
        1    0.000    0.000    0.001    0.001 extras.py:10(<module>)
        1    0.000    0.000    0.001    0.001 pickle.py:181(<listcomp>)
      214    0.000    0.000    0.001    0.000 enum.py:351(__setattr__)
      675    0.001    0.000    0.001    0.000 {built-in method _thread.allocate_lock}
      208    0.000    0.000    0.001    0.000 __init__.py:422(<genexpr>)
     1469    0.001    0.000    0.001    0.000 {built-in method _thread.get_ident}
       24    0.000    0.000    0.001    0.000 nrtopt.py:64(_process_basic_block)
        1    0.000    0.000    0.001    0.001 wrappers.py:1(<module>)
        1    0.000    0.000    0.001    0.001 ctypeslib.py:51(<module>)
       34    0.000    0.000    0.001    0.000 contextlib.py:129(contextmanager)
        1    0.000    0.000    0.001    0.001 config.py:67(__init__)
      102    0.000    0.000    0.001    0.000 re.py:169(match)
        1    0.000    0.000    0.001    0.001 config.py:70(reset)
      270    0.001    0.000    0.001    0.000 {built-in method numpy.core.multiarray.add_docstring}
        1    0.000    0.000    0.001    0.001 config.py:74(update)
        8    0.000    0.000    0.001    0.000 values.py:618(descr_prototype)
     1288    0.001    0.000    0.001    0.000 <frozen importlib._bootstrap>:321(<genexpr>)
        1    0.000    0.000    0.001    0.001 listobj.py:3(<module>)
        1    0.000    0.000    0.001    0.001 templates.py:3(<module>)
        1    0.000    0.000    0.001    0.001 targets.py:1(<module>)
        8    0.000    0.000    0.001    0.000 values.py:580(__init__)
        1    0.000    0.000    0.001    0.001 __init__.py:55(_ensure_llvm)
      682    0.000    0.000    0.001    0.000 sre_parse.py:248(match)
      332    0.000    0.000    0.001    0.000 <frozen importlib._bootstrap>:707(find_spec)
        1    0.000    0.000    0.001    0.001 debuginfo.py:3(<module>)
\$\endgroup\$
  • 1
    \$\begingroup\$ Your Title is too generic for this site, we all want to write better code ;) Policy on CR regarding the title is to simply state what your code does. \$\endgroup\$ – Ludisposed Jan 3 '18 at 23:44
8
\$\begingroup\$

Looking at your profiling results, I'm a little confused- what order do you have these sorted in?

Regardless, let's focus on total time.

Pretty much any value that doesn't start with 0.0 in the total time column is a candidate for improvement. The obvious biggie is IntegrationField, but let's look at some of the small values first. One theme that seems to repeat itself is that you can trade space for speed:

  1. get_direction: You are computing a dictionary on the fly, then looking up a tuple in that dictionary and returning the result. If you ever make the same call again, you'll recompute the dictionary and repeat the lookup. Why not cache the results? Build a dictionary of dictionaries, one time at startup, and then just look up values:

    def get_direction(self, from, to):
        return self.directions[from][to]
    

    It's worth pointing out that your no_horizontal parameters are misleading, because apparently you realy mean no_diagonal. And it's weird since they return totally different results sometimes. I think you need to explain what that's about...

  2. _get_value_at: This is horrible because it appears to be somewhat private data, but you're peeking at it. Except you're peeking at it via an accessor function, which slows everything down! If you're going to reach inside an object, just go ahead. Access the data directly! Or, see below, you could eliminate the entire thing. Your use case for _get_value_at seems to be this:

    def IntegrationField(start, dijkstra_grid):
    
        for y in range(grid.height):
            for x in range(grid.width):
                if dijkstra_grid._get_value_at((x,y)) == grid.obstacles_symbol:
                continue
    

    This repeats later, with similar behavior: iterate over some grid points, reach inside the object to check for obstacles. Just get rid of this entirely! (I'll talk about this under IntegrationField) In the meantime, replace all these calls to _get_value_at(T) with coords[T]. Better still, if getting and setting continues to dominate your performance, make your grid classes subclasses of dict so that you can use C code to do the lookups.

  3. get_neighbors: This is another space-for-time optimization. Compute these values once, at startup time. Return the same list repeatedly. Here's an advance hint: if your obstacles are constant positioned, just drop those cells from the list - there's no need to check for obstacles if the cells that contain them never get returned.

  4. in_bounds: This is only called by get_neighbors, so it will disappear if the neighbors are precomputed.

  5. <list>.append: This appears twice - once in in_bounds which will go away, and the other in dijkstra in your bfs. There are some optimizations I'll talk about under that function.

  6. dijkstra: This function boils down to this traversal of the grid:

    for i in to_visit:
        neighbours = grid.get_neighbours(i, no_horizontal=True)
    
        for n in neighbours:
            if grid._get_value_at(n) == grid.reset_int:
                grid._set_value_at(n, grid._get_value_at(i) + 1)
                to_visit.append(n)
    

    But what if there was a dedicated function that returned empty neighbors? (Or unset, or reset, or however you want to call it):

    for xy in to_visit:
        cost = grid.coords[xy] + 1
        neighbors = grid.get_empty_neighbors(xy, no_horizontal=True)
        to_visit.extend(neighbors)
        grid.coords.update({p:cost for p in neighbors})
    

    Of course, empty_neighbors isn't a constant lookup - you have to iterate over the neighbors internally to check which ones are empty. But you can make sure to do it in the most efficient order.

    Now check this out: When you have your code mostly written, and you want to squeeze out some more performance, start at the innermost loop and start caching any value that has a dot (.) in it, by storing that value into a variable with the dot replaced by an underscore outside the loop if possible. Like this:

    # Cache object lookups
    grid_coords = grid.coords
    grid_get_empty_neighbors = grid.get_empty_neighbors 
    to_visit_extend = to_visit.extend
    grid_coords_update = grid_coords.update
    
    for xy in to_visit:
        cost = grid_coords[xy] + 1
        neighbors = grid_get_empty_neighbors(xy, no_horizontal=True)
        to_visit_extend(neighbors)
        grid_coords_update({p:cost for p in neighbors})
    

    This is a pain in the ass to maintain, so you only do it when you are done changing the algorithms and stuff, and you want to squeeze out that last 10% of performance. Note also, this is strictly a c-python thing.

  7. IntegrationField: The big cheese. The head honcho. The place where ... all the time ... is spent!

    I'll start out by pointing out that every time you write (x,y) a kitten dies!

    grid._set_value_at((x, y), grid.get_direction((x,y), minimum))
    

    Because each occurrence of (x, y) is an expression that is evaluated separately. Which means a new tuple is being constructed, when if you put that into a variable, you could just reference the same variable over and over again quite efficiently.

    But wait! Because the whole x,y thing is wrong anyway. Why are you iterating over two ranges? Why don't you tell, don't ask your grid class to give you all the valid locations in the grid, in some sequence? Define an iterator for the grid!

    for p in grid.all_the_points():
    

    And since you are then immediately checking them for obstacles, why not make that a different iterator:

    for p in grid.all_the_points_with_no_obstacles():
    

    (Or maybe grid.empty_positions()?)

    And then the very next thing you do is ask for the neighbors, and then ... you check for obstacles! So why not make that another method (I used empty neighbors previously, perhaps prematurely. I'll use clear this time):

        for n in grid.clear_neighbors(p):
    

    But wait! Because you go on to implement a min function in-line, perhaps to show your disdain for the paltry performance advantages offered by the standard library?

        cn = grid.clear_neighbors(p)
        best_nbr = min(cn, key=lambda n: dijkstra_grid.coords[n] - dijkstra_grid.coords[p])
    
        grid.coords[p] = grid.get_direction(p, best_nbr)
    

    (Of course, you could observe that dijkstra_grid[p] is basically a constant in this expression, and simplify the lambda function to just lambda n: dijkstra_grid.coords[n] or whatever.)

\$\endgroup\$
  • \$\begingroup\$ I have updated my code and with results of how it went and would love for you to re-critique it as the code was based off of your criticism. Thanks! \$\endgroup\$ – Epic Boss Jan 4 '18 at 19:48
  • \$\begingroup\$ I copied your edited code into lel.py and ran it. I was getting about 4.2 seconds on my 2011 MBP. I created two methods, get_unblocked_neighbours and get_unset_neighbours, and got the time down to 3.8 seconds or so. Your single "do everything" get_neighbours method is too slow. When you call the method, the parameters determine the behavior. So just call dedicated methods. \$\endgroup\$ – Austin Hastings Jan 4 '18 at 22:33
  • \$\begingroup\$ I got another .14 sec off the lambda expression (best_nbr) by eliminating the subtract of coords[xy], since it's a constant during the execution of the min. \$\endgroup\$ – Austin Hastings Jan 4 '18 at 22:37
  • \$\begingroup\$ You're right. I did go down from 4.3 to 4.0. However, is there anyother way to speed the process up to under 2 seconds? i.e Numba jit (although it does slow my code down, I am sure I shouldn't be just adding a @jit()) or cython or numpy? Or is it just a waste to try and speed up the process or do I have to look to implement this in another language (I only have a decent grip in python, C++ is understandable but hard for me)? \$\endgroup\$ – Epic Boss Jan 5 '18 at 19:14
  • \$\begingroup\$ Have you tried implementing the grid as a 2-d array (list of lists) instead of a dictionary? \$\endgroup\$ – Austin Hastings Jan 5 '18 at 21:54

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.