[squeak-dev] Re: includes: does linear search for SortedCollection???????

Levente Uzonyi leves at elte.hu
Sun Dec 19 18:52:15 UTC 2010


On Sun, 19 Dec 2010, Andreas Raab wrote:

> On 12/19/2010 9:55 AM, Levente Uzonyi wrote:
>> On Sun, 19 Dec 2010, Igor Stasenko wrote:
>> 
>>> On 19 December 2010 18:11, Ralph Boland <rpboland at gmail.com> wrote:
>>>> The main advantage of a sorted list is that binary search can be
>>>> performed on the list.
>>>> So I was surprised to find that the method SortedCollection>>includes:
>>>> (actually OrderedColection>includes:) does a linear search (Squeaks
>>>> 10.2 and 4.1).
>>>> 
>>>> I suggest we implement a version of SortedCollection>>includes: that
>>>> runs in O(log n)
>>>> time.  I can write this if desired or just about anybody.
>>>> 
>>> you can do binary search if argument can be passed to sort block and
>>> respond to any message(s) which sort block sends to it for determining
>>> its order.
>>> 
>>> and what you suppose to do with:
>>> coll includes: nil
>>> 
>>> or any other argument, which can't be used for binary search?
>> 
>> You can catch the error and return false.
>
> I'd say let it blow. I'm with Ralph on this one; SortedCollection really 
> ought to use binary search. Inclusion should be defined in terms of the 
> comparable that's being used in the collection; if (for example) 
> "aSortedCollection add: nil" blows up, why would you then expect 
> "aSortedCollection includes: nil" not to?
>
> Generally speaking, SortedCollection already operates on a subdomain and not 
> arbirary objects. I think it is reasonable to expect #includes: to have the 
> same set of constraints.

IIUC this wouldn't conform to the ANSI standard.

Btw, I wonder how other smalltalks implement SortedCollection, because 
Squeak's implementation is not very useful. I think it could be replaced 
with a balanced binary tree. The memory costs would grow (+1 extra 
object with 4-5 slots/element) and some methods would be slower (e.g. 
#at:), but others would be a lot faster (e.g. #add:, #remove:).


Levente

>
> ObRidiculous:
>
> 	(SortedCollection new)
> 		add: nil;  "<- works"
> 		add: 3.    "<- blows"
>
> Cheers,
>  - Andreas
>
>



More information about the Squeak-dev mailing list