我该如何优化这个Python代码? [英] How would I optimize this Python code?

查看:72
本文介绍了我该如何优化这个Python代码?的处理方法,对大家解决问题具有一定的参考价值,需要的朋友们下面随着小编来一起学习吧!

问题描述

我需要优化很多代码,这里有什么我可以做的吗?





< pre> import heapq 
import math
import sys
import queue
来自 .util import debug_write

class 节点:$ b​​ $ b 寻路节点

属性:
* visited_idealness(bool):我们是否在理想搜索步骤中访问了此节点?
* visited_validate(bool):我们是否在验证步骤中访问了此节点?
*被阻止(bool):此节点位置是否有防火墙
* pathlength:此节点与目标位置之间的距离


def __init __(self):
self.visited_idealness = False
self.visited_validate = False
self.blocked = False
self.pathlength = - 1


此类有助于寻路。我们保证结果将是
是准确的,但顶级玩家可能想要编写他们自己的寻路
代码以最大化时间效率

class ShortestPathFinder:
处理寻路

属性:
* HORIZONTAL(int):表示水平移动的常量
* VERTICAL(int):表示垂直移动的常量

* game_state(: obj:GameState):当前游戏状态
* game_map(:obj:GameMap):当前游戏地图


def __init __(self):
self.HORIZONTAL = 1
self.VERTICAL = 2
self.initialized = False

def initialize_map(self,game_sta te):
初始化地图

Args:
* game_state:表示我们想要的游戏状态的GameState对象

初始化地图
self.initialized =
self.game_state = game_state
self.game_map = [ [Node() for x in 范围(self.game_state.ARENA_SIZE)] for y in 范围(self.game_state.ARENA_SIZE)]

def navigate_multiple_endpoints(self,start_point,end_points,game_state):
查找一个单位到达一组终点所需的路径

Args:
* start_point:单位的起始位置
* end_points:单位的终点,应该是边缘位置列表
* game_state:当前游戏状态

返回:
在给定当前游戏状态时尝试到达end_points时start_point的单位将采用的路径。
请注意,如果塔在路径中被摧毁,或者您或您的敌人放置了防火墙,则此路径可能会发生变化。


如果 game_state.contains_stationary_unit(start_point):
return

初始化地图
self.initialize_map(game_state)
填写墙
< span class =code-keyword> for
location in self.game_state.game_map:
if self.game_state.contains_stationary_unit(location):
self.game_map [location [ 0 ]] [location [ 1 ]] .blocked = True
路径寻找
ideal_endpoints = self._idealness_search(start_point, end_points)
self._validate(ideal_endpoints,end_points)
return self._get_path(start_point,end_points)

< span class =code-keyword> def _idealness_search(self,start,end_points):

在可压缩空间的口袋中找到最理想的瓷砖。
边缘(如果可用)或最佳自毁位置,否则

current = queue.Queue()
current.put(start)
best_idealness = self._get_idealness(start,end_points)
self.game_map [start [ 0 ]] [start [ 1 ]]。visited_idealness = True
most_ideal = start

while not current.empty():
search_location = current.get()
中的代码关键字> self._get_neighbors(search_location):
if self.game_state.game_map.in_arena_bounds(邻居) self.game_map [neighbor [ 0 ]] [neig hbor [ 1 ]]。阻止:
继续

x, y =邻居
current_idealness = self._get_idealness(邻居,end_points)

如果 current_idealness> best_idealness:
best_idealness = current_idealness
most_ideal = neighbor

if not not self.game_map [x] [y] .visited_idealness self.game_map [x ] [y] .blocked:
self.game_map [x] [y] .visited_idealness = True
current.put(neighbor)

return most_ideal

def _get_neighbors(self,location ):
获取位置附近的位置

x,y = location
return [[x,y + 1 ] ,[x,y - 1 ],[x + 1 ,y],[x - 1 ,y]]

def _get_direction_from_endpoints(self,end_points):
打印消息到游戏调试输出

Args:
* end_points:一组端点,应该是边缘

返回:
方向[x,y]代表边缘。例如,右上角为[1,1],左上角为[-1,1]


point = end_points [ 0 ]
x,y = point
direction = [ 1 1 ]
如果 x< self.game_state.HALF_ARENA:
方向[ 0 ] = - 1
如果 y< self。 game_state.HALF_ARENA:
方向[ 1 ] = - 1
返回方向

def _get_idealness(self,location,end_points):
< span class =code-string> 获取图块的理想度,即单元最想要路径的可到达图块。
更好的自毁地点更理想。端点非常理想。

退货:
设备将尝试达到
的位置

如果 location in end_points:
return sys.maxsize

direction = self._get_direction_from_endpoints(end_points)

idealness = 0
if direction [ 1 ] == 1
idealness + = 28 * location [ 1 ]
else
idealness + = 28 *( 27 - location [ 1 ])
如果方向[ 0 ] == 1
理想度+ =位置[ 0 ]
else
idealness + =( 27 - location [ 0 ])

返回理想度

def _validate(self,ideal_tile, end_points):
广度优先搜索网格,设置每个节点的路径长度


VALDIATION
将我们最理想的图块添加到当前
current = queue.Queue()
如果 ideal_tile in end_points:
for location in end_points:
current.put(location)
将当前路径长度设置为0
self.game_map [location [ 0 ]] [location [< span class =code-digit> 1 ]]。pathlength = 0
self.game_map [location [ 0 ]] [location [ 1 ]]。visited_validate = True
else
current.put(ideal_tile)
self.game_map [ideal_tile [ 0 ]] [ideal_tile [ 1 ]]。pathlength = 0
self。 game_map [ideal_tile [ 0 ]] [ideal_tile [ 1 ]]。visited_validate = True

当前不为空
while not current.empty():
current_location = current。 get()
current_node = self.game_map [current_location [ 0 ]] [current_location [ 1 ]]
for neighbor in self._get_neighbors(current_location):
如果 self.game_state.game_map.in_arena_bounds(邻居) self.game_map [neighbor [ 0 ]] [邻居[ 1 ]]。阻止:
继续

neighbor_node = s elf.game_map [neighbor [ 0 ]] [neighbor [ 1 ]]
如果 neighbor_node.visited_validate not current_node.blocked:
neighbor_node.pathlength = current_node.pathlength + 1
neighbor_node.visited_validate = < span class =code-keyword> True
current.put(邻居)

debug_write(验证后打印)
self。 print_map()
return

def _get_path (self,start_point,end_points):
验证所有节点并找到目标后,单位可以路径到目标


获取路径
path = [start_point]
current = start_point
move_direction = 0

self.game_map [当前[ 0 ]] [当前[ 1 ]] .pathlength == 0
debug_write (当前tile {}的成本为{}。format(current,self.game_map [current [0]] [current [1]]。pathlength))
next_move = self._choose_next_move(当前,move_direction,end_points)
debug_write(nex t_move)

如果当前[ 0 ] == next_move [ 0 ]:
move_direction = self.VERTICAL
else
move_direction = self.HORIZONTAL
path.append(next_move)
current = next_move

debug_write(path)
return 路径

def _choose_next_move(self,current_point,previous_move_direction,end_points):
给定当前位置和相邻位置,返回给定单位的最佳'下一步'取

neighbors = self._get_neighbors(current_point)
debug_write(在{}处的单位以前移动{}并且具有这些邻居{}.format(current_point,previous_move_direction,neighbors))

ideal_neighbor = current_point
best_pathlength = self.game_map [current_point [ 0 ]] [current_point [ 1 ]]。pathlength
for neighbor in 邻居:
debug_write(比较champ {}和竞争者{}。format(ideal_neighbor,neighbour) )
如果 self.game_state.game_map.in_arena_bounds(邻居)< span class =code-keyword>或 self.game_map [neighbor [ 0 ]] [neighbor [ 1 ]]。阻止:
continue

new_best = False
x,y =邻居
current_pathlength = self .game_map [x] [y] .pathlength

按路径长度
if current_pathlength> best_pathlength:
continue
elif current_pathlength< best_pathlength:
debug_write(竞争者有更好的路径长度{} vs champs {}。format(current_pathlength ,best_pathlength))
new_best = True

根据prev move按方向过滤
如果 new_best self._better_direction(current_point,neighbor,ideal_neighbor,previous_move_direction, end_points):
continue

ideal_neighbor =邻居
best_pathlength = current_pathlength

debug_write(Gave unit at {} new tile {}。format(curre nt_point,ideal_neighbor))
return ideal_neighbor

def _better_direction(self,prev_tile,new_tile,prev_best,previous_move_direction,end_points):
比较两个如果单位宁愿转移到新单位,则返回True。


如果我们的移动方向不同于prev移动而且prev不是
如果我们之前移动了水平,现在我们的一个选项有不同的x位置,那么另一个(两个选项没有上/下)
if previous_move_direction == self.HORIZONTAL new_tile [ 0 ] == prev_best [ 0 ]:
我们现在想上去。如果我们没有改变我们的y,我们就不会上涨
如果 prev_tile [ 1 ] == new_tile [ 1 ]:
return 错误
返回
如果 previous_move_direction == self.VERTICAL new_tile [ 1 ] == prev_best [ 1 ]:
if prev_tile [ 0 ] == new_tile [ 0 ]:
< span class =code-comment># debug_write(contender {}与prev tile {}具有相同的x坐标,因此我们将保持最佳移动{}。格式(new_ti le,prev_tile,prev_best))
return False
< span class =code-keyword> return True
if previous_move_direction = = 0
如果 prev_tile [ 1 ] == new_tile [ 1 ]:
return 错误
返回 True

要在此处进行操作,两个移动都在同一轴上
direction = self。 _get_direction_from_endpoints(end_points)
如果 new_tile [ 1 ] == prev_best [ 1 ]: 如果他们都横向移动......
如果方向[ 0 ] == 1 new_tile [ 0 ]> prev_best [ 0 ]: 如果我们向右右移动是我们的方向,我们朝着我们的方向前进
return True
如果方向[ 0 ] == - 1 new_tile [ 0 ]< prev_best [ 0 ]: 如果我们向左和向左移动是我们的方向,我们朝着我们的方向前进
return True
返回 错误
如果 new_tile [ 0 ] == prev_best [ 0 ]: 如果它们都垂直移动......
如果方向[ 1 ] == 1 new_tile [ 1 ]> prev_best [ 1 ]: 如果我们向上和向上移动是我们的方向,我们朝着我们的方向前进
return True
如果方向[ 1 ] == - 1 new_tile [ 1 ]< prev_best [ 1 ]: 如果我们上下移动是我们的方向,我们朝着我们的方向前进
return True
返回 错误
返回 True

def print_map(self):
打印当前游戏地图的ASCII版本以用于调试目的


如果 self.initialized:
debug_write( 在路径查找器初始化之前尝试print_map。使用'this_object.initial ize_map(game_state)'首先初始化地图
return

for y 范围内( 28 ):
x 范围内( 28 ):
node = self.game_map [x] [ 28 - y - 1 ]
如果 node.blocked node.pathlength == - 1
self._print_justified(node.pathlength)
< span class =code-keyword> else

sys.stderr.write(
debug_write(

def _print_justified(self,number):
打印100到100之间的数字-10在3个空格中


如果数字< 10 数字> - 1
sys.stderr.write(
sys.stderr.write(str(number))
sys.stderr.write(





我尝试过: < br $>


我寻找机会使用列表理解等等,但这是我得到的。

解决方案

< blockquote>首先分析它并找出它花费大部分时间的地方 - 然后集中精力改进代码。一旦你对它进行了分析,你应该有一组数字告诉你它在不同的位上花了多少时间,重新运行分析器会告诉你有多少改进(否则,它也很容易倒退)你已经完成了。



但是我们不能为你做到这一点:你需要运行完整的数据代码以获得任何实质性的数字,我们有没有访问权限。每次进行更改,测试它仍然需要您的整个应用程序和数据。



不要指望这是一个简单的操作:性能改进一般来之不易而且复杂;可能需要相当长的时间才能获得良好的稳固改进。


I need to optimize a lot of code, is there anything I can do here?


<pre>import heapq
import math
import sys
import queue
from .util import debug_write

class Node:
    """A pathfinding node

    Attributes:
        * visited_idealness (bool): Have we visited this node during the idealness search step?
        * visited_validate (bool): Have we visited this node during the validation step?
        * blocked (bool): Is there a firewall at this node's location
        * pathlength: The distance between this node and the target location

    """
    def __init__(self):
        self.visited_idealness = False
        self.visited_validate = False
        self.blocked = False
        self.pathlength = -1

"""
This class helps with pathfinding. We guarentee the results will
be accurate, but top players may want to write their own pathfinding
code to maximise time efficiancy
"""
class ShortestPathFinder:
    """Handles pathfinding

    Attributes:
        * HORIZONTAL (int): A constant representing a horizontal movement
        * VERTICAL (int): A constant representing a vertical movement

        * game_state (:obj: GameState): The current gamestate
        * game_map (:obj: GameMap): The current gamemap

    """
    def __init__(self):
        self.HORIZONTAL = 1
        self.VERTICAL = 2
        self.initialized = False

    def initialize_map(self, game_state):
        """Initializes the map

        Args:
            * game_state: A GameState object representing the gamestate we want to 
        """
        #Initialize map 
        self.initialized = True
        self.game_state = game_state
        self.game_map = [[Node() for x in range(self.game_state.ARENA_SIZE)] for y in range(self.game_state.ARENA_SIZE)]

    def navigate_multiple_endpoints(self, start_point, end_points, game_state):
        """Finds the path a unit would take to reach a set of endpoints

        Args:
            * start_point: The starting location of the unit
            * end_points: The end points of the unit, should be a list of edge locations
            * game_state: The current game state

        Returns:
            The path a unit at start_point would take when trying to reach end_points given the current game state.
            Note that this path can change if a tower is destroyed during pathing, or if you or your enemy places firewalls.

        """
        if game_state.contains_stationary_unit(start_point):
            return

        #Initialize map 
        self.initialize_map(game_state)
        #Fill in walls
        for location in self.game_state.game_map:
            if self.game_state.contains_stationary_unit(location):
                self.game_map[location[0]][location[1]].blocked = True
        #Do pathfinding
        ideal_endpoints = self._idealness_search(start_point, end_points)
        self._validate(ideal_endpoints, end_points)
        return self._get_path(start_point, end_points)

    def _idealness_search(self, start, end_points):
        """
        Finds the most ideal tile in our 'pocket' of pathable space. 
        The edge if it is available, or the best self destruct location otherwise
        """
        current = queue.Queue()
        current.put(start)
        best_idealness = self._get_idealness(start, end_points)
        self.game_map[start[0]][start[1]].visited_idealness = True
        most_ideal = start

        while not current.empty():
            search_location = current.get()
            for neighbor in self._get_neighbors(search_location):
                if not self.game_state.game_map.in_arena_bounds(neighbor) or self.game_map[neighbor[0]][neighbor[1]].blocked:
                    continue

                x, y = neighbor
                current_idealness = self._get_idealness(neighbor, end_points)

                if current_idealness > best_idealness:
                    best_idealness = current_idealness
                    most_ideal = neighbor

                if not self.game_map[x][y].visited_idealness and not self.game_map[x][y].blocked:
                    self.game_map[x][y].visited_idealness = True
                    current.put(neighbor)

        return most_ideal

    def _get_neighbors(self, location):
        """Get the locations adjacent to a location
        """
        x, y = location
        return [[x, y + 1], [x, y - 1], [x + 1, y], [x - 1, y]]

    def _get_direction_from_endpoints(self, end_points):
        """Prints a message to the games debug output

        Args:
            * end_points: A set of endpoints, should be an edge 

        Returns:
            A direction [x,y] representing the edge. For example, [1,1] for the top right and [-1, 1] for the top left

        """
        point = end_points[0]
        x, y = point
        direction = [1, 1]
        if x < self.game_state.HALF_ARENA:
           direction[0] = -1
        if y < self.game_state.HALF_ARENA:
            direction[1] = -1
        return direction

    def _get_idealness(self, location, end_points):
        """Get the idealness of a tile, the reachable tile the unit most wants to path to.
        Better self destruct locations are more ideal. The endpoints are perfectly ideal. 

        Returns:
            A location the unit will attempt to reach
        """
        if location in end_points:
            return sys.maxsize

        direction = self._get_direction_from_endpoints(end_points)

        idealness = 0
        if direction[1] == 1:
            idealness += 28 * location[1]
        else: 
            idealness += 28 * (27 - location[1])
        if direction[0] == 1:
            idealness += location[0]
        else: 
            idealness += (27 - location[0])

        return idealness

    def _validate(self, ideal_tile, end_points):
        """Breadth first search of the grid, setting the pathlengths of each node

        """
        #VALDIATION
        #Add our most ideal tiles to current
        current = queue.Queue()
        if ideal_tile in end_points:
            for location in end_points:
               current.put(location)
               #Set current pathlength to 0
               self.game_map[location[0]][location[1]].pathlength = 0
               self.game_map[location[0]][location[1]].visited_validate = True
        else:
            current.put(ideal_tile)
            self.game_map[ideal_tile[0]][ideal_tile[1]].pathlength = 0
            self.game_map[ideal_tile[0]][ideal_tile[1]].visited_validate = True

        #While current is not empty
        while not current.empty():
            current_location = current.get()
            current_node = self.game_map[current_location[0]][current_location[1]]
            for neighbor in self._get_neighbors(current_location):
                if not self.game_state.game_map.in_arena_bounds(neighbor) or self.game_map[neighbor[0]][neighbor[1]].blocked:
                    continue

                neighbor_node = self.game_map[neighbor[0]][neighbor[1]]
                if not neighbor_node.visited_validate and not current_node.blocked:
                    neighbor_node.pathlength = current_node.pathlength + 1
                    neighbor_node.visited_validate = True
                    current.put(neighbor)

        #debug_write("Print after validate")
        #self.print_map()
        return

    def _get_path(self, start_point, end_points):
        """Once all nodes are validated, and a target is found, the unit can path to its target

        """
        #GET THE PATH
        path = [start_point]
        current = start_point
        move_direction = 0

        while not self.game_map[current[0]][current[1]].pathlength == 0:
            #debug_write("current tile {} has cost {}".format(current, self.game_map[current[0]][current[1]].pathlength))
            next_move = self._choose_next_move(current, move_direction, end_points)
            #debug_write(next_move)

            if current[0] == next_move[0]:
                move_direction = self.VERTICAL
            else:
                move_direction = self.HORIZONTAL
            path.append(next_move)
            current = next_move
        
        #debug_write(path)
        return path
  
    def _choose_next_move(self, current_point, previous_move_direction, end_points):
        """Given the current location and adjacent locations, return the best 'next step' for a given unit to take
        """
        neighbors = self._get_neighbors(current_point)
        #debug_write("Unit at {} previously moved {} and has these neighbors {}".format(current_point, previous_move_direction, neighbors))

        ideal_neighbor = current_point
        best_pathlength = self.game_map[current_point[0]][current_point[1]].pathlength
        for neighbor in neighbors:
            #debug_write("Comparing champ {} and contender {}".format(ideal_neighbor, neighbor))
            if not self.game_state.game_map.in_arena_bounds(neighbor) or self.game_map[neighbor[0]][neighbor[1]].blocked:
                continue

            new_best = False
            x, y = neighbor
            current_pathlength = self.game_map[x][y].pathlength

            #Filter by pathlength
            if current_pathlength > best_pathlength:
                continue
            elif current_pathlength < best_pathlength:
                #debug_write("Contender has better pathlength at {} vs champs {}".format(current_pathlength, best_pathlength))
                new_best = True

            #Filter by direction based on prev move
            if not new_best and not self._better_direction(current_point, neighbor, ideal_neighbor, previous_move_direction, end_points):
                continue

            ideal_neighbor = neighbor
            best_pathlength = current_pathlength

        #debug_write("Gave unit at {} new tile {}".format(current_point, ideal_neighbor))
        return ideal_neighbor

    def _better_direction(self, prev_tile, new_tile, prev_best, previous_move_direction, end_points):
        """Compare two tiles and return True if the unit would rather move to the new one

        """
        #True if we are moving in a different direction than prev move and prev is not
        #If we previously moved horizontal, and now one of our options has a different x position then the other (the two options are not up/down)
        if previous_move_direction == self.HORIZONTAL and not new_tile[0] == prev_best[0]:
            #We want to go up now. If we have not changed our y, we are not going up
            if prev_tile[1] == new_tile[1]:
                return False 
            return True
        if previous_move_direction == self.VERTICAL and not new_tile[1] == prev_best[1]:
            if prev_tile[0] == new_tile[0]:
                #debug_write("contender {} has the same x coord as prev tile {} so we will keep best move {}".format(new_tile, prev_tile, prev_best))
                return False
            return True
        if previous_move_direction == 0: 
            if prev_tile[1] == new_tile[1]: 
                return False
            return True
        
        #To make it here, both moves are on the same axis 
        direction = self._get_direction_from_endpoints(end_points)
        if new_tile[1] == prev_best[1]: #If they both moved horizontal...
            if direction[0] == 1 and new_tile[0] > prev_best[0]: #If we moved right and right is our direction, we moved towards our direction
                return True 
            if direction[0] == -1 and new_tile[0] < prev_best[0]: #If we moved left and left is our direction, we moved towards our direction
                return True 
            return False 
        if new_tile[0] == prev_best[0]: #If they both moved vertical...
            if direction[1] == 1 and new_tile[1] > prev_best[1]: #If we moved up and up is our direction, we moved towards our direction
                return True
            if direction[1] == -1 and new_tile[1] < prev_best[1]: #If we moved down and down is our direction, we moved towards our direction
                return True
            return False
        return True

    def print_map(self):
        """Prints an ASCII version of the current game map for debug purposes

        """
        if not self.initialized:
            debug_write("Attempted to print_map before pathfinder initialization. Use 'this_object.initialize_map(game_state)' to initialize the map first")
            return

        for y in range(28):
            for x in range(28):
                node = self.game_map[x][28 - y - 1]
                if not node.blocked and not node.pathlength == -1:
                    self._print_justified(node.pathlength)
                else:
                    sys.stderr.write("   ")
            debug_write("")

    def _print_justified(self, number):
        """Prints a number between 100 and -10 in 3 spaces

        """
        if number < 10 and number > -1:
            sys.stderr.write(" ")
        sys.stderr.write(str(number))
        sys.stderr.write(" ")



What I have tried:

I looked for oppurtunities to use list comprehension etc. but this is as far as I have gotten.

解决方案

Start by profiling it and finding out where it spend most of it's time - then concentrate your efforts on improving that code. Once you have profiled it, you should have a set of numbers which tell you how much time it is taking in its various bits, and re-running the profiler will tell you how much improvement (or otherwise, it's easy to go backwards as well as forwards) you have made.

But we can't do that for you: you need your code running complete with your data to get any substantive numbers and we have no access to that. And each time you make a change, to test it you still need your whole app and data.

Do not expect this to be a simple operation: performance improvements are generally hard-won and complicated; it can take considerable time to get a good solid improvement.


这篇关于我该如何优化这个Python代码?的文章就介绍到这了,希望我们推荐的答案对大家有所帮助,也希望大家多多支持IT屋!

查看全文
登录 关闭
扫码关注1秒登录
发送“验证码”获取 | 15天全站免登陆