index-of
Forum rules
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !
This forum is for discussing APL-related issues. If you think that the subject is off-topic, then the Chat forum is probably a better place for your thoughts !
1 post
• Page 1 of 1
index-of
In a previous post on Membership, the game was to write a function f which does not use ∊, so that
(x∊y) ≡ x f y for non-empty integer vectors x and y. Here, the game is to write a function f which does not use ⍳, so that:
⎕io←0 is assumed. ⎕io delenda est!
Outer Product
This solution has the advantage of being rock solid, but the disadvantage of being O(n*2).
Index Table
This solution is blown out of the water if the range of values in ⍺ and ⍵ is large. Otherwise, it's pretty fast.
The 1+ in the expression b←(1+-/⌽r)⍴0 is an instance of the famous "off-by-1" pitfalls waiting to trap the unwary. One of my beefs with ⎕io is that it introduces opportunities for making an off-by-1 error where there was none.
A variant of it without the two ⌽ in the indexed assignment computes the index of the last occurrence. (⍳ and it compute the index of the first occurrence.)
Interval Index
This solution is O(n×⍟n). Some notes about its implementation:
Relaxed Requirements
It is known that the implementation of ⍳ has many special cases. (You can see this for yourself by running some benchmarks.) ⍳ on integer vector arguments is a special case, different from the special cases of ⍳ on arguments with k-byte (k≠4) major cells and ⍳ on floating point vectors. The following solutions do not use ⍳ on integer vectors.
(x∊y) ≡ x f y for non-empty integer vectors x and y. Here, the game is to write a function f which does not use ⍳, so that:
x ← ¯100 + ? 5678 ⍴ 220
y ← ¯8000 + ? 1234 ⍴ 18000
(x⍳y) ≡ x f y
1
⎕io←0 is assumed. ⎕io delenda est!
Outer Product
io ← {+/∧\⍵∘.≠⍺}
(x⍳y) ≡ x io y
1
This solution has the advantage of being rock solid, but the disadvantage of being O(n*2).
Index Table
⍝
it←{
r←(⌊/,⌈/)⍺,⍵
i←(1+-/⌽r)⍴≢⍺
i[⌽⍺-⊃r]←⌽⍳≢⍺
i[ ⍵-⊃r]
}
(x∊y) ≡ x it y
1
This solution is blown out of the water if the range of values in ⍺ and ⍵ is large. Otherwise, it's pretty fast.
The 1+ in the expression b←(1+-/⌽r)⍴0 is an instance of the famous "off-by-1" pitfalls waiting to trap the unwary. One of my beefs with ⎕io is that it introduces opportunities for making an off-by-1 error where there was none.
A variant of it without the two ⌽ in the indexed assignment computes the index of the last occurrence. (⍳ and it compute the index of the first occurrence.)
Interval Index
⍝
iv←{
x←{⍵[⍋⍵]}⍺
b←1,2≠/x
u←b/x
i←0⌈u⍸⍵
((≢⍺)×~c)+(b/⍋⍺)[i]×c←⍵=u[i]
}
(x∊y) ≡ x iv y
1
This solution is O(n×⍟n). Some notes about its implementation:
- Indices returned by ⍸ need to be mapped to the corresponding indices required by ⍳.
- In such mapping, indices for items of ⍵ less than ⌊/⍺, in the range (⌊/,⌈/) of ⍺ but not in ⍺, and greater than ⌈/⍺, need to be handled. That mapping is effected by the computations involving c.
- b can be computed as ≠x, but ≠⍵ is available only in Dyalog APL version 18.0 or later. Moreover, ≠x is less independent of ⍳ than 1,2≠/x.
- u can be computed as ∪x, but ∪ is less independent of ⍳ than b/x.
- x←{⍵[⍋⍵]}⍺ and ⍋⍺ can be replaced by x←⍺[i←⍋⍺]. The two computations are equally fast because {⍵[⍋⍵]} is an idiom.
Relaxed Requirements
It is known that the implementation of ⍳ has many special cases. (You can see this for yourself by running some benchmarks.) ⍳ on integer vector arguments is a special case, different from the special cases of ⍳ on arguments with k-byte (k≠4) major cells and ⍳ on floating point vectors. The following solutions do not use ⍳ on integer vectors.
ik ← {(⍺,⍪⍺)⍳(⍵,⍪⍵)}
if ← {(⍺+0.5)⍳(⍵+0.5)}
(x⍳y) ≡ x ik y
1
(x⍳y) ≡ x if y
1
- Roger|Dyalog
- Posts: 238
- Joined: Thu Jul 28, 2011 10:53 am
1 post
• 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