Schnellster Weg von der Logikmatrix zur Liste der Sätze

Question

Ich muss eine spärliche Logikmatrix in eine Liste von Mengen konvertieren, wobei jede Liste [i] die Menge von Zeilen mit Nicht-Null-Werten für Spalte [i] enthält. Der folgende Code funktioniert, aber ich frage mich, ob es einen schnelleren Weg dafür gibt. Die tatsächlichen Daten, die ich verwende, sind ungefähr 6000x6000 und viel spärlicher als dieses Beispiel.

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 

Answer 1

Wenn Sie das spärliche Array als csc_matrix darstellen, können Sie die indices und indptr Attribute verwenden, um die Sätze zu erstellen.

Zum Beispiel

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}] 

Eine Liste von Arrays anstelle von Sätzen, rufen einfach nicht 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)] 

Answer 2

Ich weiß nicht, ob steigt viel schneller, aber Ihre Iteration kann mit

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

rationalisiert werden Ein defaultdict könnte dieser Aufgabe einen netten Touch hinzufügen:

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}} 

Eine Alternative mit spärlichen Matrizen ist das lil Format, das die Daten eine Liste von Listen speichert. Da Sie durch Spalte sammeln Daten möchten, stellen Sie die Matrix aus A.T (transponieren)

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) 

, die die gleichen Listen sind.

Für diese kleine Fall direkten Iteration ist schneller als spärlich

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 

Für eine große Auswahl, die Rüstzeit für die spärliche Matrix weniger signifikant.

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

Haben wir wirklich set brauchen? Eine Variation des lil Ansatz ist mit der Transponierten nonzero auf dem, das heißt, durch Spalte

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)) 

Die Zahlen sind alle dort zu beginnen; wir müssen nur die zweite Liste in Stücke aufgeteilt auf die ersten

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)] 

entsprechen Dies ist langsamer als die direkte Iteration, aber ich vermute, dass es besser skaliert; möglicherweise auch eine der spärlichen Alternativen:

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 

Answer 3

Da Sie bereits np.nonzero auf A genannt, sehen, ob das funktioniert schneller:

>>> 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}] 

Einige Timing:

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