17
$\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.

$\endgroup$
  • $\begingroup$ list = RandomInteger[{1, 100}, 10^7]; Position[list, Max[list]] // AbsoluteTiming // First only takes 0.8220470second $\endgroup$ – xyz May 16 '15 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 '15 at 15:38
  • $\begingroup$ Related: (900), (1342) $\endgroup$ – Mr.Wizard May 17 '15 at 5:06
18
$\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 *)
$\endgroup$
  • $\begingroup$ Is it possible to extend this solution to 2-D? $\endgroup$ – xyz May 17 '15 at 2:08
  • $\begingroup$ @ShutaoTang It already works in 2D. $\endgroup$ – C. E. May 17 '15 at 6:21
  • $\begingroup$ SparseArray[Unitize[list - Max[list]], Automatic, 1]["NonzeroPositions"] is a little faster. $\endgroup$ – Michael E2 Feb 24 '18 at 13:48
  • $\begingroup$ @MichaelE2 Thanks, added it to the list. $\endgroup$ – C. E. Feb 24 '18 at 15:09
17
$\begingroup$

For a 1D list you can also use

Pick[Range@Length@list, list, Max@list]
$\endgroup$
  • $\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 '15 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 '15 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 '15 at 5:07
12
$\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

$\endgroup$
10
$\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.

$\endgroup$
  • $\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 '15 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 '15 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 '15 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 '15 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 '15 at 1:51
8
$\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.

$\endgroup$
  • $\begingroup$ Nearest[list -> Automatic, Max[list], {All, 0.5}] gives the warning information in V8 $\endgroup$ – xyz May 17 '15 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 '15 at 1:28
  • $\begingroup$ This time it works well in V8, thks a lot:-) $\endgroup$ – xyz May 17 '15 at 1:41
  • $\begingroup$ @ShutaoTang You're welcome. I assume it's slow, like in V9? $\endgroup$ – Michael E2 May 17 '15 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 '15 at 1:47
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.

$\endgroup$
2
$\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

$\endgroup$
  • $\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 '18 at 3:12

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.