What mathematical or memory trick does numpy.flatten() use on numpy.transform?

Question

I am trying to replicate transpose + flatten method of numpy. In order to take transpose, I only swap the last dimension with the dimension I want to transpose. Then I transform item positions to
linear index. However item ordering comes out different with numpy.flatten(). How can i achieve same behavior? Desired output is numpy flatten output. The question is how does numpy achieve this?

Here is the example:

Step 1:
Let's say I have an 1d array of K=16 sequential integers:

1d_Arr = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])`

Step 2:
I reshape it to (2,2,4) dimensions. (row, col, depth) == (2,2,4)

3d_Arr = 1d_Arr.reshape((2,2,4))

Step 3:
Take dimension-wise transpose.
Notice they all swapped with the last index of the 3d_Arr.shape.

row_transpose   = 3d_Arr.transpose((2,1,0)).flatten()
col_transpose   = 3d_Arr.transpose((0,2,1)).flatten()
depth_transpose = 3d_Arr.transpose((0,1,2)).flatten()

Step 4:
Print indices by using:

# returns where is the element in the array. Such as (2,0,1)
# i: is a value of an array item.
indices = np.where(anArray == i)
# returns the current (some?) linear index for the given indices
linear_idx = np.ravel_multi_index(indices, anArray.shape)

Results:

1d_Array (Linear) :

[ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15]

Desired output:

row-transpose-flatten   = [ 0  8  4 12  1  9  5 13  2 10  6 14  3 11  7 15]  
col-transpose-flatten   = [ 0  4  1  5  2  6  3  7  8 12  9 13 10 14 11 15]  
depth-transpose-flatten = [ 0  1  2  3  4  5  6  7  8  9 10 11 12 13 14 15]`

My strategy

DEPTH-TRANSPOSE :

Element Value -> Element indices -> ravel_multi_index for Element indices

0 ->  (array([0]), array([0]), array([0])) ->  [0]
1 ->  (array([0]), array([0]), array([1])) ->  [1]
2 ->  (array([0]), array([0]), array([2])) ->  [2]
3 ->  (array([0]), array([0]), array([3])) ->  [3]
4 ->  (array([0]), array([1]), array([0])) ->  [4]
5 ->  (array([0]), array([1]), array([1])) ->  [5]
6 ->  (array([0]), array([1]), array([2])) ->  [6]
7 ->  (array([0]), array([1]), array([3])) ->  [7]
8 ->  (array([1]), array([0]), array([0])) ->  [8]
9 ->  (array([1]), array([0]), array([1])) ->  [9]
10 ->  (array([1]), array([0]), array([2])) ->  [10]
11 ->  (array([1]), array([0]), array([3])) ->  [11]
12 ->  (array([1]), array([1]), array([0])) ->  [12]
13 ->  (array([1]), array([1]), array([1])) ->  [13]
14 ->  (array([1]), array([1]), array([2])) ->  [14]
15 ->  (array([1]), array([1]), array([3])) ->  [15]

ROW-TRANSPOSE :

Element Value -> Element indices -> ravel_multi_index for Element indices

0 ->  (array([0]), array([0]), array([0])) ->  [0]
1 ->  (array([1]), array([0]), array([0])) ->  [4]
2 ->  (array([2]), array([0]), array([0])) ->  [8]
3 ->  (array([3]), array([0]), array([0])) ->  [12]
4 ->  (array([0]), array([1]), array([0])) ->  [2]
5 ->  (array([1]), array([1]), array([0])) ->  [6]
6 ->  (array([2]), array([1]), array([0])) ->  [10]
7 ->  (array([3]), array([1]), array([0])) ->  [14]
8 ->  (array([0]), array([0]), array([1])) ->  [1]
9 ->  (array([1]), array([0]), array([1])) ->  [5]
10 ->  (array([2]), array([0]), array([1])) ->  [9]
11 ->  (array([3]), array([0]), array([1])) ->  [13]
12 ->  (array([0]), array([1]), array([1])) ->  [3]
13 ->  (array([1]), array([1]), array([1])) ->  [7]
14 ->  (array([2]), array([1]), array([1])) ->  [11]
15 ->  (array([3]), array([1]), array([1])) ->  [15]`

As it can be seen above, The strategy for flatten() operation is different. Numpy flatten output pattern and my strategy gives different outputs. Desired output is numpy flatten output.
The question is how does numpy achieve this ?

How exactly is your array set up? I think the logic behind your row-transpose is correct, but for example threeD_Arr[1,0,0] is 8 and not 4 (3d_Arr is not a valid python variable name). So this does not seem to be an issue of how numpy uses transpose and flatten. This is also inconsistent between your depth- and row-tranpose. For depth-tranpose you have threeD_Arr[1,0,0] correctly as 8. — Oskar Hofmann
– Oskar Hofmann, Commented Jan 28, 2024 at 21:00
numpy uses shape and strides to make multidimensional arrays. transpose just makes a view with different strides (and shape). flatten is a copy to 1d, using the source strides to traverse the array's databuffer. You need to understand array storage. — hpaulj
– hpaulj, Commented Jan 28, 2024 at 23:02
@hpaulj Thank you. Do you know which mathematical formula Numpy traverses according to? — comp1023us
– comp1023us, Commented Jan 28, 2024 at 23:48

hpaulj · Accepted Answer · 2024-01-29 05:33:17Z

0

Your base arrays, with proper names:

In [827]: Arr1 = np.array([0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 15])
     ...: Arr3 = Arr1.reshape((2,2,4))

The key multidimension information:

In [828]: Arr3.base, Arr3.shape, Arr3.strides, Arr1.strides
Out[828]: 
(array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15]),
 (2, 2, 4),
 (32, 16, 4),
 (4,))

Step one element is done with 4 bytes. That's true for Arr1 and the columns (last dim) of Arr3. Step rows of Arr3 by 4 elements. Step planes (1st dim) by 32, i.e. 2 rows.

One of the your transposes:

In [830]: x=Arr3.transpose((2,1,0)); x.base, x.shape, x.strides
Out[830]: 
(array([ 0,  1,  2,  3,  4,  5,  6,  7,  8,  9, 10, 11, 12, 13, 14, 15]),
 (4, 2, 2),
 (4, 16, 32))

Same strides, but reversed order, as is the shape. It's a view, same Arr1 base.

In [831]: x.reshape(-1)
Out[831]: array([ 0,  8,  4, 12,  1,  9,  5, 13,  2, 10,  6, 14,  3, 11,  7, 15])

flatten/ravel is same as reshape to 1d. Display x to better visualize how it is flattened.

Making a (2,2,4) version:

In [834]: Arr3.transpose((1,0,2))
Out[834]: 
array([[[ 0,  1,  2,  3],
        [ 8,  9, 10, 11]],

       [[ 4,  5,  6,  7],
        [12, 13, 14, 15]]])

In [835]: Arr3.transpose((1,0,2)).flatten()
Out[835]: array([ 0,  1,  2,  3,  8,  9, 10, 11,  4,  5,  6,  7, 12, 13, 14, 15])

In [836]: Arr3.transpose((1,0,2)).strides
Out[836]: (16, 32, 4)

Still step 4 bytes, 1 element on the last dim, but 32 instead of 16 to step rows.

With the shape/strides formulation, you don't need a special formula for each transpose. The same stepping applies regardless of shape and strides.

edited Jan 29, 2024 at 5:33

answered Jan 29, 2024 at 1:44

hpaulj

233k14 gold badges260 silver badges392 bronze badges

Sign up to request clarification or add additional context in comments.

5 Comments

comp1023us Over a year ago

that is exactly what I wanted to learn.Thank you

comp1023us Over a year ago

hi @hpaulj. Considering that the linear index for 3d array is ``` idx = istride[0] + jstride[1] + k*stride[2]```. How to revert back to idx positions? It is more complicated.

hpaulj Over a year ago

The provided ravel/unravel take a order parameter. But it only takes C/F, and not all possible strides.

comp1023us Over a year ago

do you know the mathematical formula ?

hpaulj Over a year ago

I haven't worked out the details of unravel, at least not recently. I think it can be done with several repeats of modulus. It's not quite a staightforward as ravel.

Collectives™ on Stack Overflow

What mathematical or memory trick does numpy.flatten() use on numpy.transform?

1 Answer 1

5 Comments

Your Answer

Hot Network Questions

Collectives™ on Stack Overflow

1 Answer 1

5 Comments

Your Answer

Sign up or log in

Post as a guest

Related