Progressive Index Of

[paulmansour]

In the FinnAPL idiom library there is an entry for progressive-index-of that looks more or less like:

      progressiveIndexOf←{
     ((⍋⍺⍳⍺,⍵)⍳⍳≢⍺)⍳(⍋⍺⍳⍵,⍺)⍳⍳≢⍵
 }

There is also an equally lengthy variation that uses double grade up and reshape.

Is this the state of the art for this now? Or is there a shorter solution?

[Roger|Dyalog]

There is a derivation in J in http://code.jsoftware.com/wiki/Essays/Progressive_Index-Of. I will provide a translation in Dyalog APL and comparative timings in a bit.

[Roger|Dyalog]

I believe the two versions in the FinnAPL Idiom Library remain the shortest solutions. FYI, the possible solutions are:

Code: Select all

pix0←{((⍋⍺⍳⍺,⍵)⍳⍳≢⍺)⍳(⍋⍺⍳⍵,⍺)⍳⍳≢⍵}
pix1←{((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)⍳(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺}
pix2←{n←≢⍺ ⋄ i←⍺⍳⍺,⍵ ⋄ ((⍋i)⍳⍳≢⍺)⍳(⍋n⌽i)⍳⍳≢⍵}
pix3←{n←≢⍺ ⋄ i←⍺⍳⍺,⍵ ⋄ ((⍴⍺)⍴⍋⍋i)⍳(⍴⍵)⍴⍋⍋n⌽i}

pix4←{
  k←⍺⍳⍺,⍵
  n←≢⍺
  r←⍋⍋i←n↑k ⋄ p←r-r[n↑k]
  s←⍋⍋j←n↓k ⋄ q←s-s[⍳⍨⍵]
  (⍺,⍪p)⍳(⍵,⍪q)
}


pix0 and pix1 are from FinnAPL. pix2 and pix3 are slightly faster versions of same. pix4 is translated from J.

In terms of speed, all of these benefit from the special code in the Dyalog APL interpreter for small-range data in ⍺⍳⍵ and ⍋⍵ and for permutations in ⍋⍵. (In ⍋⍋⍵ the argument of the leftmost ⍋ is a permutation.) The following benchmarks illustrate the point:

Code: Select all

      x←?1e6⍴1e6
      y←x ⋄ y[999999]←1e10  ⍝ x is small-range; y is not

      cmpx 'x⍳x' 'y⍳y'
  x⍳x → 9.31E¯3 |     0% ⎕⎕                           
  y⍳y → 1.29E¯1 | +1287% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
      cmpx '⍋x' '⍋y'
  ⍋x → 5.11E¯2 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕           
* ⍋y → 7.89E¯2 | +54% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕

      p←1e6?1e6
      q←p ⋄ q[999999]←⊃q  ⍝ p is a permutation; q is not; both are small-range

      cmpx '⍋p' '⍋q'
  ⍋p → 5.81E¯3 |    0% ⎕⎕⎕                           
* ⍋q → 5.74E¯2 | +887% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕


[paulmansour]

Thank you Roger.

[Adam|Dyalog]

Maybe worthy to note that with the relatively recent extensions of ⍳ and ↑ and ≢ we can make the classic expression

      {((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)⍳(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺}

apply to arguments of all ranks (using major cells) as

      {((≢⍺)↑⍋⍋⍺⍳⍺⍪⍵)⍳(≢⍵)↑⍋⍋⍺⍳⍵⍪⍺}