From: Robert Klemme <shortcutter@...>
Date: 2008-02-10T10:05:08+09:00
Subject: Re: Computer Science Problems

On 09.02.2008 23:53, Rick DeNatale wrote:
> On 2/9/08, Christopher Dicely <cmdicely@gmail.com> wrote:
>> On Feb 6, 2008 12:37 PM, Chad Perrin <perrin@apotheon.com> wrote:
>>> On Wed, Feb 06, 2008 at 10:47:51AM +0900, James Gray wrote:
>>>> A Ruby algorithms book would be really nice to have.  (I have a Perl
>>>> book like that I've used a fair bit.)
>>> I'd love to find a Ruby algorithms book, myself.
>> Interestingly, I just ran into this online book, _Data Structures and Algorithms
>> with Object-Oriented Design Patterns in Ruby_, at
>> http://www.brpreiss.com/books/opus8/
> 
> Once more into the breach dear friends!
> 
> http://groups.google.com/group/comp.lang.ruby/browse_thread/thread/5d50147449f0b532/67382c9359422e2f?lnk=gst&q=algorithm+books+ruby#67382c9359422e2f

You wrote:

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

This is actually not true: you need to compare apples with apples.  You 
cannot assign a C array beyond its boundaries (well, you *can* - 
sometimes).  So you would have to compare assignments within the 
preallocated size.  Same reasonings apply to the size in memory.  Fact 
is, you can use Ruby Arrays like C Arrays but most of the time you don't.

The fact that Ruby is interpreted and a completely different language 
than C does not invalidate complexity theory.  Keep in mind that O(n) is 
just an approximation really meaning "the effort grows asymptotically 
linear for n larger than a certain threshold" - or, slightly different, 
"the effort is O(n*X+C)" with X and C being constants.  Eventually 
runtime will be determined by the number of input parameters and 
duplication of this number will duplicate runtime.

So even though Ruby exposes different runtime characteristics it can be 
still used to study algorithms (actually I believe it is well suited 
because the clutterfree syntax eases focusing on the algorithmic part) 
and complexity theory.

Of course, this does not free us from measuring and performance tuning. 
  Often some implementations in Ruby are faster because the use library 
code implemented in C although in theory they should be slower.

You have one point though: often these ported books do not use features 
of the target language well and the code presented tends to look strange.

Kind regards

	robert