## [REBOL] Re: hash questions

### From: larry:ecotope at: 8-Jan-2002 20:30

Hi Holger, Thanks for your response. It is good that hash works for so many REBOL datatypes. I note that with a few exceptions the hashable values are of type any-string, any-word, or the so-called simple types in which the data is included in the REBOL value. I have not had a chance to test all of these possiblities. However I question whether decimal keys in a block of consecutive key-value pairs are hashable, or more precisely, the benefit of using a hash with decimal keys. I ran the following test script: REBOL [] clk: func [][now/time/precise] ;set up blocks and hashes with block values ;and either integer or decimal keys ;measure the time to find the last key in the block b1: make block! 10000 b2: make block! 10000 repeat j 10000 [ append b1 j append/only b1 reduce [j] ] repeat j 10000 [ append b2 to-decimal j append/only b2 reduce [j] ] h1: to-hash b1 h2: to-hash b2 t1: clk loop 1000 [find b1 10000] t1: clk - t1 t2: clk loop 1000 [find b2 10000.0] t2: clk - t2 print ["Find integer key in block:" t1] print ["Find decimal key in block:" t2] t1: clk loop 1000 [find h1 10000] t1: clk - t1 t2: clk loop 1000 [find h2 10000.0] t2: clk - t2 print ["Find integer key in hash:" t1] print ["Find decimal key in hash:" t2] ;end of code Here are my results for the current versions of core and view (450 MHz PII): system/version 2.5.0.3.1 Find integer key in block: 0:00:02.04 Find decimal key in block: 0:00:13.4 Find integer key in hash: 0:00 Find decimal key in hash: 0:00:14.66 system/version 1.2.1.3.1 Find integer key in block: 0:00:01.92 Find decimal key in block: 0:00:15.27 Find integer key in hash: 0:00 Find decimal key in hash: 0:00:16.59 It is interesting that the search for a decimal key takes 6 to 8 times longer than for an integer key. I noticed that if I change the code so that the decimal search keys are of the form j / 3 instead of to-decimal j, and then search for 10000 / 3 the times are much better, especially for the hash: Find integer key in block: 0:00:02.03 Find decimal key in block: 0:00:09.23 Find integer key in hash: 0:00 Find decimal key in hash: 0:00:04.78 This suggests that comparing decimals which are equal to integers (1000 and 1000.0) requires some extra time. But this does not seem to be confirmed by a direct test:>> a: 10000== 10000>> b: 10000.0== 10000>> c: 10000 / 3== 3333.33333333333>> t: clk loop 5'000'000 [equal? a a] clk - t== 0:00:06.26>> t: clk loop 5'000'000 [equal? b b] clk - t== 0:00:09.89>> t: clk loop 5'000'000 [equal? c c] clk - t== 0:00:10.11>From the original example with decimal keys equal to integers, it appearsthat using hash with decimal keys actually takes more time for FIND than when using a block. But with integer keys the hash makes FIND so fast that the loop iterations have to go up by a factor of 100 inorder to get a measurable time. I also see this:>> t: clk loop 1000 [find h2 10000.0] clk - t== 0:00:14.01>> t: clk loop 1000 [find b2 10000.0] clk - t== 0:00:14.83>> t: clk loop 1000 [find h2 5000.0] clk - t== 0:00:14.11>> t: clk loop 1000 [find b2 5000.0] clk - t== 0:00:07.36 ;twice as fast as hash It does seem that the hashes with decimal keys take a time independent of the location of the search key in the block while FIND on a block searches linearly from the beginning and thus results in half the time to find a key half-way through the block. Constant time is certainly a hallmark of a hash, but the hash time for FIND is so slow for decimal keys equal to integers that searching for a random key will take on average almost twice as long as when using a block. For the more representative j / 3 case, the times for block and hash will be comparable for a random search key, while the worst case will be a factor of 2 better for the hash. I guess I don't fully understand REBOL hashes, particularly with respect to decimal keys. Of the datatypes you mention, which will fail to display the large speed increase we expect from a hash (and which we see for string and integer keys) as opposed to a block ? Any comments are welcome. -Larry