From: Rick DeNatale <rick.denatale@...>
Date: 2007-05-13T05:02:11+09:00
Subject: Algorithm books for Ruby (was Re: Object-oriented solution to Tower of Hanoi)

On 5/12/07, Martin DeMello <martindemello@gmail.com> wrote:
> On 5/12/07, Rich Morin <rdm@cfcl.com> wrote:
> > > Robert Klemme wrote:
> > >> I suggest you also read a decent book on data structures and algorithms
> > >> (Knut, Sedgewick or the like).
> >
> > I find Sedgewick to be a lot more useful than Knuth, because
> > he uses high-level (well, higher than assembly) code.  I'd
> > love to see a good book on algorithms for Ruby (hint!).
>
> give http://www.brpreiss.com/books/opus8/ a look.

Thanks for that pointer Martin.

I've started reading it, and I have to say that I'm feeling the need
for a salt shaker for liberal use.

My first hint that this might not be the best approach for Ruby was
the large number of versions for other languages.  I'm afraid that
this looks like YAPB (yet another ported book).  It seems to treat
Ruby as if it were C.

In the algorithm analysis section he describes various axioms, which
appear to be more beleivable for a C program than for Ruby. Constant
variable access? constant method call overhead?  array access
equivalent to a certain number of ruby operations?  These appear to be
based on thought experiments rather than actual measurements of the
ruby implementation.

'm a little suspicious that this might be a case of using the axioms
of plane geometry when the subject is spherical geometry.

For example, I'm pretty sure that these two snippets will have
different timing profiles

a = Array.new(300)
a[200] = 1

and

a = Array.new(190)
a[200] = 1

Since Ruby arrays are dynamically sized, the second needs to
reallocate and copy the contents.

So in these cases certain array stores might actually be O(n) where n
is the length of the array rather than O(1).

Also the analysis of the space taken up by an array is suspect. In
general Ruby arrays have a heuristically sized storage area which
grows and shrinks automatically. The size is not always a function of
the length of the array, the implementation keeps both a length, which
is what the Ruby programmer sees, and a capacity which is the actual
size of the currently allocated storage area.

When we get to the fundamental data structures part, we see him
monkeypatching Array, to provide for different index origins.

The main portion of the book seems to be building an alternative to
the ruby library.

I'm not sure I'd recommend this to someone as a way to improve their
skills with Ruby.

I think that a more useful work would do some analysis of the
implementation of the core ruby classes like Array and Hash.

But that's just my opinion.

I was amused by some of the google ads I saw while browsing the book.
One was for arborists in my vicinity.  I guess it had something to do
with the book talking about trees.


-- 
Rick DeNatale

My blog on Ruby
http://talklikeaduck.denhaven2.com/