Why some built-in functions are slow

I just wonder why some built-in functions are slower compared to some other ways using more than one built-in functions for doing same job.

consider this example:

list = RandomInteger[10000, 10000000];

Timing[sol1 = Union[list];]

(*{2.265625, Null}*)

Timing[sol2 = Sort[First /@ Tally[list]];]

(*{0.031250, Null}*)

sol1 == sol2

(* True*)


One built-in function (Union) is so slow compared to four built-in functions (Tally, Map, First, and Sort) .

Questions:

1- why is that happening?

2- how to know that there is faster way (using more than one built-in function) for doing job compare to one built-in function? is it just by experience?

• DeleteDuplicates should be even faster! This question is strongly related. The answer is pretty much given in the chat that was created to discuss this. – Jacob Akkerboom Oct 24 '14 at 23:17
• As for the more general question why built-ins are slower than what users can cobble together I think that is answered here and here. TL;DR There is no good reason. Developers just haven't gotten around to optimizing those functions yet. – C. E. Oct 24 '14 at 23:37

The general case

There are indeed some functions in Mathematica that are/were not performing nicely. The one I am most scared of is Total (the issue is addressed here) (update: apparently Total has been fixed in version 10.0.2). User C.E. provides some more examples in his comment. But I feel the case of Union is different, as it is simply specialised for a specific case and in this case it performs well.

The case of Union

The way I see it, there is a spectrum of lists on which Union has to work. On one side of the spectrum, there are many duplicates, on the other few. Union is optimised to handle relatively few duplicates, and here it is unbeatable. But for many duplicates, using DeleteDuplicates first is faster.

To see that this is true, one can experiment with the following code.

mm = 1*^6;
kk = 1*^4;
rands = RandomInteger[kk, mm];

(res1 = Sort[DeleteDuplicates[rands]]) // Timing // First
(res2 = DeleteDuplicates[Sort[rands]]) // Timing // First
(res3 = Union[rands]) // Timing // First

res1 == res2 == res3
res1 == Range[0, Min[kk, 10^6]]

0.003440
0.152277
0.149979
True
True


Here there are many duplicates, so that Sort@*DeleteDuplicates is faster. Compare this with

kk = 1*^10;
rands = RandomInteger[kk, mm];
(res1 = Sort[DeleteDuplicates[rands]]) // Timing // First
(res2 = DeleteDuplicates[Sort[rands]]) // Timing // First
(res3 = Union[rands]) // Timing // First

res1 == res2 == res3
res1 == Range[0, Min[kk, 10^6]]

0.376823
0.365987
0.175067
True
False


where there are few duplicates, and Union is unbeatable.

At first I felt that it was strange that Union was so focussed on the few-duplicates case, but then again, techniques like sampling the list to see how many duplicates there are are pretty ugly and heuristic at best. I think the choice to make Union work like this is all right, though I think it should be documented more clearly.

In the documentation of DeleteDuplicates one can find that deleting duplicates can be much faster than "using Union". However it does not say that in cases like this it may be better to use technique of deleting duplicates first and then sorting.

A tricky part of understanding all this is understanding that DeleteDuplicates can be so much faster. I think the power of the hash table is easily underestimated, and to think that it is always a good idea to delete duplicates by sorting elements is an easy mistake to make.

I would love to see something like an option of Union to make it assume it is dealing with many duplicates. It must be possible to make something that is (at least a little bit) faster than using Sort@*DeleteDuplicates. That would also mean that the issue would have to be addressed in the documentation of Union.

• +1, but I think this should compare with the same length list having many and few duplicates as well as duplicated items. Without having tested it, I think you might be seeing trade-offs between the $O(n^2 \log{n})$ average case behavior of Union (worst case for pathological lists: $O(n^3)$), the $O(n)$ average case for DeleteDuplicates, and the $O(n^2)$ worst case for the same, which will happen if there are many different duplicated items. (I am guessing about the complexity of Union. It could be just $O(n \log{n})$ average case and $O(n^2)$ worst case, as for quicksort.) – Oleksandr R. Dec 19 '14 at 18:58
• @OleksandrR. thank you for your comment. I am not entirely sure what you mean with your first sentence. The lists here have the same size, which is mm. I suppose it could be nice to add the observation that Union does not get much slower, whereas DeleteDuplicates does, when have fewer duplicates. I think a comparison in terms of big O notation is also useful. I think delete duplicates indeed takes $O(n)$ time. For fixed kk a $O(n\, log(n))$ algorithm for Union exists, as an algorithm would be to first delete duplicates and then sort, an with abuse $O(n)+O(n\,log(n)) = O(n\,log(n))$ – Jacob Akkerboom Dec 20 '14 at 18:02
• I do not know about the actual implementation of Union of course. Here Leonid says DeleteDuplicates can be $O(n)$ and that Union can use a $O(n\,log(n))$ algorithm. All my statements so far have been about worst case, though I like your distinction between the average and worst case. If we let kk depend on $n$ in such comparisons and then Union may (I think) have better asymptotic behaviour than DeleteDuplicates. If you feel the answer can be made better feel free to edit it, I cannot do so right now. – Jacob Akkerboom Dec 20 '14 at 18:12
• Yes, sorry, you are right. I was typing faster than I was thinking when I wrote that, and surely Union must be $O(n \log{n})$ average case, not $O(n^2 \log{n})$, as it's not necessary to scan the entire list to remove each duplicate if it's already sorted. (Note that Quicksort is $O(n^2)$ worst case, though this is seldom seen in practice.) The cost of looking an item up in a hash table is $O(1)$, but it's $O(m)$ to (re)build it ($m$ entries), so $O(mn)$ or roughly $O(n^2)$ if it needs to be rebuilt $O(n)$ times, as if there are many widely dispersed but seldom duplicated items in the input. – Oleksandr R. Dec 22 '14 at 15:58
• In summary, I think we probably have $O(n^2)$ worst case for both Union and DeleteDuplicates, except that the worst case for the latter is more frequently observed and probably has a larger constant factor. The average case will be $O(n \log{n})$ and $O(n)$, respectively, as you say. – Oleksandr R. Dec 22 '14 at 16:02