Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

Re: Re: Re: Re: programming problem about elements

• To: mathgroup at smc.vnet.net
• Subject: [mg72535] Re: [mg72521] Re: [mg72510] Re: [mg72497] Re: programming problem about elements
• From: Andrzej Kozlowski <akoz at mimuw.edu.pl>
• Date: Fri, 5 Jan 2007 02:14:12 -0500 (EST)
• References: <200612301039.FAA21673@smc.vnet.net><en82hd$6or$1@smc.vnet.net> <200701030603.BAA29747@smc.vnet.net> <200701031016.FAA07246@smc.vnet.net> <200701041148.GAA18047@smc.vnet.net>

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

• References:
  • Re: programming problem about elements taken
    • From: "Ray Koopman" <koopman@sfu.ca>
  • Re: Re: programming problem about elements taken
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>
  • Re: Re: Re: programming problem about elements
    • From: Daniel Lichtblau <danl@wolfram.com>