# DeleteDuplicatesBy is not performing as I'd hoped. Am I missing something?

Déjà vu: a new-in-v10 function should provide a better solution to an old problem, but my enthusiasm is curbed when I run timings. This time the function is DeleteDuplicatesBy and while its performance is miles ahead of PositionIndex, I am still wondering if I am missing something or if this function was not ready for prime time.

In an effort to make this a question and short-circuit the cycle I shall summarize my question as:

1. What is the relative performance of DeleteDuplicatesBy and an obvious alternative?
2. Is there a case where the performance of this function clearly outstrips other methods?
-

The behavior described here is the same from 10.0.0 up to at least 10.3.

Summary

We can look at the code of DeleteDuplicatesBy and it turns out it uses GroupBy. The test cases proposed by Mr.Wizard are all handled by some part of the code of DeleteDuplicatesBy. Other parts of this code also seem to have some issues. Most of the members of the *By family of functions seem to have side effects.

How DeleteDuplicatesBy works

It turns out DeleteDuplicatesBy is not a function written in C. So it's Mr.Wizard's pure-MMA skills vs that of a WRI programmer for this one ;).

Let's see what the definition of DeleteDuplicatesBy is. From v10.1.0 onwards, this may be done conveniently by using

<<GeneralUtilities
PrintDefinitions@DeleteDuplicatesBy


If we predict where we will end up for a list, the definition basically says

DeleteDuplicatesBy[expr_, f_] := Values[GroupBy[expr, f, First]]


I guess theoretically the best way to do this would have to involve some kind of hash table. I expect GatherBy also uses some kind of hash table, but who knows. It does not feel really surprising that an approach using a general purpose hash table like Association is slower than what is used by GatherBy. But if Association was exactly the right kind of hash table for this, I suppose this approach may have been really fast. Unfortunately, it seems Association is not the best choice for the job, but who knows if it is better for really large expressions (or something).

Results of DeleteDuplicatesBy for "other expressions"

By default we end up in the last branch in the Which, corresponding to True. It looks like this code may not give the results we might expect. Example

DeleteDuplicatesBy[
Hold[{a, 2}, {b, 1}, {c, 1}], Function[Null, Last@Unevaluated[#], HoldAll]]

Hold[{a,2},{b,1},{c,1}]


This output is not expected, as we have

Function[Null, Last@Unevaluated[#], HoldAll][{b, 1}] ==
Function[Null, Last@Unevaluated[#], HoldAll][{c, 1}]

True


As an aside, in the last argument of Which, the following snippet occurs

Table[{f[expr[[i]]], i}, {i, Length[expr]}]


This is kind of an anti pattern. Performance in cases like this is better when using Map, Range and Transpose. We can also see that the snippet does not work when f has a hold argument, as the code relies on expr to evaluate.

Side effects of other *By family members

This is actually what I previously (before edits) thought was going wrong in DeleteDuplicatesBy. This should not print.

a := Print["hello"]
SortBy[Hold[{a, 2}, {b, 2}, {c, 1}],
Function[Null, Last@Unevaluated[#], HoldAll]]

"hello"
Hold[{c,1},{a,2},{b,2}]


For the new KeySortBy we have

a := Print["hello"]
KeySortBy[Association@Unevaluated@{a -> 2, 3 -> 4}, Hold]

"hello"
<|3->4, a->2|>


Good old SplitBy has some side effects

SplitBy[Hold[{a, 1}, {b, 1}, {c, 2}],
Function[Null, Last@Unevaluated@#, HoldAll]]

hello
Hold[Hold[{a,1},{b,1}],Hold[{c,2}]]


MaximalBy (and I suppose MinimalBy), GroupBy and CountsBy do not have the bonus of working with Unevaluated without creating side effects

q := Print["arg"]
MaximalBy[Unevaluated@{Hold[a, 3], {q, 2}},
Function[Null, Last@Unevaluated@#, HoldAll]]

arg
{Hold[a,3]}


But at least we can pretend they ignore Unevaluated rather that they give bad results. CountDistinctBy and of course GatherBy seem to works as expected.

Conclusion: DeleteDuplicatesBy may need a bit of work. I think some functions in the *By family could be a bit better, some more than others.

-
Thanks for the analysis. I didn't try Spelunk on this function because I assumed that it would be implemented in C. I'm pretty disappointed that this is how core functions are being handled in v10. – Mr.Wizard Jul 19 '14 at 12:39
I note that for an association argument there are four conversions!: assoc -> list -> assoc -> list -> assoc – Simon Woods Jul 19 '14 at 13:14
@Mr.Wizard note that for example SplitBy works in a similar way and already present in 7. GatherBy also has to deal with the problem that it has to rely on evaluation. It deals with this reasonably, as it generates a bunch of expressions which it then appears to compare in C. However, the one thing I don't like about GatherBy is that it only works on expressions with head List. – Jacob Akkerboom Jul 19 '14 at 13:51
@Jacob It's funny but I knew SplitBy wasn't as fast as I'd have liked but I don't think I was aware it was merely a proxy for Split[e, f[#1] === f[#2] &]. As I've said so often before: still so much to learn. Please, so me the SortBy side effects you're referring to. – Mr.Wizard Jul 19 '14 at 14:04
@TaliesinBeynon thank you posting an answer and for reporting. I had not reported anything yet. If you feel I should report the other leaks (or if my answer can be improved), please let me know. – Jacob Akkerboom Jul 20 '14 at 8:04

Timing charts updated for version 10.0.2. The behavior remains unchanged.

Attempting to analyze the performance of this function in the manner that Taliesin Beynon did for PositionIndex I shall use the same tools.

The old method that will be compared in all cases below:

myDeDupeBy[x_, f_] := GatherBy[x, f][[All, 1]]


## Speed

A BenchmarkPlot of DeleteDuplicatesBy versus myDeDupeBy:

Needs["GeneralUtilities"]

BenchmarkPlot[
{DeleteDuplicatesBy[#, Floor] &, myDeDupeBy[#, Floor] &},
RandomReal[#, 2*#] &,
2^Range[3, 22],
"IncludeFits" -> True
]


Again my function starts off in the lead. Let's try a higher duplicate density:

BenchmarkPlot[
{DeleteDuplicatesBy[#, Floor] &, myDeDupeBy[#, Floor] &},
RandomReal[#/4, 2*#] &,
2^Range[3, 22],
"IncludeFits" -> True
]


And a lower duplicate density:

BenchmarkPlot[
{DeleteDuplicatesBy[#, Floor] &, myDeDupeBy[#, Floor] &},
RandomReal[4*#, 2*#] &,
2^Range[3, 22],
"IncludeFits" -> True
]


DeleteDuplicatesBy seems to be a bit closer when there is high density so let's take that to the extreme with only two functionally unique values:

BenchmarkPlot[
{DeleteDuplicatesBy[#, Floor] &, myDeDupeBy[#, Floor] &},
RandomReal[2, 2*#] &,
2^Range[3, 22],
"IncludeFits" -> True
]


So it seems that my function is faster in nearly all cases, but when there is extreme duplication DeleteDuplicatesBy catches up. That's not saying much for it. Maybe its disappointing performance is an unavoidable trade-off of speed for memory?

## Memory

One might hope that a function that needs only retain one copy of each functional duplicate (DeleteDuplicatesBy) would have better memory performance that one that retains all elements (GatherBy). Let's check:

(* in a fresh Kernel *)

a = RandomReal[1*^3, 1*^7];
DeleteDuplicatesBy[a, Floor];
MaxMemoryUsed[]

284876480

(* in a fresh Kernel *)

a = RandomReal[1*^3, 1*^7];
GatherBy[a, Floor];
MaxMemoryUsed[]

284870272


So much for that hope. GatherBy actually uses slightly less memory.

If there is a use-case for DeleteDuplicatesBy apart from Associations I am not seeing it. :-/

-
thanks for the analysis. You should avoid doing the 2^n inside the example constructor function and use PowerRange instead of Range when supplying Benchmark or BenchmarkPlot with the range of n to test. This is because the library of time complexities does not assume that you've already done the transformation n -> log n, so you get those weird exponential fits. – Taliesin Beynon Jul 19 '14 at 21:40
@TaliesinBeynon Thanks for the instruction. :-) – Mr.Wizard Jul 20 '14 at 2:04
Mr.W, (@TaliesinBeynon), it seems the plots in your answer no longer work in v10.1.0. It seems that the function IndexBy has been removed and that BenchmarkPlot still refers to this. It also doesn't work without the options "IncludeFits" -> True. I will see if any other BenchmarkPlot work. – Jacob Akkerboom Apr 20 '15 at 13:28
A BenchMarkPlot in another answer still works, but I cannot get the ones in your answer to work for now. – Jacob Akkerboom Apr 20 '15 at 13:45
Anyway your function is still faster. – Jacob Akkerboom Apr 20 '15 at 14:02

This function will be rewritten in C for 10.0.2 and should come down to average-case complexity of $O(n)$ from its current $O(n \log(n))$. Note that the version most users will be bothered to write (and the way we advertized this before in the docpage for DeleteDuplicates) is $O(n^2)$, so most users are probably already winning.

In the meantime, my advice is to use this despite the suboptimal performance, unless it makes your program unusably slow. Premature optimization and all that. The main thing is that we can all rely on it being here for the rest of time, it is one less idiom that requires ugly boilerplate code.

-
Thanks (as always) for responding. Can you tell me if the memory usage will be addressed? I realize that's not a bug, and it may be unavoidable, but it would be great if it used less memory. By the way I'd like to chat again; when might you have time? – Mr.Wizard Jul 20 '14 at 1:37
@Mr.Wizard memory usage will still have to be $O(n)$ in the worst case, when $n = n_{unique}$. Note the weird case in which the image is really large, you might then prefer the $O(n^2)$ time complexity of DeleteDuplicates because the space complexity will be $O(1)$. – Taliesin Beynon Jul 20 '14 at 19:08
Okay. What about special handing of packed arrays to remove duplicates without unpacking? – Mr.Wizard Jul 21 '14 at 4:51
It seems that the rewrite did not make it into 10.0.2. Do you know if it is planned for 10.0.3? – Mr.Wizard Feb 10 '15 at 12:37
@Mr.Wizard I was over-optimistic. This isn't planned for 10.0.3. Hopefully we'll do a bulk port at some point of a lot of these top-level implementations to C. – Taliesin Beynon Feb 23 '15 at 11:10