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

**Re: floor problems**

**RE: ListPlot with little plus s**

**UnsameQ implementation**

**Re: UnsameQ implementation**