13

What is the time-complexity of np.transpose?

In my opinion, it loops two for loops inside so, that means it should have O(n2) complexity but can someone confirm on that? Also, is there any way so, that I can reduce the time-complexity of matrix transpose

Ricky
  • 147
  • 1
  • 2
  • 9
  • As others noted, a numpy transpose just changes a couple of parameters, not the whole data buffer. But subsequent use of the transposed array might require a copy, which will roughly depend on the total number of elements. But in general the `numpy` approach to handling dimensions is flexible and efficient - don't be afraid to take full advantage of its features. – hpaulj Oct 08 '19 at 04:19

3 Answers3

14

In memory the matrices are represented as blocks of contiguous memory, that is as if it were a one-dimensional array. N-dimensions are an abstraction that we humans use to make the problem more understandable. For numpy, transposing the matrix is ​​simply an axis change, but the memory is not changed.

So the temporal complexity is O(1) because to transpose an array, numpy just swaps the shape and stride information for each axis.

No data needs to be copied for this to happen. Numpy can simply change how it looks at the underlying memory to construct the new array.

If you want to deepen the topic you can see this beautiful answer with illustrations

Massifox
  • 4,369
  • 11
  • 31
  • 1
    As someone who is a physical scientist first and a computer scientist second, "N-dimensions are an abstraction that we humans use to make the problem more understandable." is . . hilarious on so many levels. – Daniel F Oct 08 '19 at 05:49
  • Hilarious on as many levels as there are dimensions in the `ndarray`? – fishmulch Jul 26 '22 at 22:03
  • The above answer applies to the numpy `reshape` operation as well. – Rafael Nov 01 '22 at 09:39
11

It is O(1), because it does not copy data at all. Just modifies the shape and strides.

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

Note that C_CONTIGUOUS, F_CONTIGUOUS were swapped (i.e. major iteration order changes), and the transposed array has OWNDATA false (i.e. it is just a view into the original array's data).

Related tip: when you have a view like this, to find the array owning the data you can check the base attribute

>>> np.transpose(A).base is A
True
wim
  • 338,267
  • 99
  • 616
  • 750
  • 1
    I'd say it modifies `shape` and `strides`. The flags change is an indirect effect of changing strides. I think `A.__array_interface__` is a better indicator than `flags`. – hpaulj Oct 08 '19 at 01:34
  • 1
    Well however you want to look at it. The main point is that the array data is not copied by a transpose. – wim Oct 08 '19 at 01:39
-2

Yes adding to that we can also transpose matrix by using zip 

list(zip(*matrix))
Ricky
  • 147
  • 1
  • 2
  • 9
  • 1
    That's not a `numpy` answer. – hpaulj Oct 08 '19 at 03:43
  • that's true but as I mentioned in my question that I was looking for any other way to transpose the matrix(not necessarily numpy). I found this one so, shared. – Ricky Oct 09 '19 at 03:10
  • 2
    I didn't notice that you'd answered your own question. If you start with a list of lists, then this probably the best way of doing a 'transpose'. I wouldn't use it if `matrix` is already a `numpy` array. `numpy` can change the order of axes simply by changing the `strides`; no copy is needed. – hpaulj Oct 09 '19 at 04:27