Re: Partitioning lists
- To: mathgroup at smc.vnet.net
- Subject: [mg20530] Re: [mg20439] Partitioning lists
- From: "Wolf, Hartmut" <hwolf at debis.com>
- Date: Sat, 30 Oct 1999 00:13:50 -0400
- Organization: debis Systemhaus
- References: <199910260433.AAA05986@smc.vnet.net.>
- Sender: owner-wri-mathgroup at wolfram.com
DIAMOND Mark schrieb:
>
> I would like a function f to split a list as follows
>
> a={1,2,3,4,5,6}
> f[a] =
> {
> {{1},{2,3,4,5,6}},
> {{1,2},{3,4,5,6}},
> {{1,2,3},{4,5,6}},
> {{1,2,3,4},{5,6}},
> {{1,2,3,4,5},{6}}
> }
>
> I can do this as
>
> Table[{Take[a, i], Drop[a, i]}, {i, 1, Length[a] - 1}]
>
> but it *looks* as though it is very inefficient. Is it?
> It also looks as though there should be a way of using Partition simply to
> chop a list between positions i and i+1, but
> I cannot see how to do it. Any suggestions?
>
> mark diamond
Hello Mark,
I think your first approach is perfectly right, Take and Drop are thee
_Mathematica_ functions to do that (Partition has quite another use).
As to what matters performance, there is *only* one way to judge on
that, namely measument.
In[1]:= n = 1000;
In[2]:= a = Range[n]; // Timing
Out[2]= {0. Second, Null}
Your method:
In[3]:= Table[{Take[a, i], Drop[a, i]}, {i, 1, Length[a] - 1}]; //
Timing
Out[3]= {0.37 Second, Null}
and I think that's pretty fast.
A fundamentally different approach would be to build an index structure
and mapping thereover an array of your application:
In[4]:= b = Table[{Range[i], Range[i + 1, n]}, {i, 1, n - 1}]; // Timing
Out[4]= {0.351 Second, Null}
Compare this time with that one above. Does this prove that your way is
indeed the fastes possible? I think so, but we can't be shure, observe:
In[5]:= anArray = Array[c, {n}]; // Timing
Out[5]= {0.02 Second, Null}
(Just a model for our application array.) Now
In[6]:= Map[Part[anArray, #] & , b, {3}]; // Timing
Out[6]= {43.162 Second, Null}
In[7]:= Map[Extract[anArray, #] & , b, {3}]; // Timing
Out[7]= {50.032 Second, Null}
That takes some time (to map and to form a new structure composed of a
million leave elements!) However
In[8]:= d = Map[anArray[[#]] & , b, {2}]; // Timing
Out[8]= {3.175 Second, Null}
Astonishing, isn't it? But observe
In[11]:= e = d[[555, 1]]; // Timing
Out[11]= {1.082 Second, Null}
Much time to access these elements, but
In[12]:= e; // Timing
Out[12]= {0. Second, Null}
is short (of course). Now, what made Out[11] that fast? First I concede,
I don't know, but I might speculate: Out[11] did only part of the work
as specified
"expr[[{i1,i2,...}] gives a list of the parts i1, i2,... of expression",
i.e. it did it lazy, the list wasn't really build up. Only thereafter,
when beginning to use that object d[[{1,2,3,...,555}]] it will be
evaluated and the list is then being build (and of course it's then that
you have to pay for it).
Of course this is a clever scheme which avoids spoiling computational
resources for intermediate parts of your calculation which are not
explicitly used.
Yet for us it's more difficult to judge on the performance of the
primitives, let even by looking.
Kind regards, hw
- References:
- Partitioning lists
- From: "DIAMOND Mark" <noname@noname.com>
- Partitioning lists