From: Robert Klemme <bob.news@...>
Date: 2003-05-28T01:49:53+09:00
Subject: Re: Binary Tree vs. Hash


"ahoward" <ahoward@fsl.noaa.gov> schrieb im Newsbeitrag
news:Pine.LNX.4.53.0305271517520.28367@eli.fsl.noaa.gov...
> On Tue, 27 May 2003, Robert Klemme wrote:
>
> > IMHO that's overly complicating Array. An Array is simply a sequence
of
> > items.  Period.
>
> on paper - sure.  but in reality we have:
>
>
>   [ ] new & * + -- << <=> == === [ ] [ ]= | assoc at clear
>   collect collect! compact compact! concat delete delete_at
>   delete_if each each_index empty? eql? fill first flatten
>   flatten! include? index indexes indices join last length map!
>   nitems pack pop push rassoc reject! replace reverse reverse!
>   reverse_each rindex shift size slice slice! sort sort! to_a
>   to_ary to_s uniq uniq! unshift
>
>   mixins
>   Enumerable:
>     collect, detect, each_with_index, entries,
>     find, find_all, grep, include?, map, max,
>     member?, min, reject, select, sort, to_a
>
>
> *much* more than a sequence of items.

Well, yes.  But all these actions don't introduce a new class invariant.
Note, that methods sort and sort! must be invoked explicitely.  Under the
hood it remains a "sequence of things" and it is not a "sorted sequence of
things".  This is a major difference although it might not look that way
on first glance.  If you consider, how all modifying methods must change
you'll might easier see the impact of this difference.  Having all methods
of this kind check a flag is commonly considered bad practice.  I'd favour
an extra type, i.e. sub class or proxy that delegates.

Apart from that, since instances of a class are not comparable by default
(i.e. implement <=>) the SortedArray either would have to ensure that only
comparable elements go into the container or make up an artifical
comparison.  This checks would have to be employed, if the sorted flag
changes from false to true.  Then what do you do?  Kick those out that
don't match?  If you make the flag read only, i.e. only set during
construction, you are better off having a different type for this.

IMHO a flag like you suggested is not sufficient: maybe you want to apply
different sorting criteria for the same type.  Java solved this elegantly
by defining an interface Comparator that performs the comparison
operation.  You can then create a sorted collection either with default
sorting (uses Comparable, same in ruby) or you implement a comparator on
your own.  This is the most modular, flexible and clean solution.

> what would be the issue if Enumerable was optimized for containers, like
> Array, which could support random access and binary searches?  the same
> methods would exist - they would simply be faster.  admittedly this is
less
> 'general' but optimization for such a heavily used container as the
Array
> makes sense IHMO, espcially when it could be done in such a way to be
> completely backward compatible while giving a speed increase to
practially
> every ruby program ever written...

I have several objections:

 - The speed increase would not be there automatically, but one would have
to explicitely set the sorting flag; so there's no automatic performance
increase.

 - You can't use sorting by default because a lot of applications rely on
the data *not* being sorted behind the scenes and

 - there's a performance penalty to pay for sorting, which you clearly
don't want if you don't need sorted data.

 - You suggested optimization is the other way round: Enumerable is the
general implementation just requiring an implementation of each.  All
containers that can do include? and others better than the default
implementation override those methods by their own implementation.

Sorry, if I'm beeing a bit massive (lots of text), but I think there are
serious reasons to not change Array to support automated internal sorting.
However, introducing such a type is surely not a bad idea.  Maybe we
simply adopt the pattern from Java.  I think, they did a good design job
on this.

Regards

    robert