大きな数値を処理するためにコードを改善するにはどうすればよいですか？

Question

私は逆転をカウントするためにハッカーの挑戦をしていますが、タイムアウトと言ってもほとんどテストケースに合格できません。私は自分のシステムでテストケースを実行し、正しい結果を得るには約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 

これは0.5秒まで7.5秒〜100,000の要素を持つ配列のための時間を短縮できます。