Re: the simplest way?
- To: mathgroup at smc.vnet.net
- Subject: [mg16426] Re: the simplest way?
- From: Hartmut Wolf <hw at gsmail01.darmstadt.dsh.de>
- Date: Sat, 13 Mar 1999 02:21:41 -0500
- Organization: debis Systemhaus
- References: <7c58om$7lr@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Dear Antoine;
Antoine Zahnd schrieb:
>
> I have two questions with lists, each time to avoid the Length function.
>
> 1) For example, how to write a function that will go thru the elements of a
> list of
> integers, and will return False as soon as an odd number is found, without
> using
> Length?
>
> With Length it is easy, but not so clean ...
> f[l_]:= Block[{k},For[k=1,k<=Length[l],k++,If[OddQ[l[[k]]],Return[True]]];
> False];
>
> 2) Is it possible to write the following function without Length?
>
> l={1,2,3};
> Table[ReplacePart[l,l[[i]]-1,i],{i,1,Length[l]}]
> {{0,2,3},{1,1,3},{1,2,2}}
>
> More generally, is there a way to write something like:
> (for x in l ... collect (f x) ) , and the collection of the (f x) are
> returned
> in a list?
>
> I don't see how to write a Lisp style dolist function in Mathematica
> without the Length!
>
Antoine, I believe your problem is: you think Lisp in Mathematica.
That's not bad for functional programming, but it is indeed bad for
treating with large Lists! Quite contrary to Lisp, Lists in Mathematica
are not implemented as nested pairs, but as arrays. (Shocking to you??
It shouldn't, that indeed speeds up many core operations of Mathematica,
where it is good at. The dark side of course is operating with very,
very long Lists.) So for your computational purposes you have to look
out (again) for the appropriate idoms.
1) Length is a _very_ performant operation:
In[11]:= l=2*Range[100000];//Timing
Out[11]= {1.342 Second,Null}
In[12]:= Length[l]//Timing
Out[12]= {0. Second,100000}
You also see that Append-ing and Prepend-ing make it in the same time
with Mathematica:
In[13]:= l1=Append[l, 3];//Timing
Out[13]= {0.12 Second,Null}
In[14]:= l2=Prepend[l, 3];//Timing
Out[14]= {0.101 Second,Null}
Mapping a function over a List is fast: doing that for OddQ takes about
1 second for 100000 entries on my machine (Pentium P54 166 MHz, 256
MByte) and that's not bad (It includes construction of a new List, and
to me that seems to be the quickest way to make up the result, beware of
recursively appending).
In[21]:= lq1= OddQ/@ l1;//Timing
Out[21]= {1.111 Second,Null}
In[22]:= lq2= OddQ/@ l2;//Timing
Out[22]= {1.111 Second,Null}
Or is not executed in the standard way: applying it to the lists l1
(with the odd number at the end) and l2 (with the odd number at the
beginning) does indeed result in a different timing:
In[27]:= Or @@ lq1//Timing
Out[27]= {0.12 Second,True}
In[28]:= Or @@ lq2//Timing
Out[28]= {0.08 Second,True}
2) So instead of explicit looping, map over e.g. Ranges. MappingAt ist
good, when indexing would result in a look-up for changed upvalues.
In[34]:= ll=Range[10]
Out[34]= {1,2,3,4,5,6,7,8,9,10}
In[36]:= MapAt[#-1&,ll, {#}]& /@ Range[10]
Out[36]=
{{0,2,3,4,5,6,7,8,9,10},{1,1,3,4,5,6,7,8,9,10},{1,2,2,4,5,6,7,8,9,10},
{1,2,3,3,5,6,7,8,9,10},{1,2,3,4,4,6,7,8,9,10},{1,2,3,4,5,5,7,8,9,10},
{1,2,3,4,5,6,6,8,9,10},{1,2,3,4,5,6,7,7,9,10},{1,2,3,4,5,6,7,8,8,10},
{1,2,3,4,5,6,7,8,9,9}}
3) I'm not quite shure about what you want, isn't it just?
f /@ Select[l, predicate]
If you really need to work with very large Lists you can resort to Lisp
style, but then using streams instead of Lists, avoiding Appending, etc.
using MakeStream[a, stream] and avoiding to clutter precious core memory
with many intermediate results of long "List"s thanks to delayed
evaluation (Attributes[MakeStream] == {HoldRest}). See Roman Maeder:
"The Mathematica Programmer". Deplorably he only treats infinite
streams.
---Hartmut
__________________________________________________
Hartmut Wolf, debis Systemhaus, Darmstadt, Germany
=============[mailto:hwolf at debis.com]=============