python - Python中内存高效的大量numpy数组

Question

我需要使用 numpy 对一个非常大的基因组数据集进行排序。我有一个包含 26 亿个 float 的数组，维度 = (868940742, 3) 一旦加载并坐在那里就占用了我机器上大约 20GB 的内存。我有一台 2015 年初的 13' MacBook Pro，配备 16GB 内存、500GB 固态硬盘和 3.1 GHz 英特尔 i7 处理器。只是将数组加载到虚拟内存中，但不会导致我的机器受到影响，或者我必须停止我正在做的所有事情。

我从 22 个较小的 (N, 2) 子数组逐步构建这个非常大的数组。

函数 FUN_1 使用我称之为 sub_arr 的 22 个子数组中的每一个生成 2 个新的 (N, 1) 数组。

FUN_1 的第一个输出是通过将来自 sub_arr[:,0] 的值插入到数组 b = array([X, F(X) ]) 并通过使用数组 r = array([X, BIN(X)]) 将 sub_arr[:, 0] 放入 bin 中生成第二个输出>。我将这些输出分别称为 b_arr 和 rate_arr。该函数返回 (N, 1) 数组的三元组:

import numpy as np

def FUN_1(sub_arr):
    """interpolate b values and rates based on position in sub_arr"""

    b = np.load(bfile)
    r = np.load(rfile)

    b_arr = np.interp(sub_arr[:,0], b[:,0], b[:,1])
    rate_arr = np.searchsorted(r[:,0], sub_arr[:,0])  # HUGE efficiency gain over np.digitize...

    return r[rate_r, 1], b_arr, sub_arr[:,1] 

我在 for 循环中调用该函数 22 次，并用以下值填充预分配的零数组 full_arr = numpy.zeros([868940742, 3]):

full_arr[:,0], full_arr[:,1], full_arr[:,2] = FUN_1

在这一步节省内存方面，我认为这是我能做的最好的，但我愿意接受建议。无论哪种方式，我都没有遇到问题，而且只需要大约 2 分钟。

这里是排序例程(有两个连续的排序)

for idx in range(2):
    sort_idx = numpy.argsort(full_arr[:,idx])
    full_arr = full_arr[sort_idx]
    # ...
    # <additional processing, return small (1000, 3) array of stats>

现在这种方法一直在工作，尽管速度很慢(大约需要 10 分钟)。然而，我最近开始使用一个更大、更精细的 [X, F(X)] 值的分辨率表，用于返回 b_arr 的 FUN_1 中的上述插值步骤 现在 SORT 真的变慢了，尽管其他一切都保持不变。

有趣的是，我什至没有在排序滞后的那一步对插值进行排序。以下是不同插值文件的一些片段——较小的插值文件在每种情况下都小了大约 30%，并且在第二列中的值更加统一；较慢的具有更高的分辨率和更多的独特值，因此插值的结果可能更独特，但我不确定这是否应该有任何效果......？

更大、更慢的文件:

17399307    99.4
17493652    98.8
17570460    98.2
17575180    97.6
17577127    97
17578255    96.4
17580576    95.8
17583028    95.2
17583699    94.6
17584172    94

更小、更统一的常规文件:

1       24  
1001    24  
2001    24  
3001    24  
4001    24  
5001    24
6001    24
7001    24

我不确定是什么导致了这个问题，我会对任何关于在这种内存限制情况下排序的建议或一般输入感兴趣!

Answer 1

目前，对 np.argsort 的每次调用都会生成一个 (868940742, 1) 数组 int64 索引，它本身将占用大约 7 GB。此外，当您使用这些索引对 full_arr 的列进行排序时，您将生成另一个 (868940742, 1) float 组，因为 fancy indexing always returns a copy rather than a view .

一个相当明显的改进是使用它的 .sort() method 对 full_arr 进行排序。 .不幸的是，.sort() 不允许您直接指定要排序的行或列。但是，您可以为结构化数组指定一个作为排序依据的字段。因此，您可以通过获取 view 来强制对三列之一进行就地排序。作为具有三个浮点字段的结构化数组添加到您的数组中，然后按以下字段之一排序:

full_arr.view('f8, f8, f8').sort(order=['f0'], axis=0)

在这种情况下，我将 full_arr 按第 0 个字段排序，该字段对应于第一列。请注意，我假设有三个 float64 列 ('f8') - 如果您的 dtype 不同，您应该相应地更改它。这还要求您的数组是连续的并且采用行主要格式，即 full_arr.flags.C_CONTIGUOUS == True。

此方法的功劳应归功于 Joe Kington 的回答 here .

---

虽然它需要更少的内存，但不幸的是，与使用 np.argsort 生成索引数组相比，按字段对结构化数组进行排序要慢得多，正如您在下面的评论中提到的(参见 this previous question )。如果您使用 np.argsort 来获取一组要排序的索引，您可能会看到通过使用 np.take 而不是直接索引来获取排序的适度的性能提升数组:

 %%timeit -n 1 -r 100 x = np.random.randn(10000, 2); idx = x[:, 0].argsort()
x[idx]
# 1 loops, best of 100: 148 µs per loop

 %%timeit -n 1 -r 100 x = np.random.randn(10000, 2); idx = x[:, 0].argsort()
np.take(x, idx, axis=0)
# 1 loops, best of 100: 42.9 µs per loop

但是我不希望在内存使用方面看到任何差异，因为这两种方法都会生成一个副本。

---

关于您关于为什么对第二个数组进行排序更快的问题 - 是的，当数组中的唯一值较少时，您应该期望任何合理的排序算法更快，因为平均而言，它要做的工作更少。假设我有一个 1 到 10 之间的随机数字序列:

5  1  4  8  10  2  6  9  7  3

有10个! = 3628800 种排列这些数字的可能方式，但只有一种是按升序排列的。现在假设只有 5 个唯一数字:

4  4  3  2  3  1  2  5  1  5

现在有 2⁵ = 32 种方法可以按升序排列这些数字，因为我可以在排序后的向量中交换任何一对相同的数字而不会破坏顺序。

默认情况下，np.ndarray.sort() 使用 Quicksort . qsort该算法的变体通过递归选择数组中的“枢轴”元素，然后重新排序数组，使得所有小于枢轴值的元素都放在它之前，所有大于枢轴值的元素都放在它之后.等于枢轴的值已经排序。具有更少的唯一值意味着，平均而言，更多的值将等于任何给定扫描的主值，因此需要更少的扫描来对数组进行完全排序。

例如:

%%timeit -n 1 -r 100 x = np.random.random_integers(0, 10, 100000)
x.sort()
# 1 loops, best of 100: 2.3 ms per loop

%%timeit -n 1 -r 100 x = np.random.random_integers(0, 1000, 100000)
x.sort()
# 1 loops, best of 100: 4.62 ms per loop

在这个例子中，两个数组的 dtypes 是相同的。如果较小的数组与较大的数组相比具有较小的项大小，那么由于花哨的索引而复制它的成本也会更小。