13
$\begingroup$

Starting with

{{0, 0, 0}, {1, 1, 2}, {2, 3, 3}, {3, 4, 5}}

I would like to get

{{0, 2, 3, 5}, {1, 3, 2, 3}}

where the first list returned is the highest value reached in each of the first lists, and the second output is the position of the highest values that were reached in each list.

I have been trying different combinations of Max and Position, but have been unsuccessful.

$\endgroup$
16
$\begingroup$
dat = {{0, 0, 0}, {1, 1, 2}, {2, 3, 3}, {3, 4, 5}};

f[a_] := {#, Position[a, #, 1, 1][[1, 1]]} & @ Max[a]

Transpose[f /@ dat]
{{0, 2, 3, 5}, {1, 3, 2, 3}}

Since your lists are "very long" here is a faster method using my favorite trick: SparseArray Properties.

f2[a_] := {#, First @ SparseArray[UnitStep[a - #]]["AdjacencyLists"]} & @ Max @ a

Transpose[f2 /@ dat]
{{0, 2, 3, 5}, {1, 3, 2, 3}}

Performance comparison on a big array:

dat = RandomInteger[1*^9, {1000, 100000}];

Transpose[f /@ dat]  // Timing // First
Transpose[f2 /@ dat] // Timing // First
3.9

0.515

Update

Reminded of this question it occurs to me that R.M's Ordering solution can be modified to give the desired output by negating the list:

f3[x_] := {x[[#]], #} & @@ Ordering[-x, 1]

Compared in Mathematica 10.1:

r2 = Transpose[f2 /@ dat]; // RepeatedTiming
r3 = Transpose[f3 /@ dat]; // RepeatedTiming

r2 === r3
{0.649, Null}

{0.478, Null}

True
$\endgroup$
  • $\begingroup$ @ Mr Wizard, thanks for the time you have given to this - I will test once Mathematica has evaluated what I have given it! $\endgroup$ – martin Jan 11 '14 at 19:29
  • 1
    $\begingroup$ @Mr.Wizard you do have a fast computer: mathematica.stackexchange.com/questions/28209/… $\endgroup$ – s0rce Jan 11 '14 at 20:29
  • $\begingroup$ @s0rce I use version 7 which seems to be faster than later versions in a number of cases of basic programming. But yes, I have found clock speed to correlate well with Mathematica performance and I run an unlocked i5-2500K CPU at 4.6 GHz. $\endgroup$ – Mr.Wizard Jan 11 '14 at 20:34
  • $\begingroup$ @Mr.Wizard f2 is surprisingly much faster than the typical C solution, when compiled (on my computer). $\endgroup$ – VF1 Jan 11 '14 at 20:58
  • 1
    $\begingroup$ @VF1 I know I'm supposed to be a wizard but I can't see into the future. :-p $\endgroup$ – Mr.Wizard Jan 13 '14 at 16:13
8
$\begingroup$

Using Ordering is another option, and more efficient if you have long lists/sublists:

dat = {{0, 1, 0}, {3, 1, 2}, {2, 3, 4}, {5, 3, 4}}; (* different example with a unique max *)
With[{l = #}, Composition[{l[[#]], #} &, Last, Ordering]@#] & /@ dat // Transpose
(* {{1, 3, 4, 5}, {2, 1, 3, 1}} *)

Note that if you have more than one element that is the maximum, then Ordering will only give you the last index.

$\endgroup$
  • 1
    $\begingroup$ But that's not the example that martin gave; I assume he specifically chose an example with repeated maximums, and wanted only the first position. $\endgroup$ – Mr.Wizard Jan 11 '14 at 18:53
  • $\begingroup$ I have very long lists! Many thanks :) $\endgroup$ – martin Jan 11 '14 at 18:53
  • $\begingroup$ @Mr.Wizard Well, we don't know and that's the problem with underspecified questions :) $\endgroup$ – rm -rf Jan 11 '14 at 18:53
  • $\begingroup$ @ Mr Wizard, that is true - will try all now $\endgroup$ – martin Jan 11 '14 at 18:54
  • $\begingroup$ @martin Which result do you actually want? $\endgroup$ – Mr.Wizard Jan 11 '14 at 18:54
4
$\begingroup$

Another option:

list = {{0, 0, 0}, {1, 1, 2}, {2, 3, 3}, {3, 4, 5}}

maxWithPosition[list_] := 
 With[{max = Max /@ list}, {max, 
   MapThread[Position, {list, max}][[All, 1, 1]]}]

maxWithPosition[list]
{{0, 2, 3, 5}, {1, 3, 2, 3}}
$\endgroup$
2
$\begingroup$

If speed is an issue, and you're using numeric values, I would go for Compile. This will only work for data types that are compilable, such as _Integer or _Real, but those seem to be the only ones OP is interested in.

Here's the fastest I could come up with:

Module[{cfn1},
 cfn1 = Compile[{{list, _Integer, 1}},
        Module[{temp, max = First@list, maxp = 1},
     Do[temp = list[[i]]; 
      If[temp > max, max = temp; maxp = i], {i, Length@list}];
     {max, maxp}
     ], CompilationTarget -> "C"];
 singlePassC[arg : {__Integer}] := cfn1[arg];
 singlePassC[{}] = {};
 ]

I noticed some interesting timing trends, though, compared to Mr.Wizard's function. Consider the more Mathematica-like Compiled implementation for finding the maximum position:

Module[{cfn1},
 cfn1 = Compile[{{list, _Integer, 1}},
    With[{max = Max@list}, {{{max}}, Position[list, max]}],
    CompilationTarget -> "C"];
 twoPassC[arg : {__Integer}] := cfn1[arg][[All, 1, 1]];
 twoPassC[{}] = {};
 ]
     (* Mr. Wizard's non-compiled implementation *)
sparseArrayME[
  a_] := {#, First@SparseArray[UnitStep[a - #]]["AdjacencyLists"]} &@ Max@a

All of these work:

sparseArrayME@{3, 5, 4} ===
 singlePassC@{3, 5, 4} ===
 twoPassC@{3, 5, 4} ===
 {5, 2}
 (* True *)

But notice these peculiar timings:

dat = RandomInteger[1*^9, {100000000}];
datm = RandomInteger[1*^9, {1000, 100000}];
test[f_] := f@dat // Timing // First
testm[f_] := f /@ datm // Transpose // Timing // First
funcs = {sparseArrayME, singlePassC, twoPassC};
{{"Data Type", "Sparse Array", "Single Pass C", "Two Pass C"},
  Prepend[test /@ funcs, "Single Array"],
  Prepend[testm /@ funcs, "Matrix"]} // TableForm

results

So Mr.Wizard's uncompiled SparseArray properties is faster than a compiled Position when applied to many smaller-sized sublists. I doubt this is because of the deeper nesting I am forced to make in twoPassC's cfn1 which I then extract from in the actual function - that shouldn't be what takes so long.

$\endgroup$

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.