2007/12/18, Christophe Mckeon <chromatophore / gmail.com>:
> ok here's the scoop. i have a collection of hashes all with an arbitrary
> number of symbolic keys pointing to arbitrary objects. i have a template
> hash also containing symbol keys pointing to 'matching objects', i.e.
> objects to be matched with the objects in the aforementioned collection,
> and i want to pull out the first match. an example:
>
> # please don't psychoanalyze the below :)

You are crazy.  Please contact a doctor ASAP. Oh, sorry. :-)

> collection = [
>   { :foo => 'python', :bar => 'php', :x => 69 },
>   { :foo => 'scheme', :mama => 'ruby', :papa => 'C' },
>   { :x => 386 },
>   { :mama => 'ruby', :papa => 'simula', :lil_bro => 'fortran' }
> ]
>
> template1 = { :mama => 'ruby', :papa => 'C' }
> template2 = { :x => Numeric }
>
> match_first(template1, collection)
> # should return: { :foo => 'scheme', :mama => 'ruby', :papa => 'C' }
> match_all(template2, collection)
> # should return: [{:x => 386 }, {:foo => 'python', :bar => 'php', :x =>
> 69}]
>
> so obviously === is being used internally as is evidenced by Numeric in
> template2, but what kind of datastructures/algorithms should i be
> looking at for the most efficient (time-wise) implementation, keeping in
> mind, there may be many hashes in the collection and those hashes are
> generally not very large, i.e. contain few key/value pairs. i'm not too
> savy on the taxonomy of algorithms so any pointers to what i should be
> looking at to read up on would be appreciated.
>
> my potentially naive solution is something like the following (in full
> color http://pastie.caboo.se/130033):

<snip/>

> thanks for reading this far!

I think you are on a pretty good way.  Here's what I would do differently:

1. Do no recreate all those candidate collections for every
match_first call. Instead, stuff everything into a class and provide a
method that will create an /index/ of the data (see 2).

2. I would use Hashes to store your indexes, i.e. instead of creating
candidates all over again, create them once (see 1) and keep them
there.

Kind regards

robert

-- 
use.inject do |as, often| as.you_can - without end