22
$\begingroup$

For Example, list=RandomInteger[{1,100},2000]. Yes,I know Position[list,Max[list]] can do. But it's based on pattern matching! Ordering[list,-1] could find one position but not all. So how to find all the positions of max value of list in a more efficient way?Thank you.

Improve this question
$\endgroup$
3
  • $\begingroup$ list = RandomInteger[{1, 100}, 10^7]; Position[list, Max[list]] // AbsoluteTiming // First only takes 0.8220470second $\endgroup$
    – xyz
    May 16, 2015 at 14:43
  • $\begingroup$ @Shutao Tang Similar topic to find one position of max value of a matrix was discussed in Baidu Tieba. tieba.baidu.com/p/3717089683 (I notice that you are a Chinese student.) But I am not satisfied by the code posted by xzcyr which uses Ordering and only finds one position,so I come to here to ask experts. $\endgroup$
    – WateSoyan
    May 16, 2015 at 15:38
  • $\begingroup$ Related: (900), (1342) $\endgroup$
    – Mr.Wizard
    May 17, 2015 at 5:06

9 Answers 9

Reset to default
20
$\begingroup$

A fast uncompiled alternative without pattern matching is to use the NonzeroPositions property of SparseArray, as long as you're dealing with numerical data.

list = RandomInteger[{1, 100}, 10^7];

SparseArray[Unitize[list - Max[list]] - 1]["NonzeroPositions"]; // RepeatedTiming
(* 0.0855 *)

Position[list, Max[list]] // RepeatedTiming
(* 0.509 *)

compPos[list, Max[list]] // RepeatedTiming (* Marius' solution *)
(* 0.0366 *)

SparseArray[Unitize[list - Max[list]], Automatic, 1][
   "NonzeroPositions"]; // RepeatedTiming (* MichaelE2's solutions *)
(* 0.0663 *)
Improve this answer
$\endgroup$
4
  • $\begingroup$ Is it possible to extend this solution to 2-D? $\endgroup$
    – xyz
    May 17, 2015 at 2:08
  • $\begingroup$ @ShutaoTang It already works in 2D. $\endgroup$
    – C. E.
    May 17, 2015 at 6:21
  • $\begingroup$ SparseArray[Unitize[list - Max[list]], Automatic, 1]["NonzeroPositions"] is a little faster. $\endgroup$
    – Michael E2
    Feb 24, 2018 at 13:48
  • $\begingroup$ @MichaelE2 Thanks, added it to the list. $\endgroup$
    – C. E.
    Feb 24, 2018 at 15:09
19
$\begingroup$

For a 1D list you can also use

Pick[Range@Length@list, list, Max@list]
Improve this answer
$\endgroup$
3
  • $\begingroup$ +1 For me this is the fastest here without requiring a compile, although probably takes more memory because of the range. Weird though, because it's still doing pattern matching yet much faster than Position $\endgroup$
    – Histograms
    May 16, 2015 at 19:23
  • 1
    $\begingroup$ @Histograms, Pick has been shown to often be very fast, e.g. here. The only thing beating it in that case is compiled Select, which is basically what I implemented in my answer. $\endgroup$
    – Marius Ladegård Meyer
    May 16, 2015 at 19:42
  • 1
    $\begingroup$ @Histograms Since version 8 Pick is optimized for packed arrays, bypassing pattern matching in a case like this. See: (11) $\endgroup$
    – Mr.Wizard
    May 17, 2015 at 5:07
13
$\begingroup$

For a one-dimensional list:

compPos = 
 Compile[{{list, _Integer, 1}, {max, _Integer}},
  Block[{copy = list, i = 1},
   Do[
    If[
     list[[j]] == max, copy[[i++]] = j],
    {j, Length[list]}];
   copy[[1 ;; i - 1]]
  ], 
   CompilationTarget -> "C"
  ];

Though I think Position is a good non-compiled alternative in this case, since the "pattern" you use is a number. There won't be any useless matches to this pattern.

Performance Test

list = RandomInteger[{1, 100}, 10^7];
Position[list, Max[list]] // AbsoluteTiming // First

0.8220470

compPos[list, Max[list]] // AbsoluteTiming // First

0.0830048

Obviously, 10 times speed-up

Improve this answer
$\endgroup$
11
$\begingroup$

It is possible to Compile Position itself for machine types (e.g. Integer or Real):

posmax = Compile[{{list, _Integer, 1}}, Position[list, Max@list] ];

Performance:

x = RandomInteger[{1, 100}, 10^7];

Position[x, Max@x] // Timing // First

posmax[x] // Timing // First

0.44754

0.0736

With a C compiler this should be faster still; I'll find out in a few minutes if the Microsoft compiler installs correctly.

Improve this answer
$\endgroup$
14
  • $\begingroup$ I have read every Q&A I can find about installing a C compiler but I still get "Compile::nogen: A library could not be generated from the compiled function." -- I am using Mathematica 10.1 under Windows 7 x64. If anyone can help me with this problem please comment here. $\endgroup$
    – Mr.Wizard
    May 17, 2015 at 6:24
  • $\begingroup$ I tried to get a Borland C++ compiler to work, with no luck as well. I wanted to mention something I found useful, in case you haven't come across it. I have been playing with the CreateExecutable function from the "CCompilerDriver`GenericCCompiler` package. Two options have been instructive: "ShellOutputFunction" -> Print and "CleanIntermediate" -> False. The shell output function allowed me to see what the compiler was complaining about (I discovered that the command line generated for the compiler was wrong); leaving the intermediate files behind also helped. No joy yet though... $\endgroup$
    – MarcoB
    May 17, 2015 at 7:32
  • $\begingroup$ @MarcoB Thanks for the ideas. ShellOutputFunction helps, showing that there seem to be missing .bat files in the installation for the x64 compilers, despite the x64 compilers themselves being present. I'm not sure what to make of that. If I'm going to have to debug an installation I think I'd rather go with GCC; I installed the Microsoft SDK because was supposed to be the most pain-free solution. $\endgroup$
    – Mr.Wizard
    May 17, 2015 at 9:26
  • $\begingroup$ Installing VisualStudio2013 may help...I seldom use C complier-though I know that compilefunction will run faster. $\endgroup$
    – WateSoyan
    May 17, 2015 at 14:59
  • $\begingroup$ Oddly, I found no improvement compiling to C. I suppose that means that the compiled versions of Max and Position are already optimal. (Mac OS) +1 of course. $\endgroup$
    – Michael E2
    May 18, 2015 at 1:51
9
$\begingroup$

My proposal:

Nearest[list -> Automatic, Max[list], {All, 0.5}]

Among non-C solutions, it's slightly faster than Pickett's, but slower than Simon Woods's.

list = RandomInteger[{1, 100}, 10^7];

Needs["GeneralUtilities`"];

Nearest[list -> Automatic, Max[list], {All, 0.5}] // AccurateTiming
SparseArray[Unitize[list - Max[list]] - 1]["NonzeroPositions"] // AccurateTiming (* P. *)
Pick[Range@Length@list, list, Max@list] // AccurateTiming                       (* S.W. *)
(*
  0.0925321
  0.121649
  0.0403738
*)

I have to say I was surprised, because I'd become accustomed to the superiority of SparseArray. But Nearest has been improved in V10. For instance, it takes 2.5 sec on my machine in V9.0.1!! Wow.

Improve this answer
$\endgroup$
5
  • $\begingroup$ Nearest[list -> Automatic, Max[list], {All, 0.5}] gives the warning information in V8 $\endgroup$
    – xyz
    May 17, 2015 at 0:43
  • 2
    $\begingroup$ @ShutaoTang I don't see why one would use this pre-V10, though. Try replacing All by Length@list. (I don't have V8 to debug.) $\endgroup$
    – Michael E2
    May 17, 2015 at 1:28
  • $\begingroup$ This time it works well in V8, thks a lot:-) $\endgroup$
    – xyz
    May 17, 2015 at 1:41
  • $\begingroup$ @ShutaoTang You're welcome. I assume it's slow, like in V9? $\endgroup$
    – Michael E2
    May 17, 2015 at 1:42
  • 1
    $\begingroup$ In V8, @Michael E2, Nearest[list -> Automatic, Max[list], {Length@list, 0.5}]; // AbsoluteTiming takes 4.1367188 sec. Now, I cannot test it in V9 owing to that my OS didn't install V9. $\endgroup$
    – xyz
    May 17, 2015 at 1:47
7
$\begingroup$

If you don't mind using an undocumented internal function, you could try using Random`Private`PositionsOf:

list = RandomInteger[100, 10^7];

r1 = Random`Private`PositionsOf[list, Max[list]]; //RepeatedTiming
r2 = Pick[Range@Length@list, list, Max@list]; //RepeatedTiming

r1 === r2

{0.011, Null}

{0.037, Null}

True

Improve this answer
$\endgroup$
1
  • $\begingroup$ How did this have zero votes 'til now? +1! Although in v10.1 it doesn't yet have the speed. $\endgroup$
    – Mr.Wizard
    Oct 30, 2018 at 3:12
4
$\begingroup$

I think this works Ordering[dat, -Count[dat, Max[dat]]] but it is actually slower than Position[dat,Max[dat]]

This also works, but again, it's still slower

pos1[list_, max_] := Block[{i = 1, l = Length[list]},
  Last[Reap[While[i <= l,
  If[list[[i]] == max, CompoundExpression[Sow[i], i++], i++]]]]]

... unfortunately so is this more compact solution

pos2[list_, max_] := MapIndexed[If[#==max,Sow@#2,##&[]]&,list]

You could try compiling them; I can't use Compile with CompilationTarget->"C" on my system for various reasons. I'd just stick with using Position.

Improve this answer
$\endgroup$
1
$\begingroup$

Since V 13.2 we have PositionLargest and PositionSmallest

list = RandomInteger[{1, 100}, 2000];

PositionLargest[list]

{55, 99, 248, 614, 654, 749, 894, 967, 1029, 1144, 1209, 1392, 1866, 1893, 1932}

It is comparatively fast:

list = RandomInteger[{1, 100}, 10^7];

PositionLargest[list]; // Timing // First

0.173024

Position[list, Max @ list] // Timing // First

0.346482

Improve this answer
$\endgroup$
1
$\begingroup$

Using PositionIndex: (introduced 9th July 2014)

SeedRandom[1];
list = RandomInteger[{1, 10}, 10^7];
PositionIndex[list][Max[list]]; // RepeatedTiming

{0.155408, Null}

Improve this answer
$\endgroup$

Your Answer

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

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