Union in Mathematica versions 3 and 4

*To*: mathgroup at smc.vnet.net*Subject*: [mg23309] Union in Mathematica versions 3 and 4*From*: Carl Woll <carlw at u.washington.edu>*Date*: Mon, 1 May 2000 18:00:10 -0400 (EDT)*Sender*: owner-wri-mathgroup at wolfram.com

Recently, there has been some discussion of a vector union function where I asserted that Union with a SameTest funtion other than the default has complexity of O(N^2). This is a change between Mathematica versions 3 and 4, and is in fact really a bug fix, since the algorithm used in Mathematica version 3 did not produce a true Union function. That is, in version 3 it was possible to apply the Union function to a data set using a SameTest option other than the default with the result that some of the elements of the data set were not eliminated even though they should have been removed. This is because the old Union algorithm always sorted the data set with the standard canonical ordering first, and then compared adjacent elements using the supplied SameTest function. This is a good change, but there are situations where the sort and then test algorithm will still produce the correct result. In version 3, we just used Union to execute this algorithm, but in version 4, this approach will clearly perform very inefficiently on large data sets. In this post I wanted to discuss how to produce such an algorithm in version 4. The simplest idea was the following: SortUnion[data_, OrderFunction->p_, SameTest->f_]:=First/@Split[Sort[data, p],f] The first thing about this function I wanted to mention was the use of First/@. In previous versions of Mathematica I believe this was the fastest way to generate a list of just the first elements. In Mathematica 4, however, it is not the most efficient way of getting a list of the first elements. The most efficient techique now uses the new All specification in Part. So a better SortUnion function is the following: SortUnion[data_, OrderFunction->p_, SameTest->f_]:=Split[Sort[data,p],f][[All,1]] By the way, if you wanted just the last elements, you would just replace 1 with -1. The next thing to note is that Sort without the optional OrderFunction is much much faster than a sort using an optional OrderFunction. In my tests, this difference may be as much as 2 orders of magnitude. For example, In[1]:= data = Table[Random[], {100000}]; In[5]:= s1 = Sort[data]; // Timing s2 = Sort[data, OrderedQ[{#1, #2}] &]; // Timing s1 === s2 Out[5]= {0.609 Second, Null} Out[6]= {44.672 Second, Null} Out[7]= True This suggests that it may be wise to organize ones data such that the standard optionless Sort performs the sort you want. On the other hand, the function Split with and without the optional SameTest function does not exhibit as pronounced a difference. With this in mind, I believe that a SortUnion function with a SameTest option, but without an OrderFunction option would be useful, as in SortUnion[data_, SameTest->f_]:=Split[Sort[data],f][[All,1]] I believe that this captures the exact same functionality as the version 3 Union function. Now for the reason why I looked into the above. There has been some discussion recently of the somewhat misleadingly named OrderedUnion function (I now think I should have named it UnsortedUnion). It turns out that a competing O(N log N) function which I wrote before became O(N^2) in version 4 because of the above change in Union. In revisiting this algorithm, I came up with an improvement which is now significantly better than the above OrderedUnion function. That is, while OrderedUnion used an O(N) algorithm, it turned out that the crossover point from my new O(N log N) function to the O(N) function was so high that the O(N) function froze the kernel. Below I give the definition of this new O(N log N) function (called UnsortedUnion) to find the union of a set while preserving the original order. In[7]:= SortUnion[data_, SameTest -> f_] := Split[Sort[data], f][[All, 1]] In[8]:= UnsortedUnion[li_List] := Module[{len = Length[li], tmp}, tmp = SortUnion[Transpose[{li, Range[len]}], SameTest -> (#1[[1]] === #2[[1]] &)]; Sort[Transpose[RotateLeft[Transpose[tmp]]]][[All, 2]] ] In[9]:= OrderedUnion[li_List] := Block[{i, Sequence}, i[n_] := (i[n] = Sequence[]; n); i /@ li] In[10]:= data = Table[Random[Integer, 40000], {40000}]; In[11]:= r1 = OrderedUnion[data]; // Timing r2 = UnsortedUnion[data]; // Timing r1 === r2 Out[11]= {5.266 Second, Null} Out[12]= {4.031 Second, Null} Out[13]= True

**Re: more on vector unions**

**RE: [Q] Equation solving?**

**Re: more on vector unions**

**Re: Union in Mathematica versions 3 and 4**