## 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 !

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 0 guests

Powered by phpBB © 2000, 2002, 2005, 2007 phpBB Group