<<   >>

31. Inverted Table Index-Of

(⍉↑x⍳¨x) ⍳ (⍉↑x⍳¨y)

A table is a set of values organized into rows and columns. The rows are records. Values in a column have the same type and shape. A table has a specified number of columns but can have any number of rows. The extended index-of on tables finds record indices.

   tx                   ty                    tx ⍳ ty
┌──────┬─┬───┬──┐    ┌──────┬─┬───┬──┐     3 1 5 2 5 5
│John  │M│USA│26│    │Min   │F│CN │17│
├──────┼─┼───┼──┤    ├──────┼─┼───┼──┤        tx ⍳ tx
│Mary  │F│UK │24│    │Mary  │F│UK │24│     0 1 2 3 4
├──────┼─┼───┼──┤    ├──────┼─┼───┼──┤
│Monika│F│DE │31│    │John  │M│UK │26│        ty ⍳ ty
├──────┼─┼───┼──┤    ├──────┼─┼───┼──┤     0 1 2 3 4 4
│Min   │F│CN │17│    │Monika│F│DE │31│
├──────┼─┼───┼──┤    ├──────┼─┼───┼──┤
│Max   │M│IT │29│    │Mesut │M│DE │24│
└──────┴─┴───┴──┘    ├──────┼─┼───┼──┤
                     │Mesut │M│DE │24│
                     └──────┴─┴───┴──┘

An inverted table is a table with the values of a column collected together. Comma-bar each (⍪¨) applied to an inverted table makes it “look” more like a table. And of course the columns have the same tally (≢). A table can be readily inverted and vice versa.

   x
┌──────┬─────┬───┬──────────────┐
│John  │MFFFM│USA│26 24 31 17 29│
│Mary  │     │UK │              │
│Monika│     │DE │              │
│Min   │     │CN │              │
│Max   │     │IT │              │
└──────┴─────┴───┴──────────────┘
   ⍪¨x                     ≢¨x      
┌──────┬─┬───┬──┐       5 5 5 5
│John  │M│USA│26│
│Mary  │F│UK │24│
│Monika│F│DE │31│
│Min   │F│CN │17│
│Max   │M│IT │29│
└──────┴─┴───┴──┘

   invert ← {↑¨↓⍉⍵}  
   vert   ← {⍉↑⊂⍤¯1¨⍵}
            
   x  ≡ invert tx
1
   tx ≡ vert x
1

A table has array overhead per element. An inverted table has array overhead per column. The difference that this makes becomes apparent when you have a sufficiently large number of rows. The other advantage of an inverted table is that column access is much faster.

An important computation is x index_of y where x and y are compatible inverted tables. Obviously, it can not be just x⍳y . The computation obtains by first “verting” the arguments (un-inverting the tables) and then applying ⍳ , but often there is not enough space for that.

   ⍪¨x                   ⍪¨y
┌──────┬─┬───┬──┐     ┌──────┬─┬───┬──┐
│John  │M│USA│26│     │Min   │F│CN │17│
│Mary  │F│UK │24│     │Mary  │F│UK │24│
│Monika│F│DE │31│     │John  │M│UK │26│
│Min   │F│CN │17│     │Monika│F│DE │31│
│Max   │M│IT │29│     │Mesut │M│DE │24│
└──────┴─┴───┴──┘     │Mesut │M│DE │24│
                      └──────┴─┴───┴──┘
   x ⍳ y
4 4 4 4

   (vert x) ⍳ (vert y)
3 1 5 2 5 5

We derive a more efficient computation of index-of on inverted tables:

(vert x) ⍳ (vert y)  (a)
({⍉↑⊂⍤¯1¨⍵}x) ⍳ ({⍉↑⊂⍤¯1¨⍵}y)   (b)
(⍉↑⊂⍤¯1¨x) ⍳ (⍉↑⊂⍤¯1¨y)  (c)
(⍉↑x⍳¨x) ⍳ (⍉↑x⍳¨y)  (d)

(a)   The indices obtain by first uninverting the tables, that is, by first applying vert .
(b) Replace vert by its definition.
(c) Replace the D-fn by its definition. We see that ⊂⍤¯1 plays a major role. ⊂⍤¯1 encloses, or alternatively computes a scalar representation.
(d) For purposes of index-of x⍳¨x and x⍳¨y have the same information as ⊂⍤¯1¨x and ⊂⍤¯1¨y , but are much more efficient representations (small integers v the data itself).

Point (d) illustrated on column 0:

   ⊂⍤¯1⊢x0←0⊃x
┌──────┬──────┬──────┬──────┬──────┐
│John  │Mary  │Monika│Min   │Max   │
└──────┴──────┴──────┴──────┴──────┘
   x0 ⍳ x0
0 1 2 3 4

   ⊂⍤¯1⊢y0←0⊃y
┌──────┬──────┬──────┬──────┬──────┬──────┐
│Min   │Mary  │John  │Monika│Mesut │Mesut │
└──────┴──────┴──────┴──────┴──────┴──────┘
   x0 ⍳ y0
3 1 0 2 5 5

That is, the function {(⍉↑⍺⍳¨⍺)⍳(⍉↑⍺⍳¨⍵)} computes index-of on inverted tables.

I believe that in another language a derivation such as the one above would be very long (in part because the program would be very long), possibly impractically long.


Appeared in J in [94] and in APL in [95, 96].