python - Le moyen le plus rapide de convertir une liste d’index en un tableau 2D à numpy




arrays performance (4)

Ce n'est peut-être pas le moyen le plus rapide. Vous devrez comparer les temps d'exécution de ces réponses à l'aide de grands tableaux afin de déterminer le moyen le plus rapide. Voici ma solution

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

J'ai une liste d'indices

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

Quel est le moyen le plus rapide de convertir cela en un tableau numpy de 1, où chaque index indique la position où 1 se produirait?

C'est ce que je veux, c'est:

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

Je connais la taille maximale du tableau à l'avance. Je sais que je pourrais parcourir chaque liste et insérer un 1 à chaque position d'index, mais existe-t-il un moyen plus rapide / vectorisé de le faire?

Mon cas d'utilisation peut contenir des milliers de lignes / colonnes et je dois le faire des milliers de fois, donc le plus rapide sera le mieux.


Dans le cas où vous pouvez et souhaitez utiliser Cython vous pouvez créer une solution lisible (du moins si cela ne vous dérange pas de la frappe) et rapide.

Ici, j'utilise les liaisons IPython de Cython pour le compiler dans un cahier 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

Pour comparer les performances des solutions présentées ici, j'utilise ma bibliothèque simple_benchmark :

Notez que cela utilise l’axe logarithmique pour afficher simultanément les différences entre les tableaux de taille petite et grande. Selon mes critères, ma fonction est en fait la plus rapide des solutions, mais il convient également de souligner que toutes les solutions ne sont pas trop éloignées.

Voici le code complet que j'ai utilisé pour le benchmark:

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

Pourquoi ne pas utiliser l'indexation par tableaux? Si vous en saviez plus sur votre entrée, vous pourriez vous débarrasser de la pénalité liée à la conversion préalable en un tableau linéaire.

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

Que dis-tu de ça:

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

Voici les timings pour un tableau binaire 1000x1000, notez que j'utilise une version optimisée de ce qui précède, voir la fonction pp ci-dessous:

pp 21.717635259992676 ms
ts 37.10938713003998 ms
u9 37.32933565042913 ms

Code pour produire les timings:

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




numpy