Hi,
> When you test the hash function, your timing function (time-blk)
loops over
> the block:
(...)
> This block includes the CREATION of the hash and INSERTING items
into the
> hash. Certainly creating a hash and inserting items into the
hash is not
> the same thing as searching in a hash and the time required to
CREATE the
> data structure and INSERT items into the data structure should
not be part
> of the value reported for the time required to SEARCH in the
data structure.
>
> Inserting an element into a hash is by nature of hashing
algorithms far
> more time consuming than inserting an element into a block.
Hashes are
> optimized for locating an element at the penalty of consuming
more time for
> insertion. To correctly identify the time it takes to locate an
element in
> a hash, you must separate the insertion of the element into the
hash from
> the time you calculate to retrieve the element in the hash.
>
> If you separate insertion from the search in a hash, you must do
the same
> for the blocks as well. Only then will you be able to compare
values that
> reflect how long it takes to SEARCH in the different series
types you are
> testing!
I was testing the usability of Hash! datatype for memoizing
functions, the code is quite typical. The results show, that Hash!
datatype is not suitable for that purpose.
I tested a "pure searching" code too, see the results and the
code:
Test size: 4096
Block/find time: 7.8125E-3 not found
Block/bfind time: 9.765625E-4 not found
Hash/find time: 6.591796875E-3 not found
Test size: 8192
Block/find time: 1.5625E-2 not found
Block/bfind time: 1.220703125E-3 not found
Hash/find time: 1.5625E-2 not found
Test size: 16384
Block/find time: 2.34375E-2 not found
Block/bfind time: 1.28173828125E-3 not found
Hash/find time: 2.587890625E-2 not found
include %timblk.r
n: to integer! ask "Test size: "
m: 10 * n ; random number range
prin "Block/find time: "
random/seed 1
c: 0
blk: copy []
repeat i n [
d: random m
append blk d
]
k: random m
prin time-block [
l: find blk k
] 0.05
either l [
prin " index: "
print index? l
] [
print " not found"
]
prin "Block/bfind time: "
random/seed 1
c: 0
blk: copy []
repeat i n [
d: random m
append blk d
]
sort blk
k: random m
prin time-block [
l: bfind blk k
] 0.05
either (pick blk l) = k [
prin " index: "
print l
] [
print " not found"
]
prin "Hash/find time: "
random/seed 1
c: 0
blk: copy []
repeat i n [
d: random m
append blk d
]
blk: make hash! blk
k: random m
prin time-block [
l: find blk k
] 0.05
either l [
prin " index: "
print index? l
] [
print " not found"
]
