Complexité temporelle de numpy.transpose

Question

Quelle est la complexité temporelle de np.transpose ?

A mon avis, il y a deux boucles for à l'intérieur, ce qui signifie qu'il devrait avoir une complexité O(n2) mais quelqu'un peut-il le confirmer ? De plus, y a-t-il un moyen de réduire la complexité temporelle de la transposition de matrice ?

Answer 1

En mémoire, les matrices sont représentées comme des blocs de mémoire contigus, c'est-à-dire comme s'il s'agissait d'un tableau unidimensionnel. Les N-dimensions sont une abstraction que nous, humains, utilisons pour rendre le problème plus compréhensible. Pour numpy, la transposition de la matrice est simplement un changement d'axe, mais la mémoire n'est pas modifiée.

Donc la complexité temporelle est O(1) parce que pour transposer un tableau, numpy échange simplement les informations de forme et de stride pour chaque axe.

Aucune donnée ne doit être copiée pour que cela se produise. Numpy peut simplement changer la façon dont il regarde la mémoire sous-jacente pour construire le nouveau tableau.

Si vous voulez approfondir le sujet, vous pouvez voir ce belle réponse avec des illustrations

Answer 2

Elle est O(1), car elle ne copie pas du tout les données. Il modifie juste la forme et les enjambées.

>>> A = np.random.rand(3,4)
>>> A.flags
  C_CONTIGUOUS : True
  F_CONTIGUOUS : False
  OWNDATA : True
  WRITEABLE : True
  ALIGNED : True
  WRITEBACKIFCOPY : False
  UPDATEIFCOPY : False
>>> np.transpose(A).flags
  C_CONTIGUOUS : False
  F_CONTIGUOUS : True
  OWNDATA : False
  WRITEABLE : True
  ALIGNED : True
  WRITEBACKIFCOPY : False
  UPDATEIFCOPY : False

Notez que C_CONTIGUOUS , F_CONTIGUOUS ont été échangés (c'est-à-dire des changements majeurs de l'ordre d'itération), et le tableau transposé a OWNDATA faux (c'est-à-dire qu'il s'agit simplement d'un voir dans les données du tableau original).

Conseil connexe : Lorsque vous avez une vue comme celle-ci, pour trouver le tableau qui contient les données, vous pouvez vérifier la valeur de l'attribut base attribut

>>> np.transpose(A).base is A
True

Answer 3

Oui, en plus de cela, nous pouvons aussi transposer la matrice en utilisant zip.

list(zip(*matrix))