python - La forma más rápida de convertir una lista de índices a una matriz numpy 2D de unos

arrays performance

Question

Tengo una lista de indices

a = [
  [1,2,4],
  [0,2,3],
  [1,3,4],
  [0,2]]

¿Cuál es la forma más rápida de convertir esto en una gran variedad de unidades, donde cada índice muestra la posición en la que ocurriría 1?

Es decir lo que quiero es:

output = array([
  [0,1,1,0,1],
  [1,0,1,1,0],
  [0,1,0,1,1],
  [1,0,1,0,0]])

Sé de antemano el tamaño máximo de la matriz. Sé que podría recorrer cada lista e insertar un 1 en cada posición del índice, pero ¿hay una forma más rápida / vectorizada de hacerlo?

Mi caso de uso podría tener miles de filas / cols y tengo que hacer esto miles de veces, así que cuanto más rápido mejor.

Answer 1

¿Qué hay de usar la indexación de matriz? Si supiera más acerca de su entrada, podría deshacerse de la penalización por tener que convertir primero a una matriz lineal.

import numpy as np


def main():
    row_count = 4
    col_count = 5
    a = [[1,2,4],[0,2,3],[1,3,4],[0,2]]

    # iterate through each row, concatenate all indices and convert them to linear

    # numpy append performs copy even if you don''t want it, list append is faster
    b = []
    for row_idx, row in enumerate(a):
        b.append(np.array(row, dtype=np.int64) + (row_idx * col_count))

    linear_idxs = np.hstack(b)
    #could skip previous steps if given index inputs well before hand, or in linear index order. 
    c = np.zeros(row_count * col_count)
    c[linear_idxs] = 1
    c = c.reshape(row_count, col_count)
    print(c)


if __name__ == "__main__":
    main()

#output
# [[0. 1. 1. 0. 1.]
#  [1. 0. 1. 1. 0.]
#  [0. 1. 0. 1. 1.]
#  [1. 0. 1. 0. 0.]]

Answer 2

En caso de que pueda y quiera usar Cython , puede crear una solución legible (al menos si no le importa la escritura) y rápida.

Aquí estoy usando los enlaces IPython de Cython para compilarlo en un cuaderno Jupyter:

%load_ext cython

%%cython

cimport cython
cimport numpy as cnp
import numpy as np

@cython.boundscheck(False)  # remove this if you cannot guarantee that nrow/ncol are correct
@cython.wraparound(False)
cpdef cnp.int_t[:, :] mseifert(list a, int nrow, int ncol):
    cdef cnp.int_t[:, :] out = np.zeros([nrow, ncol], dtype=int)
    cdef list subl
    cdef int row_idx
    cdef int col_idx
    for row_idx, subl in enumerate(a):
        for col_idx in subl:
            out[row_idx, col_idx] = 1
    return out

Para comparar el rendimiento de las soluciones presentadas aquí, uso mi biblioteca simple_benchmark :

Tenga en cuenta que esto utiliza el eje logarítmico para mostrar simultáneamente las diferencias para matrices grandes y pequeñas. Según mi punto de referencia, mi función es en realidad la más rápida de las soluciones, sin embargo, también vale la pena señalar que todas las soluciones no están demasiado lejos.

Aquí está el código completo que utilicé para el punto de referencia:

import numpy as np
from simple_benchmark import BenchmarkBuilder, MultiArgument
import itertools

b = BenchmarkBuilder()

@b.add_function()
def pp(a, nrow, ncol):
    sz = np.fromiter(map(len, a), int, nrow)
    out = np.zeros((nrow, ncol), int)
    out[np.arange(nrow).repeat(sz), np.fromiter(itertools.chain.from_iterable(a), int, sz.sum())] = 1
    return out

@b.add_function()
def ts(a, nrow, ncol):
    out = np.zeros((nrow, ncol), int)
    for i, ix in enumerate(a):
        out[i][ix] = 1
    return out

@b.add_function()
def u9(a, nrow, ncol):
    out = np.zeros((nrow, ncol), int)
    for i, (x, y) in enumerate(zip(a, out)):
        y[x] = 1
        out[i] = y
    return out

b.add_functions([mseifert])

@b.add_arguments("number of rows/columns")
def argument_provider():
    for n in range(2, 13):
        ncols = 2**n
        a = [
            sorted(set(np.random.randint(0, ncols, size=np.random.randint(0, ncols)))) 
            for _ in range(ncols)
        ]
        yield ncols, MultiArgument([a, ncols, ncols])

r = b.run()
r.plot()

Answer 3

Esta podría no ser la forma más rápida. Tendrá que comparar los tiempos de ejecución de estas respuestas utilizando matrices grandes para encontrar la manera más rápida. Aquí está mi solución

output = np.zeros((4,5))
for i, ix in enumerate(a):
    output[i][ix] = 1

# output -> 
#   array([[0, 1, 1, 0, 1],
#   [1, 0, 1, 1, 0],
#   [0, 1, 0, 1, 1],
#   [1, 0, 1, 0, 0]])

Answer 4

Puede que no sea la mejor manera, sino la única en la que puedo pensar:

output = np.zeros((4,5))
for i, (x, y) in enumerate(zip(a, output)):
    y[x] = 1
    output[i] = y
print(output)

Qué salidas:

[[ 0.  1.  1.  0.  1.]
 [ 1.  0.  1.  1.  0.]
 [ 0.  1.  0.  1.  1.]
 [ 1.  0.  1.  0.  0.]]

Answer 5

Qué tal esto:

ncol = 5
nrow = len(a)
out = np.zeros((nrow, ncol), int)
out[np.arange(nrow).repeat([*map(len,a)]), np.concatenate(a)] = 1
out
# array([[0, 1, 1, 0, 1],
#        [1, 0, 1, 1, 0],
#        [0, 1, 0, 1, 1],
#        [1, 0, 1, 0, 0]])

Aquí hay tiempos para una matriz binaria de 1000x1000, tenga en cuenta que uso una versión optimizada de lo anterior, vea la función pp continuación:

pp 21.717635259992676 ms
ts 37.10938713003998 ms
u9 37.32933565042913 ms

Código para producir tiempos:

import itertools as it
import numpy as np

def make_data(n,m):
    I,J = np.where(np.random.random((n,m))<np.random.random((n,1)))
    return [*map(np.ndarray.tolist, np.split(J, I.searchsorted(np.arange(1,n))))]

def pp():
    sz = np.fromiter(map(len,a),int,nrow)
    out = np.zeros((nrow,ncol),int)
    out[np.arange(nrow).repeat(sz),np.fromiter(it.chain.from_iterable(a),int,sz.sum())] = 1
    return out

def ts():
    out = np.zeros((nrow,ncol),int)
    for i, ix in enumerate(a):
        out[i][ix] = 1
    return out

def u9():
    out = np.zeros((nrow,ncol),int)
    for i, (x, y) in enumerate(zip(a, out)):
        y[x] = 1
        out[i] = y
    return out

nrow,ncol = 1000,1000
a = make_data(nrow,ncol)

from timeit import timeit
assert (pp()==ts()).all()
assert (pp()==u9()).all()

print("pp", timeit(pp,number=100)*10, "ms")
print("ts", timeit(ts,number=100)*10, "ms")
print("u9", timeit(u9,number=100)*10, "ms")