Exercise 3 Index   <<   >>


 

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% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕