1

MergeSort を使用してファイルから反転をカウントしようとしています。私のコードは小さなファイルでは機能するようですが、大きなファイルでは間違った出力が生成されます。私のコード:

InversionCount.py:

count = 0

def merge_sort_inversions(numberlist):
    if len(numberlist) < 2:
        return numberlist
    else:
        mid = len(numberlist) // 2
        lefthalf = numberlist[:mid]
        righthalf = numberlist[mid:]

    return sort_count_inversions(merge_sort_inversions(lefthalf), merge_sort_inversions(righthalf))

def sort_count_inversions(l, r):
    result = []

    i=0
    j=0

    global count

    while(i < len(l) and j<len(r)):
        if (r[j] > l[i]):
            result.append(l[i])
            i+= 1
        elif(r[j] < l[i]):
            result.append(r[j])
            count += (len(l) - i)
            j+=1
    if(j>=len(r)):
        result+=l
    elif(i>=len(l)):
        result+=r

    print(count)
    return result

アプリケーション.py:

import InversionCount

text_file = open('algorithms-1-test2.txt', 'r')
number_list = text_file.readlines()
number_list = list(map(int, number_list))

InversionCount.merge_sort_inversions(number_list)

答えは 2407905288 ですが、最終的に表示されるカウントは 22945388587258 です。自分でアルゴリズムを学ぼうとしているので、これについて何か助けていただければ幸いです。また、私の問題は大きなファイルで発生するので、非常に大きな入力でのみ発生するように見える問題をデバッグするにはどうすればよいですか (これを小さな入力でテストしてみましたが、正しい答えが得られます)。ありがとうございました！

4

0 に答える 0