Progressive Index Of

General APL language issues

Progressive Index Of

Postby paulmansour on Wed Jul 18, 2018 11:42 am

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?
paulmansour
 
Posts: 276
Joined: Fri Oct 03, 2008 4:14 pm

Re: Progressive Index Of

Postby Roger|Dyalog on Wed Jul 18, 2018 4:07 pm

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
 
Posts: 133
Joined: Thu Jul 28, 2011 10:53 am

Re: Progressive Index Of

Postby Roger|Dyalog on Thu Jul 19, 2018 1:09 am

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% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
Roger|Dyalog
 
Posts: 133
Joined: Thu Jul 28, 2011 10:53 am

Re: Progressive Index Of

Postby paulmansour on Fri Jul 20, 2018 7:31 pm

Thank you Roger.
paulmansour
 
Posts: 276
Joined: Fri Oct 03, 2008 4:14 pm

Re: Progressive Index Of

Postby Adam|Dyalog on Sun Jul 22, 2018 10:58 am

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
      {((≢⍺)↑⍋⍋⍺⍳⍺⍪⍵)⍳(≢⍵)↑⍋⍋⍺⍳⍵⍪⍺}
User avatar
Adam|Dyalog
 
Posts: 40
Joined: Thu Jun 25, 2015 1:13 pm


Return to Language

Who is online

Users browsing this forum: No registered users and 1 guest