[BUG]Collection>>removeAll:
Stephan Rudlof
sr at evolgo.de
Wed Aug 28 14:07:11 UTC 2002
Richard A. O'Keefe wrote:
<snipped>
> So we find that
>
> - x copyWithoutAll: y is already O(1) when x isEmpty
> without adding any special test;
>
> - x removeAll: y must not make a special case when x isEmpty
> (unless y isEmpty also), in fact, if x is empty and y isn't
> an error will be reported after O(1) work so there isn't
> even a performance problem finding the error;
>
> - x removeAllFoundIn: y is the only remaining method where
> removing a large y from an empty x could be expensive,
> but then *in context* that's likely to be dominated by the
> cost of building y in the first place.
Agreed.
>
> Personally, I'm all in favour of special cases in implementations
> when they solve real problems.
>
> a := (1 to: 200*1000) asArray.
> e := OrderedCollection new.
> [e removeAllFoundIn: a] timeToRun
> ==> 4 seconds
> [e removeAllFoundInSR: a] timeToRun "really had 200000 timesRepeat:"
> ==> 4 milliseconds
>
> So yes, sticking a (self isEmpty) check in #removeAllFoundIn: can save
> as much time as you like (just make the argument as big as you want);
> the question is, does that happen often enough to pay off.
Agreed.
>
> Several of the sends to #removeAllFoundIn: in the system have arguments
> that are obviously very short or are obviously shorter than the receiver
> or else are called infrequently. I have no idea how other people use
> #removeAllFoundIn:.
And in most cases the shortcut probably wouldn't be one, since the receiver
is not empty.
If the programmer *knows*, that he/she wants to send #removeAllFoundIn: to a
potentially empty collection with potentially very big args, he/she is free
to check for emptyness before making this.
So (my current opinion ;-) ): let it be (the self isEmpty check).
But I stay voting for asserts in the addAll:/removeAll: family making the
implicit precondition explicit.
Greetings,
Stephan
>
>
--
Stephan Rudlof (sr at evolgo.de)
"Genius doesn't work on an assembly line basis.
You can't simply say, 'Today I will be brilliant.'"
-- Kirk, "The Ultimate Computer", stardate 4731.3
More information about the Squeak-dev
mailing list
|