Re: UnsameQ implementation
- To: mathgroup at smc.vnet.net
- Subject: [mg8195] Re: UnsameQ implementation
- From: Robert Knapp <rknapp>
- Date: Mon, 18 Aug 1997 23:24:44 -0400
- Organization: Wolfram Research, Inc.
- Sender: owner-wri-mathgroup at wolfram.com
C. Woll wrote:
>
> Hi,
>
> The function UnsameQ gives true if all of its arguments are pairwise
> distinct. The following function also gives true if all of its arguments
> are pairwise distinct
>
> DistinctQ[a__]:=Length[Union[{a}]]===Length[{a}]
>
> Now, let's consider a test of these two functions.
>
> test = Table[i[Random[Integer,10000]],{10000}];
> utest= Union[test];
>
> Applying the above functions yields
>
> UnsameQ@@test//Timing
> DistinctQ@@test//Timing
>
> {0. Second, False}
> {0.06 Second, False}
>
> UnsameQ@@utest//Timing
> DistinctQ@@utest//Timing
>
> {0.4 Second, True}
> {0.02 Second, True}
>
> Notice that for utest, DistinctQ is much faster than the built in
> function UnsameQ.
>
> For a list which contains duplicates, it's not surprising that UnsameQ is
> much faster, since it terminates as soon as a duplicate is found. But why
> is UnsameQ so slow when given a list with no duplicates?
>
The reason for this is explain well by your description of the command
above (highlighted here for emphasis) "The function UnsameQ gives true
if all of its arguments are PAIRWISE distinct". Now with a list of
length n, there are n(n-1)/2 PAIRS to check. (For the utest I got on my
system, this is 20043946 comparisons). It is important that the check
be done pairwise because in Mathematica SameQ has a built in tolerance
for inexact numbers. Because of this, the DistinctQ you defined is not
equivalent to SameQ if there are inexact numbers in the epxressions.
> Although this isn't a bug, it seems to me that UnsameQ should be
> implemented so that it's at least as fast as DistinctQ above. Will this be
> looked at in future versions of Mathematica?
>
> Carl Woll
> Physics Dept
> U of Washington
>
> License L2514-7296
We will be looking into alternative ways of doing this, making sure we
don't slow the command down for smaller number of arguments.
Rob Knapp
Wolfram Research, Inc.