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.
|
|