Exercise 4 Index   <<   >>


 

Write xiyC , an adaptation of function xiy , to return the number of comparisons involving x or y .

















 z←x xiyC 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←0# comparisons involving x or y

 :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] ⊣ z+←1
     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] ⊣ z+←1
     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,⍵)⍴2e9 ⋄ x xiyC y}¨1000×1 2 4 8 16 32
2006 3913 8014 13858 31127 59585