3

我有一个非常大的 1D python 数组x，其中有些重复的数字以及一些d相同大小的数据。

x = np.array([48531, 62312, 23345, 62312, 1567, ..., 23345, 23345])
d = np.array([0    , 1    , 2    , 3    , 4   , ..., 99998, 99999])

在我的上下文中，“非常大”是指 10k...100k 条目。其中一些是重复的，因此唯一条目的数量约为 5k...15k。

我想将它们分组到垃圾箱中。这应该通过创建两个对象来完成。一个是矩阵缓冲区，b数据项取自 d。另一个对象是v每个缓冲区列引用的唯一 x 值向量。这是示例：

v =  [48531, 62312, 23345, 1567, ...]
b = [[0    , 1    , 2    , 4   , ...]
     [X    , 3    , ....., ...., ...]
     [ ...., ....., ....., ...., ...]
     [X    , X    , 99998, X   , ...]
     [X    , X    , 99999, X   , ...] ]

由于 x 中每个唯一数字的出现次数不同，缓冲区 b 中的一些值是无效的（由大写字母表示X，即“不关心”）。

在 numpy 中很容易推导出 v：

v, n = np.unique(x, return_counts=True)  # yay, just 5ms

我们甚至得到nb 中每列中有效条目的数量。此外，(np.max(n), v.shape[0])返回需要分配的矩阵 b 的形状。

但是如何有效地生成 b？一个 for 循环可能会有所帮助

b = np.zeros((np.max(n), v.shape[0]))
for i in range(v.shape[0]):
    idx = np.flatnonzero(x == v[i])
    b[0:n[i], i] = d[idx]

此循环遍历 b 的所有列，并idx通过识别 的所有位置来提取索引x == v。

但是我不喜欢这个解决方案，因为 for 循环相当慢（比唯一命令长约 50 倍）。我宁愿将操作矢量化。

因此，一种矢量化方法是创建一个索引矩阵，x == v然后nonzero()在其上沿列运行命令。但是，此矩阵需要 150k x 15k 范围内的内存，因此在 32 位系统上大约需要 8GB。

np.unique对我来说， -操作甚至可以有效地返回倒排索引听起来很愚蠢，x = v[inv_indices]但是没有办法为 v 中的每个 bin 获取 v-to-x 分配列表。当函数时，这应该几乎是免费的正在扫描 x。在实现方面，唯一的挑战是生成的索引矩阵的未知大小。

假设 np.unique-command 是用于分箱的方法，则另一种表述这个问题的方法：

给定三个数组x, v, inv_indices中v的唯一元素，x是否x = v[inv_indices]有一种有效的方法来生成索引向量v_to_x[i]，all(v[i] == x[v_to_x[i]])以便所有 bin i？

我不应该花费比 np.unique-command 本身更多的时间。我很高兴为每个箱子中的物品数量提供一个上限（例如 50 个）。

4

2 回答 2

0

我通过改写问题得到了我正在寻找的答案，请参见此处：python：矢量化累积计数

通过“累积计数”inv_indices返回的np.unique()我们接收稀疏矩阵的数组索引，以便

c = cumcount(inv_indices)
b[inv_indices, c] = d

上面链接的线程中建议的累积计数非常有效。运行时间低于 20 毫秒是非常现实的。

于 2018-02-23T14:17:03.160 回答
0

根据@user202729 的建议，我编写了这段代码

x_sorted_args = np.argsort(x)
x_sorted = x[x_sorted_args]

i = 0
v = -np.ones(T)
b = np.zeros((K, T))

for k,g in groupby(enumerate(x_sorted), lambda tup: tup[1]):
    groups = np.array(list(g))[:,0]
    size = groups.shape[0]

    v[i] = k
    b[0:size, i] = d[x_sorted_args[groups]]
    i += 1

在大约 100 毫秒内运行，这导致上面发布的原始代码有相当大的加速。

x它首先在添加相应的索引信息时枚举值。然后枚举按实际x值分组，该值实际上是由 生成的元组的第二个值enumerate()。

for 循环遍历所有组，将这些元组迭代器g转换groups为大小矩阵，(size x 2)然后丢弃第二列，即x仅保留索引的值。这导致groups只是一个一维数组。

groupby()仅适用于排序数组。

干得好。我只是想知道我们是否可以做得更好？似乎仍然发生了很多不合理的数据复制。创建一个元组列表，然后将其转换为 2D 矩阵只是为了丢弃其中的一半仍然感觉不太理想。

于 2018-02-07T13:54:36.700 回答