从逻辑矩阵到集合列表的最快方法

我需要将稀疏逻辑矩阵转换为集合列表，其中每个列表[i]包含列[i]的非零值的行集合。下面的代码有效，但我想知道是否有更快的方法来做到这一点。我使用的实际数据大约是6000x6000，比这个例子更稀疏。从逻辑矩阵到集合列表的最快方法

import numpy as np 

A = np.array([[1, 0, 0, 0, 0, 1], 
       [0, 1, 1, 1, 1, 0], 
       [1, 0, 1, 0, 1, 1], 
       [1, 1, 0, 1, 0, 1], 
       [1, 1, 0, 1, 0, 0], 
       [1, 0, 0, 0, 0, 0], 
       [0, 0, 1, 1, 1, 0], 
       [0, 0, 1, 0, 1, 0]]) 

rows,cols = A.shape 

C = np.nonzero(A) 
D = [set() for j in range(cols)] 

for i in range(len(C[0])): 
    D[C[1][i]].add(C[0][i]) 

print D

来源

2016-06-11 ToneDaBass

如果您代表稀疏数组为csc_matrix，您可以使用indices和indptr属性创建集。

例如，

In [93]: A 
Out[93]: 
array([[1, 0, 0, 0, 0, 1], 
     [0, 1, 1, 1, 1, 0], 
     [1, 0, 1, 0, 1, 1], 
     [1, 1, 0, 1, 0, 1], 
     [1, 1, 0, 1, 0, 0], 
     [1, 0, 0, 0, 0, 0], 
     [0, 0, 1, 1, 1, 0], 
     [0, 0, 1, 0, 1, 0]]) 

In [94]: from scipy.sparse import csc_matrix 

In [95]: C = csc_matrix(A) 

In [96]: C.indptr 
Out[96]: array([ 0, 5, 8, 12, 16, 20, 23], dtype=int32) 

In [97]: C.indices 
Out[97]: array([0, 2, 3, 4, 5, 1, 3, 4, 1, 2, 6, 7, 1, 3, 4, 6, 1, 2, 6, 7, 0, 2, 3], dtype=int32) 

In [98]: D = [set(C.indices[C.indptr[i]:C.indptr[i+1]]) for i in range(C.shape[1])] 

In [99]: D 
Out[99]: 
[{0, 2, 3, 4, 5}, 
{1, 3, 4}, 
{1, 2, 6, 7}, 
{1, 3, 4, 6}, 
{1, 2, 6, 7}, 
{0, 2, 3}]

对于数组，而不是集列表，只是不叫set()：

In [100]: [C.indices[C.indptr[i]:C.indptr[i+1]] for i in range(len(C.indptr)-1)] 
Out[100]: 
[array([0, 2, 3, 4, 5], dtype=int32), 
array([1, 3, 4], dtype=int32), 
array([1, 2, 6, 7], dtype=int32), 
array([1, 3, 4, 6], dtype=int32), 
array([1, 2, 6, 7], dtype=int32), 
array([0, 2, 3], dtype=int32)]

来源

2016-06-11 00:23:46

真棒，这方法大约是我原来的代码的两倍。谢谢！ – ToneDaBass

在较大的稀疏数组上，我发现'np.nonzero（A）'和'稀疏。csc_matrix（A）'大概在同一时间。它比收集集合的迭代要大得多。 – hpaulj

我不知道，如果速度增加不多，但你的迭代可精简为

for i,j in zip(*C): 
    D[j].add(i)

defaultdict可以为此任务添加一个不错的接触：

In [58]: from collections import defaultdict  
In [59]: D=defaultdict(set) 
In [60]: for i,j in zip(*C): 
    D[j].add(i) 

In [61]: D 
Out[61]: defaultdict(<class 'set'>, {0: {0, 2, 3, 4, 5}, 1: {1, 3, 4}, 2: {1, 2, 6, 7}, 3: {1, 3, 4, 6}, 4: {1, 2, 6, 7}, 5: {0, 2, 3}}) 

In [62]: dict(D) 
Out[62]: 
{0: {0, 2, 3, 4, 5}, 
1: {1, 3, 4}, 
2: {1, 2, 6, 7}, 
3: {1, 3, 4, 6}, 
4: {1, 2, 6, 7}, 
5: {0, 2, 3}}

带稀疏矩阵的替代方法是lil格式，该格式将数据保存为列表列表。由于您想按列收集数据，因此请从A.T（转置）制作矩阵

In [70]: M=sparse.lil_matrix(A.T) 

In [71]: M.rows 
Out[71]: 
array([[0, 2, 3, 4, 5], [1, 3, 4], [1, 2, 6, 7], [1, 3, 4, 6], 
     [1, 2, 6, 7], [0, 2, 3]], dtype=object)

这些列表相同。

对于这种小的情况下直接迭代比稀疏

In [72]: %%timeit 
    ....: D=defaultdict(set) 
    ....: for i,j in zip(*C): 
    D[j].add(i) 
    ....: 
10000 loops, best of 3: 24.4 µs per loop 

In [73]: %%timeit 
    ....: D=[set() for j in range(A.shape[1])] 
    ....: for i,j in zip(*C): 
    D[j].add(i) 
    ....: 
10000 loops, best of 3: 22.9 µs per loop 

In [74]: %%timeit 
    ....: M=sparse.lil_matrix(A.T) 
    ....: M.rows 
    ....: 
1000 loops, best of 3: 588 µs per loop 

In [75]: %%timeit 
    ....: C=sparse.csc_matrix(A) 
    ....: D = [set(C.indices[C.indptr[i]:C.indptr[i+1]]) for i in range(C.shape[1])] ....: 
1000 loops, best of 3: 476 µs per loop

更快对于一个大的阵列中，设置时间稀疏矩阵将更少显著。

==========================

我们真的需要set？在lil方法的一个变型是转置开始与nonzero，即通过柱

In [90]: C=np.nonzero(A.T) 

# (array([0, 0, 0, 0, 0, 1, 1, 1, 2, 2, 2, 2, 3, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5], dtype=int32), 
# array([0, 2, 3, 4, 5, 1, 3, 4, 1, 2, 6, 7, 1, 3, 4, 6, 1, 2, 6, 7, 0, 2, 3], dtype=int32))

中的数字都在那里;我们只需将第二个列表拆分为对应于第一个的部分

In [91]: i=np.nonzero(np.diff(C[0]))[0]+1 

In [92]: np.split(C[1],i) 
Out[92]: 
[array([0, 2, 3, 4, 5], dtype=int32), 
array([1, 3, 4], dtype=int32), 
array([1, 2, 6, 7], dtype=int32), 
array([1, 3, 4, 6], dtype=int32), 
array([1, 2, 6, 7], dtype=int32), 
array([0, 2, 3], dtype=int32)]

这比直接迭代慢，但我怀疑它比较好;可能以及任何稀疏的替代品：

In [96]: %%timeit 
C=np.nonzero(A.T) 
    ....: i=np.nonzero(np.diff(C[0]))[0]+1 
    ....: np.split(C[1],i) 
    ....: 
10000 loops, best of 3: 55.2 µs per loop

来源

2016-06-11 00:32:47 hpaulj

这很酷。在我的测试中，CSC_matrix方法似乎比LIL_matrix方法快两倍。 – ToneDaBass

在小样本中，'lil'构造比'csc'构造慢了一点。从'coo'到'csc'的转换是编译代码。 – hpaulj

我确实需要集合，因为接下来我要做的是删除其他列的子集的列。设置（i）.issubset（set（j））似乎是执行此操作的最快方法。 – ToneDaBass

既然你已经在A称为np.nonzero，看看这是否更快：

>>> from itertools import groupby 
>>> C = np.transpose(np.nonzero(A.T)) 
>>> [{i[1] for i in g} for _, g in groupby(C, key=lambda x: x[0])] 
[{0, 2, 3, 4, 5}, {1, 3, 4}, {1, 2, 6, 7}, {1, 3, 4, 6}, {1, 2, 6, 7}, {0, 2, 3}]

一些时间：

In [4]: %%timeit 
    ...: C = np.transpose(np.nonzero(A.T)) 
    ...: [{i[1] for i in g} for _, g in groupby(C, key=lambda x: x[0])] 
    ...: 
10000 loops, best of 3: 39 µs per loop 

In [7]: %%timeit 
    ...: C=csc_matrix(A) 
    ...: [set(C.indices[C.indptr[i]:C.indptr[i+1]]) for i in range(C.shape[1])] 
    ...: 
1000 loops, best of 3: 317 µs per loop

来源

2016-06-11 00:53:05

我最后的编辑做了这样的事情，但是使用'np.split'将'C [1]'数组分解成块。 – hpaulj

由于'np.split'和'groupby'都是用c编写的，不知道哪一个会更快。我应该做一个'timeit' –

有趣的方法，但csc_matrix似乎在我的大型数据集上更快 – ToneDaBass

从逻辑矩阵到集合列表的最快方法

回答

相关问题