From: Ara.T.Howard@...
Date: 2005-04-23T12:54:35+09:00
Subject: Re: Question: Time efficiency of Array <<

On Sat, 23 Apr 2005, Saynatkari wrote:

> I think it is a bit of a stretch to call the following test 'real-world' :)
> That being said, Array does perform well.

true true.  by that i meant more that just big O analysis.

> Remember that an rb-tree is O(log n) for insertion, deletion _and_ search,
> and it can be treated as sparse.

oh i know - i use rbtree all the time and can't imagine why it's not in the
core.  on the other hand i also have bsearch code for Arrays that makes them
O(log n) for searching in most (pre-sorted) cases.

> As a sidenote, you can use Benchmark for convenient timing:
>
> require 'benchmark'
> Benchmark.bm do |bench|
>  # Setup
>  # ...
>  bench.report { # test1 }
>  bench.report { # test2 }
>  # ...
> end

i prefer to fork and (tho i forgot in this case) kill the CG - i like
factoring out threads and eliminating any possible memory clashes.

> In your test, it most likely suffers from allocating memory piecemeal rather
> than in chunks. Not sure how effectively one could preallocate for a tree.

yes that's true too.  i've done tests in the past comparing bdb, gperf, and
other hashing type look ups against a bsearch and found them to be quite a bit
slower.  on closer analysis it turned out that, although hashing is O(1), the
call stack is so much deeper for each search as compared to a non-recursive
bsearch that it predominates - i was suprised.

thanks for the info.

cheers.

-a
-- 
===============================================================================
| email   :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone   :: 303.497.6469
| although gold dust is precious, when it gets in your eyes, it obstructs
| your vision. --hsi-tang
===============================================================================