interval index

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 !

interval index

Postby Roger|Dyalog on Thu Apr 29, 2021 4:33 am

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

      (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: 231
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