コードの現在のアルゴリズムをO（n + m + k）とすると、どのように最適化できますか？

Question

私は3つの配列h1, h2, h3を持っています。

n1, n2,n3は、配列の長さを決定します。

すべての配列の最終的な合計が同じになるように、1つ以上の配列から入力を削除する必要があります。

###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 

我々は、上記の配列

sum of h1 = 8 sum of h2 = 9 sum of h3 = 7 配列の先頭からdeletion should happenに表示された場合。 だからここに私が削除した場合、 3 from h1 (as h1[0]) 4 from h2 (as h2[0]) 1 and 1 from h3 (as h3[0] and h3[1]) 今、すべての(Sum of h1 containts, h2 containts, h3 containts)合計が5になります。これは私の最終的な答えです。 以下のコードは、入力リストが小さい場合にうまく機能します。しかし、入力リストがn1 = 100000, n2 = 200000, n3 = 300000になると。このコードでは、実行に多くの時間がかかります。どうすれば時間を短縮できますか？ Pythonのリストの先頭から削除

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

Pythonは（1つのスペースをそれらを動かす）、新しいインデックスに他のすべての項目への参照をコピーする必要があるため（O(N)）遅いです。対照的に、リストの最後からの削除は速く（O(1)）、ただ1つの参照を削除してサイズを調整するためです。

アルゴリズムのパフォーマンスを向上させるには、最初に削除する項目が最後になるように、逆のリストを使用することをおすすめします。リストの理解の中でreversed関数を使用してそれらを取り消すことができます。または、リストの作成後にlist.reverseメソッドを使用することができます。あなたのアルゴリズムが終わったら、もう一度やり直すことで、それらを期待どおりの順序に戻すことができます。

また、（それは削除する項目のリストを検索する必要があるので）、後者はまだ終わりで遅くなりますように、というよりも、list.removelist.popまたはdel some_list[-1]を使用する必要があります。

私はそれがあなたのパフォーマンスを大きく損なうとは思わないが、非常に繰り返しの多いコードもたくさんある。これを見ると変数に数値が含まれていると、ほとんどの場合、独立変数ではなくインデックス可能なデータ構造を使用してコードを単純化できます。リストのリスト（およびその合計のリスト）を使用して問題を解決する方法は次のとおりです。

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)