如何在Python中创建超过最大大小的列表

Question

根据这个链接，在32位系统上，Python列表的最大大小是536,870,912个元素。

有没有办法初始化一个比这个更大的列表呢？

假设：

list1 = [None]*1000000000

Answer 1

这么大的列表会占用大量空间，因为列表中的每个元素至少需要4个字节。所以，如果你有一个最大元素数量的列表，光是这个列表就至少要占用2GB的内存¹。而且这还不算64位系统²。

1. 4 * 5.4e+8 = 2.1e+9，也就是2.1 GB
2. 8 * 1.2e+18 = 9.2e+18，也就是9.2 EB（没错，是艾字节）

不过，为了讨论这个问题，我们假设你有很多内存。

---

一个最简单的办法就是自己创建一个对象来存放和处理这个巨大的列表。基本上就是把这个大列表分成几个小列表，然后在需要的时候按需访问它们。因为list的子类化没有什么实际好处^{这里有解释}，因为你无论如何都得重写所有的方法，所以不如直接继承object，然后再进行扩展。这里最重要的是不要把子列表合并或复制（因为它们太大了），所以在需要的时候可以使用itertools.chain来遍历这些列表。

下面是一些最简单的列表方法append、extend、get/setitem的示例：

import sys
from itertools import chain

class largeList(object):
    def __init__(self, mylist=None):
        self.maxSize = sys.maxsize/4
        self.src = [[]]
        self.extend(mylist if mylist is not None else [])

    def __iter__(self):
        return chain(*self.src)

    def __getitem__(self, idx):
        return self.src[int(idx/self.maxSize)][idx%self.maxSize]

    def __setitem__(self, idx, item):
        self.src[int(idx/self.maxSize)][idx%self.maxSize] = item
        # expand set/getitem to support negative indexing.

    def append(self, item):
        if len(self.src[-1]) < self.maxSize:
            self.src[-1].append(item)
        else:
            self.src.append([item])
    
    def extend(self, items):
        remainder = self.maxSize - len(self.src[-1])
        self.src[-1].extend(items[:remainder])
        for i in xrange(0, len(items[remainder:]), self.maxSize):
            self.src.append(items[remainder:][i:i+self.maxSize])

    def __len__(self):
        return sum(len(l) for l in self.src)
    
    def __str__(self):
        size = self.__len__()
        if size >= 8:
            first, last = [], []
            for i, ele in enumerate(self.__iter__()):
                if i < 3:
                    first.append(ele)
                if i >= size - 3:
                    last.append(ele)
            return str(first)[:-1] + ', ..., ' + str(last)[1:]
        return str(list(self.__iter__()))

示例使用（如果你的可用内存少于4GB，或者你在64位系统上，请在尝试之前更改sys.maxsize！）：

#sys.maxsize = 1000

list1 = largeList(xrange(sys.maxsize/4 + 2))
print len(list1)
# 53687093
print list1
#[0, 1, 2, ..., 536870910, 536870911, 536870912]
print list1.src
#[[0, 1, 2 ..., 536870910], [536870911, 536870912]]
list1.extend([42, 43])
print list1
#[0, 1, 2, ..., 536870912, 42, 43]

结果是：在内部，这些列表被分成了多个列表，而在使用时它们看起来就像一个列表。更多的list功能可以通过添加更多的方法轻松实现。例如：pop、remove、insert和index：

(...)

    def pop(self, idx):
        listidx = int(idx/self.maxSize)
        itempopped = self.src[listidx].pop(idx%self.maxSize)
        for i in xrange(listidx, len(self.src)-1):
            self.src[i].append(self.src[i+1].pop(0))
        if not self.src[-1]:
            del self.src[-1]
        return itempopped
        
    def remove(self, item):
        for i, ele in enumerate(self.__iter__()):
            if ele == item:
                self.pop(i)
                break
    
    def insert(self, idx, item):
        listidx = int(idx/self.maxSize)
        itemtoshift = self.src[listidx].pop(-1)
        self.src[listidx].insert(idx%self.maxSize, item)
        for i in xrange(listidx+1, len(self.src)-1):
            itemremoved = self.src[i].pop(-1)
            self.src[i].insert(0, itemtoshift)
            itemtoshift = itemremoved
        if len(self.src[-1]) < self.maxSize:
            self.src[-1].insert(0, itemtoshift)
        else:
            self.src.append([self.src[-1].pop(-1)])
            self.src[-2].insert(0, itemtoshift)
    
    def index(self, item):
        for i, ele in enumerate(self.__iter__()):
            if ele == item:
                return i
        return -1

示例使用，继续：

#sys.maxsize = 1000

list1 = largeList(xrange(sys.maxsize/4 + 2))
list1.insert(0, 'a')
print list1
#['a', 0, 1, ..., 536870910, 536870911, 536870912]
list1.pop(2)
#1
list1.remove(536870910)
print list1.index('a')
#0
print len(list1)
#536870911
print list1
#['a', 0, 2, ..., 536870909, 536870911, 536870912]
print list.src
#[['a', 0, 2, ..., 536870909, 536870911], [536870912]]