Wie kann ich den Code aktuellen Algorithmus optimieren O (n + m + k)?

Question

Ich habe drei Arrays, h1, h2, h3.

Die n1, n2,n3 entscheidet über die Länge des Arrays.

Ich muss Eingaben von 1 oder mehr Arrays löschen, so dass die endgültige Summe aller Arrays gleich sein soll.

###Inputs 
n1,n2, n3 = 5, 3, 4 
h1 = 3 2 1 1 1 # 5 elements 
h2 = 4 3 2  # 3 elements 
h3 = 1 1 4 1 # 4 elements 

Wenn wir in der obigen Anordnung sehen

sum of h1 = 8 sum of h2 = 9 sum of h3 = 7 Die deletion should happen vom Anfang des Arrays. Also hier wenn ich löschen, 3 from h1 (as h1[0]) 4 from h2 (as h2[0]) 1 and 1 from h3 (as h3[0] and h3[1]) Nun sind alle (Sum of h1 containts, h2 containts, h3 containts) die Summe wird 5 werden. Das ist meine letzte Antwort. Der folgende Code funktioniert gut, wenn die Eingabelisten klein sind. Aber wenn die Eingabeliste n1 = 100000, n2 = 200000, n3 = 300000 geht. Dieser Code benötigt viel Zeit für die Ausführung. Wie kann ich die Zeit reduzieren?

from collections import * 
n1,n2,n3 = input().strip().split(' ') 
n1,n2,n3 = [int(n1),int(n2),int(n3)] 
h1 = [int(h1_temp) for h1_temp in input().strip().split(' ')] 
h2 = [int(h2_temp) for h2_temp in input().strip().split(' ')] 
h3 = [int(h3_temp) for h3_temp in input().strip().split(' ')] 
#print(n1, n2, n3, h1, h2, h3) 
h1_tot, h2_tot, h3_tot = sum(h1), sum(h2), sum(h3) 
#print(h1_tot, h2_tot, h3_tot) 
arr = [h1_tot, h2_tot, h3_tot] 
done = False 
while len(Counter(arr)) != 1: 
    if len(Counter(arr)) == 3: 
     if arr.index(min(Counter(arr))) == 0: 
      h3.remove(h3[0]) 
      h2.remove(h2[0]) 
     elif arr.index(min(Counter(arr))) == 1: 
      h3.remove(h3[0]) 
      h1.remove(h1[0]) 
     else: 
      h1.remove(h1[0]) 
      h2.remove(h2[0]) 
    if len(Counter(arr)) == 2: 
     index = arr.index(min(arr)) 
     if arr[0] == arr[1] and index == 2: 
      h1.remove(h1[0]) 
      h2.remove(h2[0]) 
     elif arr[1] == arr[2] and index == 0: 
      h2.remove(h2[0]) 
      h3.remove(h3[0]) 
     elif arr[0] == arr[2] and index == 1: 
      h1.remove(h1[0]) 
      h3.remove(h3[0]) 
     if arr[0] == arr[1] and (index == 0 or index == 1): 
      h3.remove(h3[0]) 
     elif arr[1] == arr[2] and (index == 2 or index == 1): 
      h1.remove(h1[0]) 
     elif arr[0] == arr[2] and (index == 0 or index == 2): 
      h2.remove(h2[0]) 

    h1_tot, h2_tot, h3_tot = sum(h1), sum(h2), sum(h3) 

    arr = [h1_tot, h2_tot, h3_tot] 



print(arr[0]) 

Answer 1

von Anfang an einer Python-Liste löschen ist langsam (O(N)), weil Python die Verweise auf alle anderen Elemente in einen neuen Index kopieren muss (bewegte sie einen Platz nach oben). Im Gegensatz dazu ist das Löschen am Ende einer Liste schnell (O(1)), da nur eine Referenz gelöscht und die Größe angepasst wird.

Um die Leistung Ihres Algorithmus zu verbessern, würde ich vorschlagen, mit umgekehrten Listen zu arbeiten, so dass die Elemente, die Sie zuerst entfernen, am Ende sind. Sie können sie mit der reversed-Funktion in Ihrem Listenverständnis umkehren oder die Methode list.reverse verwenden, nachdem die Listen erstellt wurden. Sobald Sie mit Ihrem Algorithmus fertig sind, können Sie ihn wieder in die erwartete Reihenfolge bringen, indem Sie ihn erneut umkehren.

Sie werden auch list.pop oder del some_list[-1] verwenden müssen, anstatt list.remove, da diese noch am Ende langsam sein (da es durch die Liste suchen, muss für das Element zu entfernen).

Während ich glaube nicht, dass es Ihre Leistung sehr verletzt, haben Sie auch eine Menge von sehr repetitiven Code. Wenn Sie das sehen und Variablen mit Zahlen darin haben, ist es fast immer ein Zeichen, dass Sie Ihren Code viel vereinfachen können, indem Sie eine indexierbare Datenstruktur anstelle von unabhängigen Variablen verwenden. Hier ist, wie ich Ihr Problem mit einer Liste von Listen (und eine Liste ihrer Summen, für ein gutes Maß) lösen würde:

lengths = [int(x) for x in input().split()] # this is ignored by the rest of the code 

values = [[int(x) for x in reversed(input().split())] for _ in range(3)] # make a list of 
sums = [sum(v) for v in values]           # reversed lists 

while not sums[0] == sums[1] == sums[2]: # if there wasn't a fixed number of lists, I'd use 
    max_sum = max(sums)     # something like "if max(sums) == min(sums)" 
    for i, (v, s) in enumerate(zip(values, sums)): # this loop over the lists lets us avoid 
     if s == max_sum:       # duplicating our code for each one 
      sums[i] -= v.pop(-1) # pop is fast at the end! 

for v in values: # I'm not sure what the desired output is, so I'm just printing the lists. 
    v.reverse() # Could instead use print(*reversed(v)) for formatting like in the input. 
    print(v)