z←x xiy y;⎕io;h;hf;i;j;m;n;q
⍝ model of x⍳y using hashing; written to be easily translated into C
⎕io←0
hf←{123457×⍵} ⍝ hash function
n←≢y
m←≢x
q←2*1+⌈2⍟m ⍝ size of hash table
h←q⍴m ⍝ hash table; m means "free"
z←n⍴m ⍝ initialize to "not found"
:For i :In ⍳m ⍝ index for each x
j←q|hf x[i] ⍝ index into hash table
:While m>h[j] ⋄ :AndIf x[h[j]]≠x[i] ⍝ i.e. stop on finding m or an equal entry
j←q|1+j ⍝ the next hash table entry
:End
:If m=h[j] ⋄ h[j]←i ⋄ :End ⍝ new hash entry
:End
:For i :In ⍳n ⍝ index for each y
j←q|hf y[i] ⍝ where to start looking in hash table
:While m>h[j] ⋄ :AndIf x[h[j]]≠y[i] ⍝ i.e. stop on finding m or an equal entry
j←q|1+j ⍝ the next hash table entry
:End
z[i]←h[j] ⍝ here, either m=h[j] or x[h[j]]=y[i]
:End
|
xiy=: 4 : 0
NB. model of x i. y using hashing; written to be easily translated into C
hf=.123457&* NB. hash function
n=.#y
m=.#x
q=.2^1+>.2^.m NB. size of hash table
h=.q$m NB. hash table; m means "free"
z=.n$m NB. initialize to "not found"
for_i. i.m do. NB. index for each x
j=.q|hf i{x NB. index into hash table
while. (m>j{h)*.((j{h){ ::0:x)~:i{x do. NB. i.e. stop on finding m or an equal entry
j=.q|1+j NB. the next hash table entry
end.
if. m=j{h do. h=. i j}h end. NB. new hash entry
end.
for_i. i.n do. NB. index for each y
j=.q|hf i{y NB. where to start looking in hash table
while. (m>j{h)*.((j{h){ ::0:x)~:i{y do. NB. i.e. stop on finding m or an equal entry
j=.q|1+j NB. the next hash table entry
end.
z=. (j{h) i}z NB. here, either m=j{h or ((j{h){x)=i{y
end.
z
)
|
x←14 16 8 6 5 8 6 16 16 19 13 12 3 1 9 12 17
y←10 13 6 7 18 21 9 3 21 15 17 16 3 13 3 3 1 3 10 6
x ⍳ y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
x xiy y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
x (⍳ ≡ xiy) y
1
x ⍳ x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
x xiy x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
x (⍳ ≡ xiy) x
1
|
x=: 14 16 8 6 5 8 6 16 16 19 13 12 3 1 9 12 17
y=: 10 13 6 7 18 21 9 3 21 15 17 16 3 13 3 3 1 3 10 6
x i. y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
x xiy y
17 10 3 17 17 17 14 12 17 17 16 1 12 10 12 12 13 12 17 3
x (i. -: xiy) y
1
x i. x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
x xiy x
0 1 2 3 4 2 3 1 1 9 10 11 12 13 14 11 16
x (i. -: xiy) x
1
|
z←x xiySRloop y;⎕io;i;max;min;n;t
⍝ small-range version of x⍳y; written to be easily translated into C
⎕io←0
n←≢x
min←⌊/x,y
max←⌈/x,y
t←(1+max-min)⍴n ⍝ initialize table of indices
z←(≢y)⍴0 ⍝ eventual result
:For i :In ⌽⍳n ⋄ t[x[i]-min]←i ⋄ :EndFor ⍝ populate table of indices
:For i :In ⍳≢y ⋄ z[i]←t[y[i]-min] ⋄ :EndFor ⍝ read off index for each item of y
|
xiySRloop=: 4 : 0
NB. small-range version of x⍳y; written to be easily translated into C
n=. #x
min=. <./x,y
max=. >./x,y
t=. (1+max-min)$n NB. initialize table of indices
z=. (#y)$0 NB. eventual result
for_i. i.-n do. t=. i ((i{x)-min)}t end. NB. populate table of indices
for_i. i.#y do. z=. (((i{y)-min){t) i}z end. NB. read off index for each item of y
)
|