[squeak-dev] Re: includes: does linear search for
andreas.raab at gmx.de
Sun Dec 19 18:10:13 UTC 2010
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.
add: nil; "<- works"
add: 3. "<- blows"
More information about the Squeak-dev