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

Re: Re: Re: programming problem about elements

• To: mathgroup at smc.vnet.net
• Subject: [mg72521] Re: [mg72510] Re: [mg72497] Re: programming problem about elements
• From: Daniel Lichtblau <danl at wolfram.com>
• Date: Thu, 4 Jan 2007 06:48:20 -0500 (EST)
• References: <200612301039.FAA21673@smc.vnet.net><en82hd$6or$1@smc.vnet.net> <200701030603.BAA29747@smc.vnet.net> <200701031016.FAA07246@smc.vnet.net>

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

• Follow-Ups:
  • Re: Re: Re: Re: programming problem about elements
    • From: Andrzej Kozlowski <akoz@mimuw.edu.pl>

• 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>