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

Igor Stasenko siguctua at gmail.com
Sun Dec 19 18:02:04 UTC 2010


2010/12/19 Levente Uzonyi <leves at elte.hu>:
> 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.
>

yes.. and so, you can't make difference between 'it is really not in
collection' and its 'not in a collection' ,
because sort block may trigger an error due to some mistake, which
occurs only for particular object :)

>
> Levente
>
>>
>>
>>
>>> Regards,
>>>
>>> Ralph Boland
>>>
>>> --
>>> Quantum Theory cannot save us from the tyranny of a deterministic
>>> universe
>>> but it does give God something to do
>>>
>>>
>>
>>
>>
>> --
>> Best regards,
>> Igor Stasenko AKA sig.
>>
>
>
>
>



-- 
Best regards,
Igor Stasenko AKA sig.



More information about the Squeak-dev mailing list