Any standard way to unindex ? #30

Activity

1. mikolalysenko commented on Jul 12, 2016

   

   mikolalysenko

   on Jul 12, 2016

   Last edited by mikolalysenko

   Member

   More actions

   This isn't always well defined. For example if you had an ndarray with strides [0,0,0] then there would be an infinite number of inverses.

   Also some elements might not have inverses. For example if you have a stride [2] and offset 1 then you wouldn't be able to compute the unindex of any odd element.

   As a result unindex isn't a function.
2. peoro commented on Jul 12, 2016

   

   peoro

   on Jul 12, 2016

   Last edited by peoro

   Author

   More actions

   I wrote the original unindex for a very simple case: no offset, all the strides are positive, the last one is 1 etc.

   I'm not very familiar with the semantics of ndarray. Just out of curiousity, what does it mean for a stride to be 0? According to wikipedia an array cannot have a stride smaller than the element size.

   You're right about your first point and conclusion: if some strides are 0 index is non-injective, thus unindex cannot be a function. Moreover my implementation was broken for such cases: it returned an array filled with NaN.
   Besides the implementation of unindex was also broken for negative indices (which are supported by index ).

   I also agree that unindex shouldn't work for elements which don't belong to index's codomain. At the moment, though, index accepts real numbers as indices. For instance:

   • arr.index(0.5)=1 if arr.offset=0 ⋀ arr.stride=[2]
   • arr.index(0.5)=0.5 if arr.offset=0 ⋀ arr.stride=[1]

   I don't know whether you care about this function at all, but I tried to implement a semantically correct version anyways.

   I re-implemented unindex taking into account the previous points and making it:

   • return undefined for the values that make the unindex non-injective.
   • return NaN for the values outside of index's codomain when its domain is an array of integers.

   function absFloor(n)
   {
       return n >= 0 ? Math.floor(n) : Math.ceil(n);
   };
   function unindex(ndarr, n)
   {
       const result = new Array( ndarr.shape.length );
   
       n = n - ndarr.offset;
       ndarr.stride.forEach( (stride, i)=>{
           if( stride ) {
               if( i === result.length-1 && ! Number.isInteger(n / stride) ) {
                   /*
                    * TODO: is `NaN` what we want?
                    *       `index` seems to support fractions: if we returned `n/stride`, then `index(unindex(x)) === x || `, for this case.
                   result[i] = n / stride;
                    */
                   result[i] = NaN;
                   return;
               }
   
               result[i] = absFloor( n / stride );
               n %= stride;
           }
           else {
               /*
                * TODO: is `undefined` what we want?
                *       if we want `unindex(index(x)) === x` we should return a number.
               result[i] = 0;
                */
           }
       });
   
       return result;
   };
   

   This is an example of how it behaves:

   arr.shape=[5,7,13,17]; arr.stride=[1547,221,17,1]
   index(0,0,0,0)=0; unindex(0)=[0,0,0,0]; index(0,0,0,0)=0
   index(1,1,1,1)=1786; unindex(1786)=[1,1,1,1]; index(1,1,1,1)=1786
   index(1,2,3,4)=2044; unindex(2044)=[1,2,3,4]; index(1,2,3,4)=2044
   index(4,6,12,16)=7734; unindex(7734)=[4,6,12,16]; index(4,6,12,16)=7734
   index(10,6,12,16)=17016; unindex(17016)=[10,6,12,16]; index(10,6,12,16)=17016
   index(4,6,12,17)=7735; unindex(7735)=[5,0,0,0]; index(5,0,0,0)=7735 // ugh...
   
   arr.shape=[5,0,0,7,13,0,17]; arr.stride=[0,0,0,0,0,17,1]
   index(0,0,0,0,0,0,0)=100; unindex(100)=[,,,,,0,0]; index(,,,,,0,0)=NaN
   index(1,1,1,1,1,1,1)=118; unindex(118)=[,,,,,1,1]; index(,,,,,1,1)=NaN
   index(1,2,3,4,5,6,7)=209; unindex(209)=[,,,,,6,7]; index(,,,,,6,7)=NaN
   index(-1,-2,-3,-4,-5,-6,-7)=-9; unindex(-9)=[,,,,,-6,-7]; index(,,,,,-6,-7)=NaN
   
   arr.shape=[100]; arr.stride=[2]
   index(-3)=-5; unindex(-5)=[-3]; index(-3)=-5
   unindex(-4)=[NaN]; // note that index(-2.5)=-4
   index(-2)=-3; unindex(-3)=[-2]; index(-2)=-3
   unindex(-2)=[NaN]; // note that index(-1.5)=-2
   index(-1)=-1; unindex(-1)=[-1]; index(-1)=-1
   unindex(0)=[NaN]; // note that index(-0.5)=0
   index(0)=1; unindex(1)=[0]; index(0)=1
   unindex(2)=[NaN]; // note that index(0.5)=2
   index(1)=3; unindex(3)=[1]; index(1)=3
   unindex(4)=[NaN]; // note that index(1.5)=4
   index(2)=5; unindex(5)=[2]; index(2)=5
   unindex(6)=[NaN]; // note that index(2.5)=6
   index(3)=7; unindex(7)=[3]; index(3)=7
   unindex(8)=[NaN]; // note that index(3.5)=8
   
   arr.shape=[100]; arr.stride=[-2]
   index(-3)=8; unindex(8)=[-3]; index(-3)=8
   unindex(7)=[NaN]; // note that index(-2.5)=7
   index(-2)=6; unindex(6)=[-2]; index(-2)=6
   unindex(5)=[NaN]; // note that index(-1.5)=5
   index(-1)=4; unindex(4)=[-1]; index(-1)=4
   unindex(3)=[NaN]; // note that index(-0.5)=3
   index(0)=2; unindex(2)=[0]; index(0)=2
   unindex(1)=[NaN]; // note that index(0.5)=1
   index(1)=0; unindex(0)=[1]; index(1)=0
   unindex(-1)=[NaN]; // note that index(1.5)=-1
   index(2)=-2; unindex(-2)=[2]; index(2)=-2
   unindex(-3)=[NaN]; // note that index(2.5)=-3
   index(3)=-4; unindex(-4)=[3]; index(3)=-4
   unindex(-5)=[NaN]; // note that index(3.5)=-5
   

   If we want a semantically perfect version of index and unindex, and having that unindex(index(x))=x ⋁ ( isNaN(index(x)) ⋀ ∀y, unindex(y)≠x ), I believe that we should modify index(i,j,...) so that it:

   • fails if i,j,... ∉ ℤ (or maybe even ℕ?),
   • fails if at least one of the indices is larger than the size of its dimension (and maybe smaller than 0).
   • accepts anything (or at least undefined) for the indices whose stride is 0.