Progressive Index Of
5 posts
• Page 1 of 1
Progressive Index Of
In the FinnAPL idiom library there is an entry for progressive-index-of that looks more or less like:
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?
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: 420
- Joined: Fri Oct 03, 2008 4:14 pm
Re: Progressive Index Of
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: 238
- Joined: Thu Jul 28, 2011 10:53 am
Re: Progressive Index Of
I believe the two versions in the FinnAPL Idiom Library remain the shortest solutions. FYI, the possible solutions are:
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
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: 238
- Joined: Thu Jul 28, 2011 10:53 am
Re: Progressive Index Of
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
{((⍴⍺)⍴⍋⍋⍺⍳⍺,⍵)⍳(⍴⍵)⍴⍋⍋⍺⍳⍵,⍺}
apply to arguments of all ranks (using major cells) as
{((≢⍺)↑⍋⍋⍺⍳⍺⍪⍵)⍳(≢⍵)↑⍋⍋⍺⍳⍵⍪⍺}
-
Adam|Dyalog - Posts: 135
- Joined: Thu Jun 25, 2015 1:13 pm
5 posts
• Page 1 of 1
Who is online
Users browsing this forum: No registered users and 1 guest
Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group