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>
- Re: Re: Re: Re: programming problem about elements
- 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: programming problem about elements taken