|
»
»
« Return to Thread: [vwnc] Bug in MethodDictionary
Re: [vwnc] Bug in MethodDictionary
by Andres Valloud-3
::
Rate this Message:
Here's a more permlink to the messages...
http://groups.google.com/group/comp.lang.smalltalk/browse_thread/thread/3c47ffb41e6433d3/d21a50cbcb3a49de?q=ANSI&lnk=nl&
FIrst, things like 'abcd' asSortedCollection includes: 5 would fail if
includes: used binary search because the argument may not be comparable
to what is inside the collection. And wrapping the sort block in an
exception handler may not work either:
" [...] consider the following:
| coll |
coll := ((1 to: 10) collect: [:each | 2 raisedTo: each])
asSortedCollection: [:a :b | a highBit <= b highBit].
coll allSatisfy: [:each | coll includes: each asFloat]
This should return true by the ANSI standard. However, it will raise an
error if you try to look for the floating point value using the sort block.
Also, does [binary search] work for the case where the sort block
doesn't uniquely
distinguish items?
| coll |
coll := (1 to: 1000) asSortedCollection: [:a :b | true].
coll allSatisfy: [:each | coll includes: each]
In this case, [includes:] has to linearly look through the whole
collection for each element. "
Andres.
Alan Knight wrote:
> At 09:42 AM 7/17/2008, Alan Knight wrote:
>
>> At 07:57 AM 7/17/2008, Holger Kleinsorgen wrote:
>>
>>>> Ahhh, very nice catch indeed. We do have a somewhat related AR,
>>>>
>>>> AR# 46540
>>>> Description SortedCollection>>includes:/indexOf: binary search
>>>>
>>>> which implements binary search / binary inclusion checks for sorted
>>>> collections. Note that this functionality is not meant to replace what
>>>> includes: / indexOf: are doing right now, but rather they provide this
>>>> via new selectors.
>>>>
>>> may I ask why? Interval didn't implement #includes: in the past, too,
>>> until a specific implementation was added in 7.6 (43789). This was nice,
>>> because all senders automatically benefited from the improvement.
>>>
>> This came up quite some time ago, and I can't seem to find the reference, but John Brant quite extensively pointed out the issues with includes: using binary search being difficult or impossible to reconcile with the ANSI standard behaviour. That's unfortunate, and arguably a bug with ANSI, but it does seem to make it inadvisable to make that the default implementation. It also does mean (if the methods are available) that you can deliberately invoke binary searches on collections that you happen to believe are sorted, even if they aren't strictly sorted collections.
>>
>
> OK, I found it. In comp.lang.smalltalk, September 2003, with the rather unrelated subject line "Re: ST standardization: (was Re: Is Python's library more standard than Smalltalk's?) "
>
>
> --
> Alan Knight [|], Engineering Manager, Cincom Smalltalk
> knight@...
> aknight@...
> http://www.cincom.com/smalltalk
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> vwnc mailing list
> vwnc@...
> http://lists.cs.uiuc.edu/mailman/listinfo/vwnc
>
_______________________________________________
vwnc mailing list
vwnc@...
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc
http://groups.google.com/group/comp.lang.smalltalk/browse_thread/thread/3c47ffb41e6433d3/d21a50cbcb3a49de?q=ANSI&lnk=nl&
FIrst, things like 'abcd' asSortedCollection includes: 5 would fail if
includes: used binary search because the argument may not be comparable
to what is inside the collection. And wrapping the sort block in an
exception handler may not work either:
" [...] consider the following:
| coll |
coll := ((1 to: 10) collect: [:each | 2 raisedTo: each])
asSortedCollection: [:a :b | a highBit <= b highBit].
coll allSatisfy: [:each | coll includes: each asFloat]
This should return true by the ANSI standard. However, it will raise an
error if you try to look for the floating point value using the sort block.
Also, does [binary search] work for the case where the sort block
doesn't uniquely
distinguish items?
| coll |
coll := (1 to: 1000) asSortedCollection: [:a :b | true].
coll allSatisfy: [:each | coll includes: each]
In this case, [includes:] has to linearly look through the whole
collection for each element. "
Andres.
Alan Knight wrote:
> At 09:42 AM 7/17/2008, Alan Knight wrote:
>
>> At 07:57 AM 7/17/2008, Holger Kleinsorgen wrote:
>>
>>>> Ahhh, very nice catch indeed. We do have a somewhat related AR,
>>>>
>>>> AR# 46540
>>>> Description SortedCollection>>includes:/indexOf: binary search
>>>>
>>>> which implements binary search / binary inclusion checks for sorted
>>>> collections. Note that this functionality is not meant to replace what
>>>> includes: / indexOf: are doing right now, but rather they provide this
>>>> via new selectors.
>>>>
>>> may I ask why? Interval didn't implement #includes: in the past, too,
>>> until a specific implementation was added in 7.6 (43789). This was nice,
>>> because all senders automatically benefited from the improvement.
>>>
>> This came up quite some time ago, and I can't seem to find the reference, but John Brant quite extensively pointed out the issues with includes: using binary search being difficult or impossible to reconcile with the ANSI standard behaviour. That's unfortunate, and arguably a bug with ANSI, but it does seem to make it inadvisable to make that the default implementation. It also does mean (if the methods are available) that you can deliberately invoke binary searches on collections that you happen to believe are sorted, even if they aren't strictly sorted collections.
>>
>
> OK, I found it. In comp.lang.smalltalk, September 2003, with the rather unrelated subject line "Re: ST standardization: (was Re: Is Python's library more standard than Smalltalk's?) "
>
>
> --
> Alan Knight [|], Engineering Manager, Cincom Smalltalk
> knight@...
> aknight@...
> http://www.cincom.com/smalltalk
>
>
> ------------------------------------------------------------------------
>
> _______________________________________________
> vwnc mailing list
> vwnc@...
> http://lists.cs.uiuc.edu/mailman/listinfo/vwnc
>
_______________________________________________
vwnc mailing list
vwnc@...
http://lists.cs.uiuc.edu/mailman/listinfo/vwnc
« Return to Thread: [vwnc] Bug in MethodDictionary
| Free Forum Powered by Nabble | Forum Help |
