Zählinversion für eine große Textdatei

Question

Das Ziel des Codes ist es, die Gesamtanzahl zu ermitteln. von Inversionen für ein Array. Mein Code funktioniert erfolgreich. Getestet erfolgreich für 6 Elemente (alle Elemente in umgekehrter Reihenfolge beginnend mit der höchsten) mit Inversionszählung = 15. Auch erfolgreich getestet für 10 Elemente (alle Elemente in umgekehrter Reihenfolge beginnend mit der höchsten) mit Inversionszählung = 45 eine große Datei mit 100k Ganzzahlen, dauert es fast 25 Sekunden. Wird das erwartet? Bitte vorschlagen oder kann ich die Ausführungszeit weiter senken? Ich habe gerade einen kleinen Tweak im konventionellen Merge-Sort-Algorithmus gemacht (d. H. Die Linie, um die Gesamtzahl der Inversionen zu zählen) Wie kann ich die Gesamtlaufzeit weiter reduzieren?

def mergeSort(final_list): 
    global total_count 
    if len(final_list)>1: 
     mid_no=len(final_list)//2 
     left_half=final_list[:mid_no] 
     right_half=final_list[mid_no:] 

     mergeSort(left_half) 
     mergeSort(right_half)  

     '''Below code is for merging the lists''' 
     i=j=k=0 #i is index for left half, j for the right half and k for the resultant list 
     while i<len(left_half) and j<len(right_half): 
      if left_half[i] < right_half[j]: 
       final_list[k]=left_half[i] 
       i+=1 
       k+=1 

      else: 
       final_list[k]=right_half[j] 

       print 'total count is' 
       print total_count 
       #total_count+=len(left_half)-i 
       total_count+=len(left_half[i:]) 
       print 'total_count is ' 
       print total_count 

       print 'pairs are ' 
       print str(left_half[i:])+' with '+str(right_half[j]) 
       j+=1 
       k+=1 




     while i<len(left_half): 
      final_list[k]=left_half[i] 
      k+=1 
      i+=1 
     while j<len(right_half): 
      final_list[k]=right_half[j] 
      j+=1 
      k+=1 

     '''Code for list merge ends''' 

#temp_list=[45,21,23,4,65] 
#temp_list=[1,5,2,3,4,6] 
#temp_list=[6,5,4,3,2,1] 
#temp_list=[1,2,3,4,5,6] 
#temp_list=[10,9,8,7,6,5,4,3,2,1] 
#temp_list=[1,22,3,4,66,7] 
temp_list=[] 
f=open('temp_list.txt','r') 
for line in f: 
    temp_list.append(int(line.strip())) 

print 'list is ' 
print temp_list 
print 'list ends' 
print temp_list[0] 
print temp_list[-1] 
'''import time 
time.sleep(1000) 
print 'hhhhhhhhhh' 
''' 



total_count=0 
mergeSort(temp_list) 

print temp_list 

Answer 1

Ich fand es (und mit Profil verifiziert)

 #total_count+=len(left_half[i:]) 
     total_count += len(left_half) - i 

left_half [i:] erstellt eine neue Liste mit einer Kopie von mehreren Elementen, viele Male, in der Hauptschleife der rekursiven Funktion . Es war ein cleverer Einsatz von Spleißen, aber die Nebenwirkungen bringen Ihre Leistung zum Erliegen.

Hier ist, wie ich die Funktion brach es zum Profil:

def so_merge (final_list, left_half, right_half): 
    global total_count 
    i=j=k=0 #i is index for left half, j for the right half and k for the resultant list 
    while i<len(left_half) and j<len(right_half): 
     if left_half[i] < right_half[j]: 
      final_list[k]=left_half[i] 
      i+=1 
      k+=1 
     else: 
      final_list[k]=right_half[j] 
      count1 = get_incriment_bad(left_half, i) 
      count2 = get_incriment_good(left_half, i) 
      if count1 != count2: 
       raise ValueError 
      total_count += count1 
      j+=1 
      k+=1 
    finish_left(final_list, left_half, i, k) 
    finish_right(final_list, right_half, j, k) 

und die Ergebnisse zeigen, dass es 19,574 Sekunden verbrachte len bekommen (left_half [i:])

ncalls tottime percall cumtime percall filename:lineno(function) 
199999/1 0.805 0.000 29.562 29.562 week1.py:124(so_mergesort) 
99999 7.496 0.000 28.735 0.000 week1.py:104(so_merge) 
776644 19.512 0.000 19.574 0.000 week1.py:101(get_incriment_bad) 
776644 0.839 0.000 0.895 0.000 week1.py:98(get_incriment_good) 
5403164 0.382 0.000 0.382 0.000 {len} 
99999 0.273 0.000 0.286 0.000 week1.py:92(finish_right) 
99999 0.255 0.000 0.266 0.000 week1.py:86(finish_left) 
    1 0.000 0.000 0.000 0.000 {method 'disable' of '_lsprof.Profiler' objects}