[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
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**
| |