includes: does linear search for SortedCollection???????
Locked
includes: does linear search for SortedCollection???????
 
|
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. Regards, Ralph Boland -- Quantum Theory cannot save us from the tyranny of a deterministic universe but it does give God something to do |
Re: includes: does linear search for SortedCollection???????
|
|
On 19 December 2010 18:11, Ralph Boland <[hidden email]> 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. > 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? > 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. |
Re: includes: does linear search for SortedCollection???????
|
|
On Sun, 19 Dec 2010, Igor Stasenko wrote:
> On 19 December 2010 18:11, Ralph Boland <[hidden email]> 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? 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. > > |
Re: includes: does linear search for SortedCollection???????
|
|
2010/12/19 Levente Uzonyi <[hidden email]>:
> On Sun, 19 Dec 2010, Igor Stasenko wrote: > >> On 19 December 2010 18:11, Ralph Boland <[hidden email]> 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. |
Re: includes: does linear search for SortedCollection???????
|
|
In reply to this post by Levente Uzonyi-2
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 <[hidden email]> 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. ObRidiculous: (SortedCollection new) add: nil; "<- works" add: 3. "<- blows" Cheers, - Andreas |
Re: includes: does linear search for SortedCollection???????
|
|
In reply to this post by Igor Stasenko
On Sun, 19 Dec 2010, Igor Stasenko wrote:
> 2010/12/19 Levente Uzonyi <[hidden email]>: >> On Sun, 19 Dec 2010, Igor Stasenko wrote: >> >>> On 19 December 2010 18:11, Ralph Boland <[hidden email]> 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 :) with the sortblock and the user got the error (or will get it soon). If it's not in the collection and the error is raised, then you should return false anyway. Levente > >> >> 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. > > |
Re: includes: does linear search for SortedCollection???????
|
|
In reply to this post by Ralph Boland
On Sun, 19 Dec 2010, Ralph Boland 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. It's not easy to do it right. The best would be to implement #indexOf:startingAt:ifAbsent:, because that's sent from #includes:. To avoid code duplication you can reuse #indexForInserting: or use #findBinaryIndex:ifNone:, but both of them is insufficient for a complete solution. You have to implement an additional galloping binary search to guarantee O(log(n)) runtime. Levente > > Regards, > > Ralph Boland > > -- > Quantum Theory cannot save us from the tyranny of a deterministic universe > but it does give God something to do > > |
Re: includes: does linear search for SortedCollection???????
|
|
In reply to this post by Andreas.Raab
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 <[hidden email]> 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 > > |
|
|
In reply to this post by Andreas.Raab
On Dec 19, 2010, at 10:10 AM, 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 <[hidden email]> 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 In GemStone we used to do a binary search on #'includes:' but a customer complained that they had a domain object where #'=' was implemented using different instance variables than #'<=' so that a linear search would find an equivalent object but a binary search would miss it. We changed #'includes:' to use a linear search and added another method, #'binarySearchIncludes:' to have the old (fast) behavior. James > ; 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. > > ObRidiculous: > > (SortedCollection new) > add: nil; "<- works" > add: 3. "<- blows" > > Cheers, > - Andreas > > |
Re: includes: does linear search for SortedCollection???????
|
|
On 19 December 2010 19:54, James Foster <[hidden email]> wrote:
> > In GemStone we used to do a binary search on #'includes:' but a customer complained that they had a domain object where #'=' was implemented using different instance variables than #'<=' so that a linear search would find an equivalent object but a binary search would miss it. We changed #'includes:' to use a linear search and added another method, #'binarySearchIncludes:' to have the old (fast) behavior. > i think this is a good compromise. > James > -- Best regards, Igor Stasenko AKA sig. |
Re: includes: does linear search for SortedCollection???????
|
|
+1. AND, I would like to postpone action until we can get 4.2 out the door.
On Sun, Dec 19, 2010 at 1:21 PM, Igor Stasenko <[hidden email]> wrote: > On 19 December 2010 19:54, James Foster <[hidden email]> wrote: >> >> In GemStone we used to do a binary search on #'includes:' but a customer complained that they had a domain object where #'=' was implemented using different instance variables than #'<=' so that a linear search would find an equivalent object but a binary search would miss it. We changed #'includes:' to use a linear search and added another method, #'binarySearchIncludes:' to have the old (fast) behavior. >> > > i think this is a good compromise. > >> James >> > -- > Best regards, > Igor Stasenko AKA sig. > > |
«
Return to Squeak - Dev
|
1 view|%1 views
| Free forum by Nabble | Edit this page |