更高效的Python 3

-1

我在https://www.hackerrank.com/challenges/angry-children处玩弄一个问题。我已经编写了正确解决一些测试用例的解决方案。其他测试用例，提供更多输入，超时的情况。我如何更改此代码以更快处理？更高效的Python 3

N = int(input()) 
K = int(input()) 
D = K - 1 
N_set = [] 
for n in range(N): 
    N_set.append(int(input())) 
N_set.sort(reverse=True) 

#Find differences between each integer in the list 
D_set = [] 
for d in range(0,N-1): 
    D_set.append(N_set[d]-N_set[d+1]) 

D_Start = 0 
D_End = D 
min_summed_diff = 99999999999999 
D_Start_Hold = None 
D_End_Hold = None 

count_down = len(D_set) - D + 1 
while count_down: 
    #print(count_down) 
    temp_summed_diff = 0 
    for i in range(D_Start, D_End): 
     temp_summed_diff += D_set[i] 

    if temp_summed_diff < min_summed_diff: 
     min_summed_diff = temp_summed_diff 
     D_Start_Hold = D_Start 
     D_End_Hold = D_End 

    D_Start += 1 
    D_End += 1 
    count_down -= 1 

K_set = N_set[D_Start_Hold:D_End_Hold+1] 
unfairness = max(K_set) - min(K_set) 
print(unfairness)

来源

2015-03-13 Cam

运行一下，看看伸出？ – Kevin 2015-03-13 20:09:32

两个初始循环会更快是方法loopup退出循环。列表理解也更快。我跑了这个实验

from timeit import timeit 

a = '''\ 
tem = [] 
for i in range(%d): 
    tem.append(int('1000')) 
''' 

b = '''\ 
tem = [] 
temapp = tem.append 
for i in range(%d): 
    temapp(int('1000')) 
''' 

c = "tem = [int('1000') for i in range(%d)]" 

for n in (10,1000, 1000000): 
    number = 1000000 // n 
    print(timeit(a%n, number = number)) 
    print(timeit(b%n, number = number)) 
    print(timeit(c%n, number = number)) 
    print()

与这些结果。

0.48560521545219426 
0.3943799918166562 
0.4146867965037263 

0.372683063890642 
0.3126639858171769 
0.2900946187597775 

0.36497313668305287 
0.33567233916055894 
0.3071572902003692

我相信这笔

temp_summed_diff = 0 
    for i in range(D_Start, D_End): 
     temp_summed_diff += D_set[i]

就是这样，这将是更快

temp_summed_diff = sum(D_set[D_start:D_end]

我没有看到任何其他的加速。

来源

2015-03-13 21:35:12

如果你的代码是正确的，并且hackerrank不会将Python的最大允许运行时间乘以至少20，那么我将继续前进。 Python的设计是为了尽量减少（昂贵的）程序员时间，而不是（便宜的）机器时间。 – 2015-03-13 21:38:39

您的计算最小不公平度的算法可以大大提高。

如果您的清单是排序的，那么每个子清单的不公平性就是它的两端之间的差异，所以它归结为找出所有长度为k的子清单的差异的最小值。

而且，在这种情况下，它通常会更快地避免input()并直接从sys.stdin中读取。

这整个问题可以在短短6行蟒蛇来解决：在'cProfile`

import sys 
nrs = map(int, sys.stdin) 
n, k = next(nrs), next(nrs) 
nrs = sorted(nrs) 
min_unfair = min(nrs[k+i-1] - nrs[i] for i in range(0, len(nrs)-k+1)) 
print(min_unfair)

来源

2015-03-13 22:23:15 mata

更高效的Python 3

回答

相关问题