## interval index

**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**### interval index

In previous posts, Membership and Index-Of, the game was to write functions f and g such that

for non-empty integer vectors x and y, where f does not use ∊ and g does not use ⍳. Here, the game is to write a function h which does not use ⍸, so that for non-empty integer vectors x and y:

⎕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).

If the arguments were floating point numbers, ⎕ct←0 would be necessary because ⍸ is defined on exact comparisons.

Index Table

This solution is blown out of the water if the range of values in ⍺ is large. Otherwise, it's pretty fast.

The 1+ in the expression i←(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.

Grade

This solution is O(n) because ⍋ is O(n).

The algorithm first appeared as the function "classify" in §1.2 of Some Uses of { and }, 1987 and also in §14 of A History of APL in 50 Functions, 2016.

The unusual construct i⊣i[i]←blah can be made expressed in another way. Since i, being the result of ⍋, is (am?) a permutation, i⊣i[i]←⍳≢i is equivalent to ⍋i. That is, i[i]←blah assigns the items in the order ⍋i and is equivalent to blah[⍋i]. Therefore, ivg is equivalent to ivg1 (although ivg is a bit faster):

(x∊y) ≡ x f y

(x⍳y) ≡ x g y

for non-empty integer vectors x and y, where f does not use ∊ and g does not use ⍳. Here, the game is to write a function h which does not use ⍸, so that for non-empty integer vectors x and y:

x ← {⍵[⍋⍵]} ¯100 + ? 5678 ⍴ 220

y ← ¯200 + ? 1234 ⍴ 440

(x⍸y) ≡ x h y

1

⎕io←0 is assumed. ⎕io delenda est!

Outer Product

ivo ← {¯1++/⍵∘.≥⍺}

(x⍸y) ≡ x ivo y

1

This solution has the advantage of being rock solid, but the disadvantage of being O(n*2).

If the arguments were floating point numbers, ⎕ct←0 would be necessary because ⍸ is defined on exact comparisons.

Index Table

⍝

ivt←{

r←(⌊/,⌈/)⍺

i←(1+-/⌽r)⍴0

i[⍺-⊃r]+←1

i←¯1++\i

(b×i[0⌈(⍵⌊⊃⌽r)-⊃r])-~b←⍵≥⊃r

}

(x⍸y) ≡ x ivt y

1

This solution is blown out of the water if the range of values in ⍺ is large. Otherwise, it's pretty fast.

The 1+ in the expression i←(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.

Grade

ivg ← {¯1+(≢⍺)↓i⊣i[i]←+\(≢⍺)>i←⍋⍺⍪⍵}

(x⍸y) ≡ x ivg y

1

This solution is O(n) because ⍋ is O(n).

The algorithm first appeared as the function "classify" in §1.2 of Some Uses of { and }, 1987 and also in §14 of A History of APL in 50 Functions, 2016.

The unusual construct i⊣i[i]←blah can be made expressed in another way. Since i, being the result of ⍋, is (am?) a permutation, i⊣i[i]←⍳≢i is equivalent to ⍋i. That is, i[i]←blah assigns the items in the order ⍋i and is equivalent to blah[⍋i]. Therefore, ivg is equivalent to ivg1 (although ivg is a bit faster):

ivg1 ← {¯1+(≢⍺)↓(+\i<≢⍺)[⍋i←⍋⍺⍪⍵]}

(x⍸y) ≡ x ivg1 y

1

- Roger|Dyalog
**Posts:**232**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