[REBOL] Re: Rebol API to DyBASE
From: joel:neely:fedex at: 17-Dec-2003 11:25
Hi, Konstantin,
Maybe even worse?
Konstantin Knizhnik wrote:
> And as far as Rebol hash is also series, appending element to it
> cause a lot of reallocations, so complexity of insert operation
> seems to be linear (instead of constant). And if we use "insert
> hash" instead of "append hash" (not "insert tail hash"), then
> performance becomes really awful - copying all series element
> increase complexity to quadratic and insertion of 100000 integer
> elements in hash takes about half an hour (less then second in all
> other languages).
>
INSERTs into a "fresh" hash (created each time with MAKE HASH! []):
Appears to be increasing faster than quadratically!
# elts seconds ratio quad slowdown
10000 3.065
20000 25.817 8.423 4 2.106
30000 63.682 20.777 9 2.309
40000 123.417 40.267 16 2.517
APPENDs into a "growing" hash (not reconstructed between runs):
# elts seconds
40000 2.153
40000 6.69
40000 10.956
40000 15.453
40000 19.568
Here the number of appends in each stest is the same, but the time
complexity of managing a growing structure shows up; likewise, for
a simple block:
APPENDs into a "growing" block:
# elts seconds
40000 2.073
40000 6.529
40000 10.735
40000 14.962
40000 18.907
If we take out the reallocation-for-growth issues we get these:
APPENDs into a "growing" hash initialized with MAKE HASH! 200000
# elts seconds
40000 0.22
40000 0.251
40000 0.2
40000 0.33
40000 0.281
APPENDs into a "growing" block initialized with MAKE BLOCK! 200000
# elts seconds
40000 0.17
40000 0.17
40000 0.171
40000 0.191
40000 0.171
Preallocation of space (whenever possible ;-) is our friend!
-jn-
--
----------------------------------------------------------------------
Joel Neely joelDOTneelyATfedexDOTcom 901-263-4446
Enron Accountingg in a Nutshell: 1c=$0.01=($0.10)**2=(10c)**2=100c=$1
