From: Christophe Mckeon <chromatophore@...>
Date: 2007-12-19T00:54:54+09:00
Subject: Database-like Algorithmic Problem

hi all,

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 :)
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):

require 'set'

@collection = {}

def add hash
  hash.each do |key,value|
    (@collection[key] ||= Set.new) << hash
  end
end

def candidates template
  sets = []
  template.keys.each do |key|
    sets << @collection[key] if @collection.include? key
  end
  if sets.empty?
    return sets
  else
    return sets.inject(sets.pop) do |intersection, set|
      intersection & set
    end
  end
end

def match template, hash
  template.each do |key, match|
    return false unless match === hash[key]
  end
  return true
end

def match_first template
  candidates(template).each do |hash|
    return hash if match(template, hash)
  end
  return nil
end

def match_all template
  return candidates(template).select do |hash|
    match(template, hash)
  end
end

[
  { :foo => 'python', :bar => 'php', :x => 69 },
  { :foo => 'scheme', :mama => 'ruby', :papa => 'C' },
  { :x => 386, :papa => 'clause' },
  { :mama => 'ruby', :papa => 'simula', :lil_bro => 'fortran' },
  { :mama => 1946, :boo => 'far', :x => 'x'}
].each do |hash|
  add hash
end

puts match_first({ :mama => 'ruby', :papa => 'C' }).inspect
puts match_all({:foo => String}).inspect

thanks for reading this far!
_c
-- 
Posted via http://www.ruby-forum.com/.