Exercise 7 Index   <<   >>


 

Write xix , an adaptation of xiy , to exploit the case where the left and right arguments are the same. Run some benchmarks comparing xix x and x xiy y .






















 z←xix x;⎕io;h;hf;i;j;m;q
⍝ model of x⍳x using hashing; written for easy translation into C

 ⎕io←0
 hf←{123457×⍵}                            ⍝ hash function
 m←≢x
 q←2*1+⌈2⍟m                               ⍝ size of hash table
 h←q⍴m                                    ⍝ hash table; m means "free"
 z←m⍴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]  ⍝ stop on finding m or =
         j←q|1+j                          ⍝ the next hash table entry
     :End
     :If m=h[j] ⋄ h[j]←i ⋄ :End           ⍝ new hash continuation
     z[i]←h[j]
 :End


_____________________

   n ← 1000 × 1 2 4 8 16 32

   {x←?⍵⍴2e9 ⋄ ÷/1 1 cmpx 'x xiy x' 'xix x'}¨n
1.82698 1.81551 1.77036 1.81175 1.77618 1.77618

   {y←0+x←?⍵⍴2e9 ⋄ ÷/1 1 cmpx 'x⍳x' 'x⍳y'}¨n
1.00061 1.00882 0.990444 1 1 0.984215