|
[Date Index]
[Thread Index]
[Author Index]
Re: Re: Re: Re: programming problem about elements
On 4 Jan 2007, at 11:48, Daniel Lichtblau wrote:
> Andrzej Kozlowski wrote:
>
> Union is different. For default SameTest it will use Sort and then
> compare elements to neighbors. This is O(n log n) due to use of Sort.
> For nondefault SameTest it must compare all pairs and this is O(n^2)
> complexity. This also necessitates use of the evaluator for each
> equivalence check, so we have a constant factor also slowing the
> process. Offhand I do not recall whether presorting is done in this
> case. There is a final Sort in order to be in agreement with
> documentation.
>
>
> Daniel Lichtblau
> Wolfram Research
>
I am not sure if my memory is not deceiving me, but I seem to
remember that in some earlier versions of Mathematica, Union with
user defined SameTest worked differently; I think, essentially the
way it does today with the default setting of SameTest. In other
words, things were first sorted and then only neighboring elements
were compared, starting with the smallest. I seem to recall that
this behavior caused some complaints to be posted to this list and in
later versions it was changed. (I might of course be just fantasizing
it all so just in case I will blame it on post-New Year hangover).
But in this particular problem the old behavior (assuming that was
the old behavior) would have been preferable so perhaps it might have
been a good idea to have preserved it as a (non-default) option.
That applies, of course, only to the real version of the problem; in
the complex version I think it is really necessary to compare all pairs.
Andrzej Kozlowski
Prev by Date:
Re: Finding paths in graphs
Next by Date:
Re: [TS 48]--Re:why isn't Rational[1,2] (apparently) atomic until it is evaluated?
Previous by thread:
Re: Re: Re: programming problem about elements
Next by thread:
Re: programming problem about elements taken
|
