       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:=
> \$Version
>
> Out=
> 4.1 for Microsoft Windows (June 13, 2001)
>
> In:=
> data=Table[{Random[],Random[]-0.5,10(Random[]-0.5)},{10000}];
>
> In:=
> Timing[a=Min[Transpose[data][]];p=Position[data,a];{a,p}]
>
> Out=
> {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:=
> 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=
> {1.31 Second,{0.0000126855,1134}}
>
> In:=
> Timing[a=Min[Transpose[data][]/.v_/;v\[LessEqual] 0
> \[Rule] Infinity];
>   p=Position[data,a];{a,p}]
>
> Out=
> {0.71 Second,{0.0000126855,{{1134,2}}}}
>
> In:=
> Timing[a=Min[Select[Transpose[data][],#>0&]];p=Position[dat
> a,a];{a,p}]
>
> Out=
> {0.61 Second,{0.0000126855,{{1134,2}}}}
>
>
>
> Thank you for your ideas
>
> Hugh Goyder
>
>
>

Hugh,

on my machine

In:= SeedRandom
In:=
data = Table[{Random[], Random[] - 0.5, 10(Random[] - 0.5)}, {10000}];

In:=
Timing[a = Min[Transpose[data][]]; p = First /@ Position[data, a]; {a,
p}]

Out=
{0.4 Second, {0.0000418617, {9188}}}

You may improve your idea a little bit:

In:=
Timing[a = Min[b = Transpose[data][]];
p = First /@ Position[b, a]; {a, p}]

Out=
{0.12 Second, {0.0000418617, {9188}}}

However (for this problem size!) it is more economic to use Ordering:

In:=
Transpose[{#, data[[#]]} &@Ordering[b = Transpose[data][], 1]] // Timing

Out=
{0.01 Second, {{9188, {0.0000418617, -0.0110595, -1.11659}}}}

In:=
Timing[a = Min[Select[Transpose[data][], # > 0 &]];
p = Position[data, a]; {a, p}]

Out=
{0.962 Second, {0.0000467033, {{1345, 2}}}}

Same trick for (slight) improvement:

In:=
Timing[a = Min[Select[b = Transpose[data][], # > 0 &]];
p = Position[b, a]; {a, p}]

Out=
{0.661 Second, {0.0000467033, {{1345}}}}

Again Ordering may be used:

In:=
{data[[#]], #} & /@
Ordering[Replace[Transpose[data][], _?NonPositive -> Infinity, {1}],
1] // Timing

Out=
{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:=
{data[[#]], #} &@
Catch[Scan[If[Positive[b[[#]]], Throw[#]] &,
Ordering[Abs[b = Transpose[data][]]]]] // Timing

Out=
{0.07 Second, {{0.451783, 0.0000467033, -4.55627}, 1345}}

If there is no positive element[], 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

```

• Prev by Date: RE: Rolling up some integers
• Next by Date: Re:
• Previous by thread: Re: Value and position in list
• Next by thread: Approximation of a Function