Plus efficace Python 3

Question

Je joue avec un problème à https://www.hackerrank.com/challenges/angry-children. J'ai écrit une solution qui résout correctement certains cas de test. D'autres cas de test, des cas qui fournissent beaucoup plus d'entrées, expirent. Comment puis-je changer ce code pour le traiter plus rapidement?

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) 

Answer 1

Les deux boucles initiales seront plus rapides si la boucle de la méthode est retirée de la boucle. Une compréhension de liste est également plus rapide. J'ai exécuté cette expérience

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() 

avec ces résultats.

0.48560521545219426 
0.3943799918166562 
0.4146867965037263 

0.372683063890642 
0.3126639858171769 
0.2900946187597775 

0.36497313668305287 
0.33567233916055894 
0.3071572902003692 

Je crois que cette somme

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

est juste ce qui sera plus rapide

temp_summed_diff = sum(D_set[D_start:D_end] 

Je ne vois pas d'autre speedups.

Answer 2

Votre algorithme de calcul de l'injustice minimale peut être grandement amélioré. Si votre liste est triée, alors l'iniquité de chaque sous-liste est juste la différence entre ses extrémités, donc tout se résume à trouver le minimum de cette différence pour toutes les sous-listes de longueur k.

Aussi, dans ce genre de situations, il est généralement plus rapide d'éviter input() et lire directement à partir de sys.stdin.

Tout ce problème peut être résolu en seulement 6 lignes de python:

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)