python - 包含 100000 个元素的列表上的奇怪行为

Question

我已经参加了斯坦福大学算法设计在线类(class)，现在我正在解决第一个编程问题。

The file contains all the 100,000 integers between 1 and 100,000 (including both) in some random order(no integer is repeated). Your task is to find the number of inversions in the file given (every row has a single integer between 1 and 100,000). Assume your array is from 1 to 100,000 and i-th row of the file gives you the i-th entry of the array.

更新:我发现我的代码仅适用于 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]

这个程序对于小数组工作得很好，但是对于问题中的大数组，它以正确的顺序打印 65536 数字的数组，而不是我所期望的 100000。它在随机位置省略数字。

Python 出现这种意外行为的原因是什么？

Answer 1

通过设置n = len(a)仅合并n * 2次，你截断b如果它长于a 。

这部分解释了一个惊人的事实:结果列表中有 2 ** 16 个项目。