index-of

APL-related discussions - a stream of APL consciousness.
Not sure where to start a discussion ? Here's the place to be
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 !

index-of

Postby Roger|Dyalog on Sun Apr 25, 2021 3:49 pm

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:

      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

Return to APL Chat

Who is online

Users browsing this forum: No registered users and 1 guest