Инверсия счетчика в python (для большого целочисленного массива)

Question

Я делаю программу для инверсии count в pyhton и используя python27 для этого же. Я реализую alogorithm с использованием техники разделения и покорения (трюк сортировки слияния). Моя программа отлично работает для входного массива размером до 100 (это максимум, который я мог проверить). Теперь я проверил свою программу на входном массиве размером 50 000 и 1 000 000, но как бы я не смог получить правильные ответы. Я приклеил мой код ниже, любезно указать любую возможную ошибку:

f=open('forum.txt') 
    a=[] 
    s=1 
    for line in f: 
     a.append(line) 





def CountInversion(IntegerArray): 
_count=0 
lc=0 
rc=0 
RightArray=[] 
LeftArray=[] 
if len(IntegerArray)>1: 
     LeftArray,lc=CountInversion(IntegerArray[:len(IntegerArray)/2]) 
     RightArray,rc=CountInversion(IntegerArray[len(IntegerArray)/2:]) 
elif len(IntegerArray)==1: 
    return IntegerArray,0 
ResultArray=IntegerArray 
i=0 
l=len(ResultArray) 
j,k=0,0 
for i in range(0,l): 
    if j<len(RightArray) and k<len(LeftArray): 
     if RightArray[j]<LeftArray[k]: 
      ResultArray[i]=RightArray[j] 
      j += 1 
      a=(len(LeftArray)-k) 
      _count = _count + a  
     else: 
      ResultArray[i]=LeftArray[k] 
      k += 1 
elif j<len(RightArray): 
    ResultArray[i]=RightArray[j] 
     j += 1 
elif k<len(LeftArray): 
     ResultArray[i]=LeftArray[k] 
     k += 1   
return ResultArray,(_count+lc+rc) 

arr,b=CountInversion(a) 

print ('end of inversions') 

print b 

Я побежал код, данный JF Себастьяна в this посте, но результаты такие же (правильные ответы на небольшой вход, но не для ввода массив размером 50000 или 1 000 000)

Answer 1

Ваша первая проблема заключается в том, что у вас непоследовательный отступ. На нескольких строках вы используете вкладки вместо пробелов, что очень плохая идея. Отступы значительны для Python, поэтому легко сделать ошибки, если вы не смотрите.

Вторая проблема, которая, как я думаю, у вас есть, заключается в том, что вы сравниваете строки, а не цифры. Python с удовольствием сортирует строки, но будет использовать лексикографическое оверсирование, что может быть неожиданным при применении к целым числам, закодированным как строки. Например, строка "11" будет сортироваться перед строкой "2", так как ее первый символ 1 предшествует 2 в наборе символов ASCII (а также в Юникоде).

Как я уже сказал в комментарии, неясно, как вы определяете, что ваш код работает некорректно. Возможно, что исправление проблем, описанных выше, поможет устранить проблемы, которые у вас возникают. Если они этого не сделают, объясните, как вы определяете, что ваши результаты недействительны, и я попытаюсь обновить этот пост с дальнейшими предложениями.

Answer 2

Задача решается путем разбора строки в Int и заполнения массива