Tengo una muestra grande (M) de matrices booleanas de longitud 'N'. Entonces, hay 2 ^ N matrices booleanas únicas posibles. Me gustaría saber cuántas matrices son duplicadas entre sí y crear un histograma.

Una posibilidad es crear un número entero único (a [0] + a [1] * 2 + a [3] * 4 + ... + a [N] * 2 ^ (N-1)) para cada matriz única y histograma ese entero.

Pero esto va a ser O (M * N). ¿Cuál es la mejor manera de hacer esto?

1
PyariBilli 27 nov. 2021 a las 09:32
Depende mucho de tu salida. Almacenar 2 ^ N combinaciones quema su memoria rápidamente para valores grandes de N. En este caso, use mejor np.histogram. Puede que solo haya una pequeña parte de ellos en arr. En este caso, no es necesario trabajar con 2 ^ N elementos y utilizar np.bincount. No hay mejores formas que hacer (a[0] + a[1]*2 + a[3]*4 + ...+a[N]*2^(N-1) y numpy.ravel_multi_index realmente lo hace en su esencia. Pero si te gusta algo aún más eficaz, prueba numexpr
 – 
mathfux
27 nov. 2021 a las 12:47

2 respuestas

La mejor respuesta

numpy.ravel_multi_index puede hacer esto por usted :

arr = np.array([[True, True, True], 
              [True, False, True], 
              [True, False, True], 
              [False, False, False], 
              [True, False, True]], dtype=int)
nums = np.ravel_multi_index(arr.T, (2,) * arr.shape[1])
>>> nums
array([7, 5, 5, 0, 5], dtype=int64)

Y como necesita un histograma, use

>>> np.histogram(nums, bins=np.arange(2**arr.shape[1]+1))
(array([1, 0, 0, 0, 0, 3, 0, 1], dtype=int64), 
 array([0, 1, 2, 3, 4, 5, 6, 7, 8]))

Otra opción es usar np.unique:

>>> np.unique(arr, return_counts=True, axis=0)
(array([[0, 0, 0],
        [1, 0, 1],
        [1, 1, 1]]),
 array([1, 3, 1], dtype=int64))
1
mathfux 27 nov. 2021 a las 12:25

Con la operación vectorizada, la creación de una clave es mucho más rápida que a [0] + a [1] x2 + a [3] x4 + ... + a [N] * 2 ^ (N-1). Creo que esa no es una solución mejor ... en cualquier caso, necesita casi "leer" una vez cada valor, y esto requiere un paso MxN.

N = 3
M = 5
sample = [
    np.array([True, True, True]),
    np.array([True, False, True]),
    np.array([True, False, True]),
    np.array([False, False, False]),
    np.array([True, False, True]),
]

multipliers = [2<<i for i in range(N-2, -1, -1)]+[1]

buckets = {}
buck2vec = {}
for s in sample:
    key = sum(s*multipliers)
    if key not in buckets:
        buckets[key] = 0
        buck2vec[key] = s
    buckets[key]+=1
    
for key in buckets:
    print(f"{buck2vec[key]} -> {buckets[key]} occurency")

Resultados:

[False False False] -> 1 occurency
[ True False  True] -> 3 occurency
[ True  True  True] -> 1 occurency
-1
Massimo Rebuglio 27 nov. 2021 a las 11:28