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?

Improve this question
$\endgroup$
5
  • $\begingroup$ MaximalBy is intended to do this. It is new in version 10. $\endgroup$ Commented Jan 2, 2015 at 1:19
  • 2
    $\begingroup$ @Pickett Indeed, but it may not be applicable. See my just-posted answer. $\endgroup$ Commented 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$ Commented Jan 2, 2015 at 1:33
  • $\begingroup$ Somewhat related: (19300) $\endgroup$ Commented 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$ Commented Jan 2, 2015 at 3:03

1 Answer 1

Reset to default
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}
Improve this answer
$\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$ Commented Jan 2, 2015 at 1:30
  • $\begingroup$ @Vladimir Okay, I think I understand what you are saying. $\endgroup$ Commented 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$ Commented Jan 2, 2015 at 1:55
  • $\begingroup$ @Dumpster Thanks. I'll abolish that nonsense entirely now. $\endgroup$ Commented Jan 2, 2015 at 1:58
  • 3
    $\begingroup$ That's a cool use of Fold!(+1) $\endgroup$ Commented Jan 2, 2015 at 2:01

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.