Re: UnsameQ implementation
- To: mathgroup at smc.vnet.net
- Subject: [mg8165] Re: [mg8129] UnsameQ implementation
- From: David Withoff <withoff>
- Date: Sat, 16 Aug 1997 11:51:09 -0400
- Sender: owner-wri-mathgroup at wolfram.com
> 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?
>
> 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
The Union function works by sorting the elements, and then
comparing adjacent elements. The speed is therefore asymptotically
proportional to n log(n).
The UnsameQ function works by comparing every pair of elements. The
speed is therefore asymptotically proportional to n^2.
That is why Union is faster than SameQ.
It is also perhaps worth pointing out that DistinctQ is not equivalent
to UnsameQ. For example:
In[1]:= DistinctQ[a__]:=Length[Union[{a}]]===Length[{a}]
In[2]:= DistinctQ[N[Pi, 20], N[Pi, 30]]
Out[2]= True
In[3]:= UnsameQ[N[Pi, 20], N[Pi, 30]]
Out[3]= False
Although it would in principle be possible to introduce a sorting
function which would be suitable for use in UnsameQ, so that UnsameQ
could also work in time proportional to n log(n), the sorting algorithm
used in Union is not suitable for this purpose. In particular, there
is no guarantee that Union will sort similar elements (elements for
which UnsameQ returns False) into adjacent positions, nor is there
any guarantee that Union will discard elements for which UnsameQ
returns False.
The answer to your second question is yes, some change of this type
may very well be considered for some future version of Mathematica,
but implementing this correctly will require a lot more work than
might be suggested by this simple example.
Dave Withoff
Wolfram Research