Подсчет Инверсии для большого текстового файла

Question

Целью кода является выяснение общего количества нет. инверсий для массива. Мой код успешно работает. Успешно протестировано для 6 элементов (все элементы в обратном порядке, начиная с самого высокого) с количеством инверсий = 15. Кроме того, успешно протестировано для 10 элементов (все элементы в обратном порядке, начиная с самого высокого) с количеством инверсий = 45 Однако для большого файл, содержащий 100 000 целых чисел, занимает почти 25 секунд. Это ожидается? Пожалуйста, предложите или я могу еще больше сократить время выполнения? Я только что сделал небольшую настройку в обычном алгоритме сортировки слиянием (то есть в строке для подсчета общего числа инверсий). Как я могу еще больше сократить общее время выполнения?

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

Я нашел это (и проверил с профилем)

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

left_half [i:] создает новый список с копией нескольких элементов, много раз, в главном цикле вашей рекурсивной функции. Это было умное использование сращивания, но побочные эффекты убивают вашу производительность.

Вот как я разбил функцию, чтобы профилировать ее:

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)

и результаты показывают, что он потратил 19,574 секунды на получение len(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}