Merkwürdiges Verhalten auf einer Liste mit 100000 Elementen

Question

Ich bin Standford Online-Kurs für Algorithmen Design beigetreten und jetzt löse ich die erste Programmierfrage.

The file enthält alles 100.000 ganze Zahlen zwischen 1 und 100.000 (einschließlich) in einer zufälligen Reihenfolge (keine ganze Zahl wiederholt wird). Ihre Aufgabe ist die Anzahl der Inversionen in der Datei zu finden (jede Zeile hat eine einzelne ganze Zahl zwischen 1 und 100.000). Angenommen, Ihr Array ist von 1 bis 100.000 und die i-te Zeile der Datei gibt Ihnen den i-ten Eintrag des Arrays.

Update: Ich habe festgestellt, dass mein Code nur für den 2^n Fall funktioniert. Problem ist im Code, nicht Python. Ich habe den Code aktualisiert, jetzt funktioniert es gut und ich habe das Quiz gemacht. Danke an alle die

Fest Code geholfen ist:

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] 

Dieses Programm arbeitet für kleinen Arrays in Ordnung, aber für die große Palette von der Frage, druckt er Array von Zahlen in der richtigen Reihenfolge, nicht 100000, wie ich es erwarte. Es lässt Zahlen an zufälligen Orten weg.

Was ist der Grund für dieses unerwartete Verhalten von Python?

Answer 1

Indem Sie n = len(a) setzen und nur n * 2 Mal zusammenführen, schneiden Sie b ab, wenn es länger als a ist.

Dies erklärt teilweise die auffällige Tatsache, dass Sie 2 ** 16 Elemente in der resultierenden Liste haben.