Re: programming problem about elements taken
- To: mathgroup at smc.vnet.net
- Subject: [mg72516] Re: programming problem about elements taken
- From: Jean-Marc Gulliet <jeanmarc.gulliet at gmail.com>
- Date: Thu, 4 Jan 2007 06:28:14 -0500 (EST)
- Organization: The Open University, Milton Keynes, UK
- References: <200612301039.FAA21673@smc.vnet.net><en82hd$6or$1@smc.vnet.net> <enfftj$smm$1@smc.vnet.net>
Ray Koopman wrote:
> Andrzej Kozlowski wrote:
>> Consider this list of 5 numbers:
>>
>> ls = Sort[Table[Random[], {5}]]
>> {0.165874, 0.256035, 0.556211, 0.811305, 0.865799}
>> Suppose we take epsilon = 0.3 and identify the numbers distant by
>> less than that from one another. Then
>>
>> Union[ls, SameTest -> (Abs[#1 - #2] < 0.3 &)]
>> {0.165874, 0.556211, 0.865799}
>> gives us just three numbers.
>> [...]
>> Note that when two numbers are identified it is the smaller one that
>> is kept.
>> [...]
>
> Is this just an observation, or official-but-not-publicly-documented?
> The arguments to SameTest seem always to be reverse-ordered (i.e.,
> #2 >= #1), even when the input list is unsorted, and the sequence of
> argument pairs seems to be the same regardless of whether the input
> list is sorted or unsorted. Can we conclude that Union sorts the input
> list before using SameTest,
Ray,
According to Michael Trott [1], Union[lst_i, ...] and Union[list_i, ...,
SameTest -> ...] (i = 1, .., n) use different algorithms. Using SameTest
changes the algorithm used by Union, not the fact that the input list(s)
is/are already sorted or not.
Union without SameTest sorts the list(s) first (O(n*log(n)) complexity),
then compares adjacent elements.
Union with SameTest uses a different strategy (in quadratic complexity).
> and that when SameTest returns True it is
> the second argument that is kept?
Regards,
Jean-Marc
1. Trott, Michael. _The Mathematica GuideBook for Programming_, Chapter
6 "Operations on Lists, and Linear Algebra", Section 6.4 "Operations
with Several Lists or with Nested Lists", Subsection 6.4.1 "Simple
Operations", see entries at Union p761 and SameTest p762, Springer (2004).
QA76.73.M29 T76 2000