python 减少内存占用的递归收益

Question

我有一个像下面这样的函数，它递归地将一个大数组分成两个子数组，并收集所有子数组以供将来处理。我的问题是有没有办法在拆分过程中产生子数组以减少内存占用，例如split调用的数组很大，~50G。

def split(array, subarrays):
    n = len(array)
    if n == 1:
        return
    else:
        i = n / 2
        subarray1 = array[:i]
        subarrays.append(subarray1)
        subarray2 = array[i:]
        subarrays.append(subarray2)
        split(subarray1, subarrays)
        split(subarray2, subarrays)
        return 

subarrays = []
# In production, range(10) will be replaced with a huge array, e.g. 50G
split(range(10), subarrays)
for i in subarrays:
    print i
    # do some other stuff with each subarray

Answer 1

这实际上会增加内存占用。每次对列表进行切片时，除了旧列表之外，您还会得到一个新列表。

例如：

l = [1, 2, 3, 4]  # great, we have 4 references to objects in this list
l2 = l[:2]        # ok, now we have an additional list with 2 more references

您真正想做的是分块读取原始数据。

Answer 2

我不确定你想在这里实现什么。是的，您可以使用 yield 到 return 一个一个地排列子数组。但它们不会按排序顺序排列，拆分过程仍会大致使您的内存使用量增加一倍。但我想这比将它增加 35 倍要好，这是在 50G 列表上使用您的代码会发生的情况。

def split(array):
    n = len(array)
    if n == 1:
        return
    else:
        i = n // 2
        subarray1 = array[:i]
        subarray2 = array[i:]
        yield subarray1
        yield subarray2

        for a in split(subarray1):
            yield a
        for a in split(subarray2):
            yield a

for a in split(range(16)):
    print a

输出

[0, 1, 2, 3, 4, 5, 6, 7]
[8, 9, 10, 11, 12, 13, 14, 15]
[0, 1, 2, 3]
[4, 5, 6, 7]
[0, 1]
[2, 3]
[0]
[1]
[2]
[3]
[4, 5]
[6, 7]
[4]
[5]
[6]
[7]
[8, 9, 10, 11]
[12, 13, 14, 15]
[8, 9]
[10, 11]
[8]
[9]
[10]
[11]
[12, 13]
[14, 15]
[12]
[13]
[14]
[15]

Answer 3

你可以尝试在这上面使用 memoryview, Eli Bendersky has written a nice blog entry。

不过我会尝试总结一下。在对象上创建内存视图时，您正在创建对存储对象的内存中的 (ctype) 数据结构的引用。 memoryview 切片是在该数据结构中查找特定值的位置的引用。您可以在同一底层结构上创建多个视图，而无需复制任何内容。这就像切片列表或数组一样工作。

尽管如此，您的数据必须支持缓冲协议（numpy 数组和字节数组支持，但列表不支持）。

我觉得加上这一行就够了

memview = memoryview(yourarray)

到您的代码并将其传递到 split 而不是您的数组。

不过请注意两件事：

您正在处理一个大数组，因此对数组的一部分（在一个切片中进行）的更改会传播到覆盖该值的所有其他切片。
您的结果现在是 memoryview 对象。要打印它们，您需要先将它们转换（例如转换为列表）。

示例：

>>> memview = memoryview("abcde")
>>> print memview
<memory at 0xfoo>
>>> print list(memview)
['a', 'b', 'c', 'd', 'e']

>>> mv_slice = memview[3:]
>>> print list(mv_slice)
['d', 'e']

>>> mv_slice[0] = 'y'
>>> print list(mv_slice)
['y', 'e']

>>> print list(memview)
['a', 'b', 'c', 'y', 'e']
# note that the change propagated to the main memoryview

当然，所有这一切都假定您可以一次将 50GB 加载到内存中。如果你做不到，你应该看看 mmap 模块。

编辑 - numpy 字符串数组

Will memoryview work with a numpy array of strings?

seems not. e.g. memview = memoryview(np.array(["abcde", 'aa'])), memview[0] is 'abcde', but memview[1] is 'aa\x00\x00\x00'

好吧，从技术上讲它确实有效。它只是展示了 numpy 如何存储字符串数组。那就是：严重 ;)

如果像这样创建一个 numpy 字符串数组：

>>> npa = np.array(["abcde", 'aa'])
>>> print repr(npa)
array(['abcde', 'aa'],
  dtype='|S5')

你看到 dtype 是 |S5，意思是长度为 5 的字符串。较短字符串的 'missing' 位置用空（零）字节填充（\x00）（为了方便起见，numpy 通常对我们隐藏）。这是因为 numpy 使用连续的二维数组将字符串存储在内存中以允许真正快速的随机访问。

这意味着，数组中的所有条目占用的内存与最长的字符串一样多。
把这个高度构造的数组想象成一个极端的例子：

strings = ["foobar"*100000] + ["f" for _ in xrange(10000)]
huge_npa = np.array(strings, dtype=str)

它包含一个非常长的字符串（600.000 个字符，每个 1 个字节）和 10.000 个只有 1 个字节的字符串。所以总内存消耗应该在 600KB 左右。如果你创建这个数组，虽然它占用 6GB 内存。

Expected:
1 string * 6 bytes * 100.000 => 600.000 * 1 byte = 600 KB
10.000 strings * 1 byte      =>  10.000 * 1 byte =  10 KB
total                                              610 kB

Reality:
10.000 strings * 6 bytes * 10.0000 => 6.000.000.000 * 1 byte = 6 GB

如果您的字符串大小相差很大，您可能会在这里浪费大量内存。也许你应该重新考虑为此使用 numpy 数组。

python 减少内存占用的递归收益

python recursive yield to reduce memory footprint

python

recursion

yield

编辑 - numpy 字符串数组