10
$\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$
  • $\begingroup$ MaximalBy is intended to do this. It is new in version 10. $\endgroup$ – C. E. Jan 2 '15 at 1:19
  • 2
    $\begingroup$ @Pickett Indeed, but it may not be applicable. See my just-posted answer. $\endgroup$ – Mr.Wizard Jan 2 '15 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$ – Vladimir Reshetnikov Jan 2 '15 at 1:33
  • $\begingroup$ Somewhat related: (19300) $\endgroup$ – Mr.Wizard Jan 2 '15 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 '15 at 3:03
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$
  • 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$ – Vladimir Reshetnikov Jan 2 '15 at 1:30
  • $\begingroup$ @Vladimir Okay, I think I understand what you are saying. $\endgroup$ – Mr.Wizard Jan 2 '15 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$ – DumpsterDoofus Jan 2 '15 at 1:55
  • $\begingroup$ @Dumpster Thanks. I'll abolish that nonsense entirely now. $\endgroup$ – Mr.Wizard Jan 2 '15 at 1:58
  • 3
    $\begingroup$ That's a cool use of Fold!(+1) $\endgroup$ – DumpsterDoofus Jan 2 '15 at 2:01

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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