11
$\begingroup$

I need a function to find max element of a list according to some custom ordering function, assuming that the function implements a total order (elements being compared might not even be numbers). Unlike Sort, the predefined Max function does not accept a custom ordering function. A naïve solution would be to use Sort[list, p]〚1〛, but this would unnecessarily sort the whole list, while I only need to find the first element.

I ended up defining

max[list_, p_] := list[[Ordering[list, 1, p][[1]] ]];

and it works fine from performance point of view. But I wonder if there is a more simple or natural way to do this task. Is there a predefined function solving this problem that I missed?

$\endgroup$
5
  • $\begingroup$ MaximalBy is intended to do this. It is new in version 10. $\endgroup$
    – C. E.
    Jan 2, 2015 at 1:19
  • 2
    $\begingroup$ @Pickett Indeed, but it may not be applicable. See my just-posted answer. $\endgroup$
    – Mr.Wizard
    Jan 2, 2015 at 1:21
  • 1
    $\begingroup$ MaximalBy requires a mapping from elements of the list to some expressions that can be compared canonically. It's not always easy to construct such a mapping if I only have a function that can compare 2 elements. $\endgroup$ Jan 2, 2015 at 1:33
  • $\begingroup$ Somewhat related: (19300) $\endgroup$
    – Mr.Wizard
    Jan 2, 2015 at 2:07
  • $\begingroup$ By the way list ~Extract~ Ordering[list, 1, p] is a bit cleaner than your present formulation. $\endgroup$
    – Mr.Wizard
    Jan 2, 2015 at 3:03

1 Answer 1

8
$\begingroup$

If your operation can be converted to a canonical ranking rather than a pairwise comparison then you can use MaximalBy introduced in version 10.

If not a good approach to a single pass through a list is Fold. Here is a function using that:

foldMax[list_, p_] := Fold[If[p[##], ##] &, list]

This proves to be faster in some cases than using Ordering (in your function):

x = RandomReal[9, 5000000];

max[x, Less]     // AbsoluteTiming
foldMax[x, Less] // AbsoluteTiming
{1.209069, 4.32482*10^-6}

{0.430025, 4.32482*10^-6}
$\endgroup$
9
  • 2
    $\begingroup$ Search for the max element requires 1 pass thru the list, that is $O(n)$, while sorting is $O(n\ln n)$. $\endgroup$ Jan 2, 2015 at 1:30
  • $\begingroup$ @Vladimir Okay, I think I understand what you are saying. $\endgroup$
    – Mr.Wizard
    Jan 2, 2015 at 1:49
  • 2
    $\begingroup$ I think the first sentence also isn't quite right: just because you have a pairwise ordering function doesn't mean that there is a significant $O(n^2)$ or $O(n\log n)$ performance penalty, as that would only be the case when you want to construct the entire total ordering of the list. In the case of a max element search, constructing the entire total ordering is not necessary, and instead the max search is $O(n)$, so there is no performance penalty. Still, I don't know of a built-in way to find the max... maybe you could make your own custom $Max function, if performance really was crucial? $\endgroup$ Jan 2, 2015 at 1:55
  • $\begingroup$ @Dumpster Thanks. I'll abolish that nonsense entirely now. $\endgroup$
    – Mr.Wizard
    Jan 2, 2015 at 1:58
  • 3
    $\begingroup$ That's a cool use of Fold!(+1) $\endgroup$ Jan 2, 2015 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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