如何改進我的代碼以處理大量數據？

Question

我正在做一個hackerrank挑戰計數倒數，但我無法通過幾個測試用例，因爲它說超時。我在我的系統上運行測試用例，大約需要10秒才能得到正確的結果。

下面是代碼：

def merge_sort_inversion(listA): 
    n=len(listA) 
    if n==1 or n==0: 
    return listA,0 

    left_subArray=listA[:n/2] 
    right_subArray=listA[n/2:] 

    left_subArray, left_inversion=merge_sort_inversion(left_subArray) 
    right_subArray,right_inversion=merge_sort_inversion(right_subArray) 
    sorted_list, split_inversion=merge_inversion(left_subArray,right_subArray) 


    return sorted_list,left_inversion+right_inversion+split_inversion 
#sorted_list=[] 
def merge_inversion(left,right): 
    sorted_list=[] 
    count=0 
    if len(left)==0 or len(right)==0: 
    return left+right,0 

    i=0 
    j=0 
    for k in range(len(left)+len(right)): 
    if len(left)!=i and len(right)!=j: 
     if left[i]>right[j]: 
     sorted_list.append(right[j]) 
     count=count+len(left[i:]) 
     #print right[j], left[i:],count 
     j=j+1 
     else: 
     sorted_list.append(left[i]) 
     i=i+1 
    elif len(left)==i: 
     return sorted_list+right[j:],count 
    elif len(right)==j: 
     return sorted_list+left[i:],count 
    return sorted_list,count 

t = int(raw_input().strip()) 
for a0 in xrange(t): 
    n = int(raw_input().strip()) 
    arr = map(int, raw_input().strip().split(' ')) 
    a,b=merge_sort_inversion(arr) 
    print b 

可有人請指教？

Answer 1

這條線是非常緩慢：

count=count+len(left[i:]) 

，因爲它產生的所有元素從位置留給我向上的新名單。

由於只需要得到的長度，就可以做到這一點通過快得多：

count += len(left) - i 

在我的電腦這降低了時間與來自7.5秒100000個元件到0.5秒的陣列。