From: Intransition <transfire@...>
Date: 2010-05-06T03:04:25+09:00
Subject: Re: Using array instead of hash and still have efficient 	cross-referencing



On May 5, 12:58 pm, Caleb Clausen <vikk...@gmail.com> wrote:
> On 5/5/10, Intransition <transf...@gmail.com> wrote:
>
> > Have a look at this class:
>
> >  http://github.com/proutils/lemon/blob/master/lib/lemon/snapshot.rb
>
> > I am storing a collection of OfModule instances in a hash (@modules)
> > indexed by the modules they correspond to. I'd rather just use an
> > array, since that is the basic intent. But I ran into difficulty when
> > implementing the #- method, which led me to use the hash instead.
>
> > Is there an efficient way to implement the #- method if @modules were
> > an array instead of a hash?
>
> So, am I understanding you correctly? The core problem in on line 77?
> You need an efficient way to tell if c has a particular module in it
> or not, so you can know whether to fool around with the methods it
> advertises?
>
> Why not create a temporary hash before the other.modules.each loop and
> use it to tell which modules are present.... something like (assuming
> you rewrite @modules as an array):
>
>   known_mods={}
>   c.modules.each{|mod| known_mods[mod.base]=mod }
>   other.modules.each do |ofmod|
>      if known_mods[ofmod.base]
>        ...
>      end
>   end
>
> Your Snapshot#- won't be as efficient as it is now, since you have to
> build that index up every time its called, but it should be a fairly
> minor performance degradation, I would think.

That was my first alternative idea too. I'm just not sure if it's
worth the efficiency trade-off. I was thinking there might be a way to
do it were the two arrays are sorted by name and then iterate down the
list popping off one or the other and merging base on <=>, but I
haven't worked it out yet. Even though there's two sorts involved it
should be just as fast I think.

> > Feel free to offer any other critiques of this code too, btw.
>
> I am curious. Why do you need this Snapshot class? And what does it do exactly?

Snapshot is used to records a list of all modules/classes and their
methods in the current process at a given moment. Eg.

  s1 = Snapshot.capture
  require 'foo'
  s2 = Snapshot.capture
  d = s2 - s1

now d will contain only the class/modules and methods that were
defined by loading 'foo'.

Lemon is unit testing framework that has a strict testcase<->class/
module and unit<->method correspondence. By taking a snapshot of the
system before and after a target library is loaded it can provide test
coverage information.