RE: Value and position in list
- To: mathgroup at smc.vnet.net
- Subject: [mg33436] RE: [mg33403] Value and position in list
- From: "Wolf, Hartmut" <Hartmut.Wolf at t-systems.com>
- Date: Thu, 21 Mar 2002 09:27:19 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
> -----Original Message----- > From: Hugh Goyder [mailto:goyder at rmcs.cranfield.ac.uk] To: mathgroup at smc.vnet.net > Sent: Wednesday, March 20, 2002 7:53 AM > To: mathgroup at smc.vnet.net > Subject: [mg33436] [mg33403] Value and position in list > > > I have a list where each element is a list of three values > {{v11,v12,v13},{v21,v22,v23}...}. > What is the fastest method for finding the position and value of the > element which has the smallest first element. > > I have the following but is it possible to do this more > quickly, perhaps > without two sorts through the data? > > > In[1]:= > $Version > > Out[1]= > 4.1 for Microsoft Windows (June 13, 2001) > > In[2]:= > data=Table[{Random[],Random[]-0.5,10(Random[]-0.5)},{10000}]; > > In[3]:= > Timing[a=Min[Transpose[data][[1]]];p=Position[data,a];{a,p}] > > Out[3]= > {0.33 Second,{0.0000316723,{{1706,1}}}} > > > > > I must also find the element which has the smallest second > element greater > than zero. Here are my attempts so far. Is there a faster method? > > In[4]:= > Timing[a=Infinity;i=0; > > While[i++;i<Length[data],If[0<data[[i,2]]<a,a=data[[i,2]];p=i]];{a,p}] > > Out[4]= > {1.31 Second,{0.0000126855,1134}} > > In[5]:= > Timing[a=Min[Transpose[data][[2]]/.v_/;v\[LessEqual] 0 > \[Rule] Infinity]; > p=Position[data,a];{a,p}] > > Out[5]= > {0.71 Second,{0.0000126855,{{1134,2}}}} > > In[6]:= > Timing[a=Min[Select[Transpose[data][[2]],#>0&]];p=Position[dat > a,a];{a,p}] > > Out[6]= > {0.61 Second,{0.0000126855,{{1134,2}}}} > > > > Thank you for your ideas > > Hugh Goyder > > > Hugh, on my machine In[1]:= SeedRandom[0] In[2]:= data = Table[{Random[], Random[] - 0.5, 10(Random[] - 0.5)}, {10000}]; your method: In[3]:= Timing[a = Min[Transpose[data][[1]]]; p = First /@ Position[data, a]; {a, p}] Out[3]= {0.4 Second, {0.0000418617, {9188}}} You may improve your idea a little bit: In[4]:= Timing[a = Min[b = Transpose[data][[1]]]; p = First /@ Position[b, a]; {a, p}] Out[4]= {0.12 Second, {0.0000418617, {9188}}} However (for this problem size!) it is more economic to use Ordering: In[6]:= Transpose[{#, data[[#]]} &@Ordering[b = Transpose[data][[1]], 1]] // Timing Out[6]= {0.01 Second, {{9188, {0.0000418617, -0.0110595, -1.11659}}}} For your second problem, your best method is In[19]:= Timing[a = Min[Select[Transpose[data][[2]], # > 0 &]]; p = Position[data, a]; {a, p}] Out[19]= {0.962 Second, {0.0000467033, {{1345, 2}}}} Same trick for (slight) improvement: In[24]:= Timing[a = Min[Select[b = Transpose[data][[2]], # > 0 &]]; p = Position[b, a]; {a, p}] Out[24]= {0.661 Second, {0.0000467033, {{1345}}}} Again Ordering may be used: In[26]:= {data[[#]], #} & /@ Ordering[Replace[Transpose[data][[2]], _?NonPositive -> Infinity, {1}], 1] // Timing Out[26]= {0.511 Second, {{{0.451783, 0.0000467033, -4.55627}, 1345}}} The time is used up with the replacement operation (or Select in your case). We search for a more efficient list operation. Now if your data are "reasonably" distributed around zero for their second component (as is in your example) we may do much faster: In[39]:= {data[[#]], #} &@ Catch[Scan[If[Positive[b[[#]]], Throw[#]] &, Ordering[Abs[b = Transpose[data][[2]]]]]] // Timing Out[39]= {0.07 Second, {{0.451783, 0.0000467033, -4.55627}, 1345}} If there is no positive element[[2]], the you'll get Null (the value of Scan). Please regard that all judgement is dependent on problem size: Transpose, Min and Position are essentially O[n]; methods involving Sort (as Ordering does) are O[n log n]. That they are better for this size is based on their efficient kernel implementation. -- Hartmut Wolf