[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
|