MathGroup Archive 2007

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

Search the Archive

Re: Re: Re: programming problem about elements

  • To: mathgroup at
  • Subject: [mg72521] Re: [mg72510] Re: [mg72497] Re: programming problem about elements
  • From: Daniel Lichtblau <danl at>
  • Date: Thu, 4 Jan 2007 06:48:20 -0500 (EST)
  • References: <><en82hd$6or$> <> <>

Andrzej Kozlowski wrote:
> [...]
> I have never tested how fast it is; probably not very fast,  since   
> Union works much faster with the default value of SameTest (the same  
> is true for Sort which is much slower with a user defined ordering  
> function).
> Andrzej Kozlowski

Just a remark on algorithm complexities. Sort with or without default 
comparison test is O(n log n) for a list of n elements, assuming 
comparisons are constant time. With default SameTest it tends to be one 
or two orders of magnitude faster than with a nondefault SameTest, due 
to relative speed of the default that, among other things, avoids use of 
the full blown Mathematica evaluator mechanism.

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

  • Prev by Date: Re: Is there Options for a variable
  • Next by Date: Finding paths in graphs
  • Previous by thread: Re: Re: programming problem about elements taken
  • Next by thread: Re: Re: Re: Re: programming problem about elements