[FIX][ENH] SortedCollection robustness & speedup

Florin X Mateoc mateoc_florin at jpmorgan.com
Mon May 1 14:06:14 UTC 2000


Hi Andres,

Have you tried the sample code ? For me it gives the correct result, as it
should. The only thing that Georg did here was to add the "^aCollection" at the
end, which makes it consistent with the way the "adding" protocol behaves. The
addition part of the method was and still is correct (well, I don't know what
image you are using). Maybe something else is broken in your image.

Cheers,

Florin





avalloud at entrypoint.com on 04/28/2000 02:14:05 PM

Please respond to squeak at cs.uiuc.edu

To:   squeak at cs.uiuc.edu
cc:   (bcc: Florin X Mateoc)
Subject:  Re: [FIX][ENH] SortedCollection robustness & speedup




Hi Georg.

> >>  addAll: aCollection
> >>          "Optimize for large additions."
> >>
> >>          aCollection size > (self size // 3) ifTrue: [
> >>                  aCollection do: [ :each | super addLast: each ].
> >>                  self reSort ]
> >>           ifFalse: [ aCollection do: [ :each | self add: each ]].
> >>          ^aCollection! !
>
> Sorry, I do not understand this one. Can you elaborate ?

The message addAll: works by adding stuff to the receiver. Hence,

x addAll: aCollection

gets you x with all its elements plus the elements of aCollection, all of
those in x. aCollection is not modified by this process. Now, with the method
above, you may get an equivalent answer but the receiver may be left untouched
by addAll:. This would happen when aCollection size <= (self size // 3). In
that case, aCollection would have its elements and those of x, so the answer
of this message would be equivalent. But aCollection is modified instead of x.
So, you could have this happen:

x _ (1 to: 10) asSortedCollection.
y _ (11 to: 12) asSortedCollection.
x addAll: y.
x size <alt-p> 10

How come it's 10 when I added stuff to it? And surprisingly,

y size <alt-p> 12

?!??!...

What I meant by merge sort is that when collections are large, the cost of
resorting is huge. So, when addAll: is sent with a big collection to another
big collection, you could do merge sort and create a third temp one whose
contents would replace the receiver's when the process is finished. Alas, you
can only do this if the sort blocks are both nil or are compatible.

I do not think that the sort blocks can be determined to be compatible... it
would take too much (even if they sent the same messages, you would also have
to verify that they were supposed to send the same messages to the same kind
of objects). That leaves the case when the sort blocks are both nil, in which
you can safely do merge sort.

Andres.











More information about the Squeak-dev mailing list