Groups | Search | Server Info | Keyboard shortcuts | Login | Register [http] [https] [nntp] [nntps]


Groups > comp.soft-sys.math.mathematica > #6053 > unrolled thread

efficiently testing a list

Started byzb <zaeem.burq@gmail.com>
First post2011-10-30 09:34 +0000
Last post2011-11-02 07:05 +0000
Articles 3 — 3 participants

Back to article view | Back to comp.soft-sys.math.mathematica


Contents

  efficiently testing a list zb <zaeem.burq@gmail.com> - 2011-10-30 09:34 +0000
    Re: efficiently testing a list "Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com> - 2011-11-01 05:09 +0000
    Re: efficiently testing a list Ray Koopman <koopman@sfu.ca> - 2011-11-02 07:05 +0000

#6053 — efficiently testing a list

Fromzb <zaeem.burq@gmail.com>
Date2011-10-30 09:34 +0000
Subjectefficiently testing a list
Message-ID<j8j5o2$fab$1@smc.vnet.net>
Consider the list of pairs:

List = Table[ {a[i],b[i]} , {i,1,N} ].

or

List = { {a[1],b[1]} , {a[2],b[2]} , {a[3],b[3]} , ... ,
{a[N],b[N]} },

and a given function f[a].

What is the quickest way of testing if all elements of List satisfy
f[a[i]] < b[i].

[toc] | [next] | [standalone]


#6097

From"Oleksandr Rasputinov" <oleksandr_rasputinov@hmamail.com>
Date2011-11-01 05:09 +0000
Message-ID<j8nuti$ehp$1@smc.vnet.net>
In reply to#6053
On Sun, 30 Oct 2011 09:34:58 -0000, zb <zaeem.burq@gmail.com> wrote:

> Consider the list of pairs:
>
> List = Table[ {a[i],b[i]} , {i,1,N} ].
>
> or
>
> List = { {a[1],b[1]} , {a[2],b[2]} , {a[3],b[3]} , ... ,
> {a[N],b[N]} },
>
> and a given function f[a].
>
> What is the quickest way of testing if all elements of List satisfy
> f[a[i]] < b[i].
>

While slightly more obscure than the suggestions already given, the  
following implements short-circuit evaluation:

LengthWhile[data, f[#[[1]]] < #[[2]] &] == Length[data]

This can be faster if the condition is violated somewhere near the  
beginning of a long list:

data = RandomInteger[{1, 100}, {1*^6, 2}];
f[x_] := 1/x;

Timing[
  LengthWhile[data, f[#[[1]]] < #[[2]] &] == Length[data]
]

{0.141, False}

Timing[
  (* Bob Hanlon's suggestion *)
  And @@ (f[#[[1]]] < #[[2]] & /@ data)
]

{4.031, False}

On the other hand, if the condition never fails, it will be slower:

data = RandomInteger[{2, 100}, {1*^6, 2}];
f[x_] := 1/x;

Timing[
  LengthWhile[data, f[#[[1]]] < #[[2]] &] == Length[data]
]

{6.016, True}

Timing[
  (* Bob Hanlon's suggestion *)
  And @@ (f[#[[1]]] < #[[2]] & /@ data)
]

{4.141, True}

So, given these choices, there is no absolute quickest method. Which is  
faster in practice will depend on the properties of your list.

[toc] | [prev] | [next] | [standalone]


#6105

FromRay Koopman <koopman@sfu.ca>
Date2011-11-02 07:05 +0000
Message-ID<j8qq3n$q5$1@smc.vnet.net>
In reply to#6053
On Oct 30, 2:34 am, zb <zaeem.b...@gmail.com> wrote:
> Consider the list of pairs:
>
> List = Table[ {a[i],b[i]} , {i,1,N} ].
>
> or
>
> List = { {a[1],b[1]} , {a[2],b[2]} , {a[3],b[3]} , ... ,
> {a[N],b[N]} },
>
> and a given function f[a].
>
> What is the quickest way of testing if all elements of List satisfy
> f[a[i]] < b[i].

"List" and "N" are protected symbols in Mathematica. Use names
that start with lowercase letters, such as "abList" and "n".

The answer to your question depends on how fast your function f is
and how many terms in abList must be checked.

The faster f is, and the more likely it is that f[a[i]] < b[i]
will be true for all i, then the more likely it is that

  And @@ ( f@#1 < #2 & @@@ abList )

will be satisfactory (though there may be faster ways in this case,
especially if f is Listable).

On the other hand, the slower f is, and the more likely it is that
f[a[i]] < b[i] will be false for some small value of i, then the
more you will want something like David Bevan's mapAndF from
https://groups.google.com/group/comp.soft-sys.math.mathematica/browse_frm/thread/7196783d6bf28c7e

  If[Scan[If[f@#[[1]]>=#[[2]],Return@False]&,abList],Null,False,True]

The downside of that is that it is very slow if all the terms in
abList must be checked.

A compromise procedure would be something like the suggestions of
Carl Woll and Chris Chiasson in
https://groups.google.com/group/comp.soft-sys.math.mathematica/browse_frm/thread/966d232547bae196

  f@#1 < #2 & @@@ And @@ abList

[toc] | [prev] | [standalone]


Back to top | Article view | comp.soft-sys.math.mathematica


csiph-web