优化python代码,减少分配/释放时间
我试图从某个网站解决编程挑战问题,我不想在这里提及.
问题如下:
给出了整数N,S,M,初始板配置也是如此. 我很确定我的解决方案是正确的,可以通过归纳证明.我将电路板转换为图形(邻接列表),其中点之间的边缘使得有效的昆虫跳跃.然后它只需要迭代M次并更新路径计数. 我主要担心的是代码需要进行优化,以便它可以在多个测试用例上工作,而无需分配/解除分配太多次,这会减慢运行时间.如果有人能在算法本身内建议优化,那也很棒. 谢谢! import sys #The board on which Jumping insect moves. #The max size in any test case is 200 * 200 board = [['_']*200 for j in xrange(200)] #Graph in the form of an adjancency list created from the board G = [list() for i in xrange(200*200)] def paths(N,S): '''Calculates the total number of paths insect takes The board size is N*N,Length of paths: M,Insect can jusp from square u to square v if ||u-v|| <=S Here ||u-v|| refers to the 1 norm''' # Totals paths are modulo 1000000007 MOD = 1000000007 # Clearing adjacency list for this testcase for i in xrange(N*N): del(G[i][:]) s = -1 #Starting point s #Creating G adjacency list # Point 'L' represents starting point # Point 'P' cannot be accessed by the insect for u in xrange(N*N): x1,y1 = u/N,u%N if board[x1][y1] == 'L': s = u elif board[x1][y1] == 'P': continue for j in xrange(S+1): for k in xrange(S+1-j): x2,y2 = x1+j,y1+k if x2 < N and y2 < N and not board[x2][y2] == 'P': v = x2*N+y2 G[u].append(v) if not u == v: G[v].append(u) if j > 0 and k > 0: x2,y1-k if x2 < N and y2 >= 0 and not board[x2][y2] == 'P': v = x2*N+y2 G[u].append(v) G[v].append(u) # P stores path counts P = [[0 for i in xrange(N*N)] for j in xrange(2)] # Setting count for starting position to 1 P[0][s] = 1 # Using shifter to toggle between prev and curr paths shifter,prev,curr = 0,0 # Calculating paths for i in xrange(M): prev,curr = shifter %2,(shifter+1)%2 #Clearing Path counts on curr for i in xrange(N*N): P[curr][i] = 0 for u in xrange(N*N): if P[prev][u] == 0: continue for v in G[u]: P[curr][v] = (P[curr][v]+P[prev][u]) % MOD shifter = (shifter+1)%2 return (sum(P[curr])%MOD) #Number of testcases num = int(sys.stdin.readline().split()[0]) results = [] # Reading in test cases for i in xrange(num): N,S = [int(j) for j in sys.stdin.readline().split()] for j in xrange(N): board[j][:N] = list(sys.stdin.readline().split()[0]) results.append(paths(N,S)) for result in results: print result 解决方法
这是numpy有用的东西,尽管你可以通过使用数组和结构模块来管理这个特定的用例.
(编辑:李大同) 【声明】本站内容均来自网络,其相关言论仅代表作者个人观点,不代表本站立场。若无意侵犯到您的权利,请及时与联系站长删除相关内容! |