100000個の要素を持つリストの不思議な振る舞い

Question

私はスタンフォードのオンラインコースに参加しました。今は最初のプログラミングの問題を解決しています。

fileは、いくつかのランダムな順序（非整数が繰り返されていない）に（両方を含む）1 100,000 間のすべて10万整数を含みます。 の作業では、与えられたファイル内の反転の数を見つけることです（すべての行 は1から100,000の間の単一の整数を持ちます）。あなたの配列は から1万から100,000であり、ファイルのi番目の行は 配列のi番目のエントリを与えるものとします。

更新：私のコードは2^nのケースでのみ動作することが判明しました。 Pythonではなく、コードに問題があります。私はコードを更新しましたが、今は正常に動作していますし、クイズを完了しました。を助けたすべての人のおかげで

固定コードです：

def merge_count_split (a, b): 
     c = [] 
     inv = 0 
     i=0 
     j=0 
     for k in range(len(a) + len(b)): 
       if i < len(a) and j < len(b): 
         if a[i] < b[j]: 
           c.append(a[i]) 
           i += 1 
         elif a[i] > b[j]: 
           c.append(b[j]) 
           inv += len(a)-i 
           j += 1 
       elif i == len(a): 
         c.append(b[j]) 
         j += 1 
       elif j == len(b): 
         c.append(a[i]) 
         i += 1 
     return c, inv 

def count_inv (data): 
     n = len(data) 
     if n == 1: 
       return data, 0 
     a, x = count_inv(data[:n/2]) 
     b, y = count_inv(data[n/2:]) 
     c, z = merge_count_split(a,b) 
     return c, x + y + z 

with open('IntegerArray.txt') as f: 
     array = [int(line) for line in f] 
     print count_inv(array)[0] 

このプログラムは、小さな配列のために正常に動作しますが、質問からの大規模な配列のためには、適切な順序で数字の配列を印刷しません100000、私が期待しています。ランダムな場所で数字を省略します。

この予期しない動作の理由は何ですか？

Answer 1

n = len(a)を設定し、n * 2回だけをマージすると、aより長い場合はbが切り捨てられます。

これは、結果リストに2 ** 16の項目があるという顕著な事実を部分的に説明しています。