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

Question

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?

Answer 1

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.

Answer 2

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. :-/

Answer 3

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.