Consider the following model of x⍳y using hashing.
(Also at
http://www.jsoftware.com/papers/APLHashingModel.htm .)
Find integer
vectors x and y
such that x xiy y takes less than one-tenth the time
as that for the model from exercise 0.
z←x xiy y;⎕io;h;hf;i;j;m;n;q
⍝ model of x⍳y using hashing; written for easy translation 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 in hash table
:While m>h[j] ⋄ :AndIf x[h[j]]≠x[i] ⍝ stop on finding m or =
j←q|1+j ⍝ the next index
: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] ⍝ index in hash table
:While m>h[j] ⋄ :AndIf x[h[j]]≠y[i] ⍝ stop on finding m or =
j←q|1+j ⍝ the next index
:End
z[i]←h[j] ⍝ m=h[j] or x[h[j]]=y[i]
:End
x y←↓?2 600⍴2e9
cmpx 'x xiy y' 'x I y'
x xiy y → 5.28e¯3 | 0% ⎕⎕
x I y → 5.77e¯2 | +992% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
|