Take the 2-minute tour ×
Mathematica Stack Exchange is a question and answer site for users of Mathematica. It's 100% free, no registration required.

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?
share|improve this question

3 Answers 3

up vote 24 down vote accepted

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. This can be seen by evaluating the following code

DeleteDuplicatesBy (*to autoload some stuff*)
ClearAttributes[DeleteDuplicatesBy, ReadProtected]
oldCP = $ContextPath; (*all context stuff is just to make things more readable*)
    $ContextPath = 
 Join[$ContextPath, {"Macros`Evaluation`PackagePrivate`", 
       "GeneralUtilities`System`PackagePrivate`"}]
    DeleteDuplicatesBy // Information
    $ContextPath = oldCP

The most relevant definition is

Self : DeleteDuplicatesBy[expr_, f_] := 
 Module[{r$}, 
      r$ = Which[! 
     Quiet[TrueQ[! AtomQ[expr] || AssociationQ[expr] || 
        Head[expr] === SparseArray]], 
    Message[DeleteDuplicatesBy::normal, 1, "HoldForm"[Self]]; 
    Macros`$FailRHS, True, 
        Macros`HoldSequence[
         Which[ListQ[expr], Values[GroupBy[expr, f, First]], 
          AssociationQ[expr], 
          Association[Values[GroupBy[Normal[expr], f@*Last, First]]], 
          Head[expr] === SparseArray, 
          DeleteDuplicates[expr, f[#1] === f[#2] &], True, 
          expr[[Values[
             GroupBy[Table[{f[expr[[i]]], i}, {i, Length[expr]}], First, 
              First]][[All, 2]]]]]]]; 
      Macros`ReleaseHoldSequence[r$] /; ! 
    MatchQ[r$, 
         Macros`$FailRHS | Macros`HoldSequence[Macros`$FailRHS]]]

If we predict where we will end up for a list, this 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|>

The undocumented System` function IndexBy also does not work with held expressions. It also doesn't give a message when the first argument is bad but still applies some rules.

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

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.

share|improve this answer
1  
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 at 12:39
    
I note that for an association argument there are four conversions!: assoc -> list -> assoc -> list -> assoc –  Simon Woods Jul 19 at 13:14
1  
@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 at 13:51
    
@Mr.Wizard turns out SortBy can have side effects too. –  Jacob Akkerboom Jul 19 at 13:55
1  
@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 at 8:04

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^(# + 1)] &,
  Range[3, 22],
  "IncludeFits" -> True
]

enter image description here

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

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

enter image description here

And a lower duplicate density:

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

enter image description here

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^(# + 1)] &,
  Range[3, 22],
  "IncludeFits" -> True
]

enter image description here

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

share|improve this answer
3  
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 at 21:40
    
@TaliesinBeynon Thanks for the instruction. :-) –  Mr.Wizard Jul 20 at 2:04

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.

share|improve this answer
    
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 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 at 19:08
    
Okay. What about special handing of packed arrays to remove duplicates without unpacking? –  Mr.Wizard Jul 21 at 4:51

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.