Exercise 5 Index   <<   >>


 

Modify function xiyC to use a different hash table size. What happens to the number of comparisons?






















 z←x (hn xiyCS) y;⎕io;h;hf;i;j;m;n;q
  ...
 :If 2=⎕nc'hn' ⋄ q←2*1+⌈2⍟m ⋄ :Else ⋄ q←hn m ⋄ :EndIf  
                                            ⍝ size of hash table
  ... 


_____________________

   n ← 1000×1 2 4 8 16 32

   {x y←↓?(2,⍵)⍴2e9 ⋄ x xiyC y}¨n
2006 3913 8014 13858 31127 59585

   {x y←↓?(2,⍵)⍴2e9 ⋄ x {2*1+⌈2⍟⍵}xiyCS y}¨n
2013 3823 7330 14979 30832 59427

   {x y←↓?(2,⍵)⍴2e9 ⋄ x {2*  ⌈2⍟⍵}xiyCS y}¨n
199934 1011089 3418309 4106918 18548069 29818911


   x←?14560⍴2e6 ⋄ x1←x,1
   y←?20000⍴2e6

   cmpx 'x⍳y' 'x1⍳y'
  x⍳y  → 3.41e¯3 |   0% ⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕⎕
* x1⍳y → 1.11e¯3 | -68% ⎕⎕⎕⎕⎕⎕⎕⎕⎕



From Hui, Index-Of, A 30-Year Quest, 2014.

 
table size key ∈ x key ∉ x
1.125
1.25
1.50
1.75
2.00
2.25
2.50
2.75
3.00
3.25
3.50
3.75
4.00
45.845
14.955
5.997
3.881
3.003
2.519
2.227
2.017
1.877
1.763
1.678
1.609
1.557
40.741
11.961
3.997
2.217
1.501
1.119
0.891
0.733
0.625
0.542
0.479
0.429
0.389
 

Average number of comparisons (key ∈ x)

 
 

See Knuth, Section 6.4, Figure 44, 1973.