From: "Ara.T.Howard" <Ara.T.Howard@...>
Date: 2005-09-07T03:29:16+09:00
Subject: Re: Sorted arrays

On Wed, 7 Sep 2005, Hugh Sasse wrote:

> I found that the real time-killer was the CSV library itself.  This is fair
> enough: it takes account of all sorts of things like if the strings contain
> quotes and commas.   For the input I've been given this never happens, so it
> was much faster to use split to separate the fields -- by which I mean that
> several hours dropped to about 5 minutes.  This was sufficient speedup for
> my purposes.

this is exactly the approach i always use with csv: i split the first line,
remember the number of fields, and continue splitting - checking that the
numbe of fields is the same, iff it is not i parse the failed line using csv.
this approach is fast and handles certain conditions like quoted/escaped
commas.  it doesn't handle csv lines that span multiple lines... but the
speedup is worth it.

>> on a related note, i did some research into lookups in c using hahses
>> verses sorted arrays/bsearch; much to my suprise (as a computer scientist)
>> i found that, with the exception of HUGE (millions) of entries lookup by
>> bsearch was and order of magnitude faster than any hashing mechanism i
>> could find.  my
>
> I'm not too surprised (with this hindsight :-)) because the address
> calculations are probably cheaper than the full hashing
> we'd-have-to-cope-with-a-whole-bunch-of-hashable-things function.

exactly right.

>> test looked at cdb, hsearch, glib hashing functions, gperf and, for
>> bsearch, the c library bsearch.  profiling the different programs showed
>> that the reason the bsearch was faster was speedy was due to lack of
>> function calls and this is easy to imagine - flipping a pointer around
>> memory with only one stack frame is about as lightweight as one can get...
>> anyhow, my tests were very specific to my application but interesting
>> nonetheless - thought you'd be interested.
>
> Yes, and I do wonder (as someone who has not looked at the code to this
> extent) how much more speed we could wring out of the ruby implementations.

trees are pretty nice - good performance for everything - ruby could use one.

cheers.

-a
-- 
===============================================================================
| email :: ara [dot] t [dot] howard [at] noaa [dot] gov
| phone :: 303.497.6469
| Your life dwells amoung the causes of death
| Like a lamp standing in a strong breeze.  --Nagarjuna
===============================================================================