更高效的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

回答

相關問題