Re: Tilting at Windmills?
- To: mathgroup at smc.vnet.net
- Subject: [mg62118] Re: Tilting at Windmills?
- From: "Jens-Peer Kuska" <kuska at informatik.uni-leipzig.de>
- Date: Sat, 12 Nov 2005 03:31:15 -0500 (EST)
- Organization: Uni Leipzig
- References: <dl1jta$1m$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hi,
that are very complicated functions to do
myFunct[lst_] := Partition[
{lst[[1]], Sequence @@
Flatten[({#, #, #, #} ) & /@ Rest[Most[lst]]],
lst[[-1]]},
2]
and it seems that it is quite slow compared with
testList = Range[200000];
Timing[myFunct[testList]] // First
0.375 Second
Regards
Jens
"Matt" <anonmous69 at netscape.net> schrieb im
Newsbeitrag news:dl1jta$1m$1 at smc.vnet.net...
| Hello,
| Where there's a chance of success, I tend to
agonize over details of
| implementation. Memory usage is one such area.
Here is a statement of
| a problem I was trying to solve in Mathematica:
|
| Given a list of the following
form:{x1,x2,x3,...,xn-1,xn} I want to
| develop an algorithm that will iterate over the
input list to produce
| output of the following
|
form:{x1,x2,x2,x2,x2,x3,x3,x3,x3,x4,x4,x4,x4,x5,...,xn-2,xn-1,xn-1,xn-1,xn-1,xn}
| which will then need to be partitioned to end up
in the following form:
|
{{x1,x2},{x2,x2},{x2,x3},{x3,x3},{x3,x4},{x4,x4},{x4,x5},...,{xn-2,xn-1},{xn-1,xn-1},{xn-1,xn}}
| which means that if I had a flattened list of
length'n' as input, then
| the new flattened list would have a length of
4*(n-2)+2
|
| Here is my first solution to this problem, along
with a test harness
| for validation:
|
|
Clear[createListOfListsForCobwebTypePlot,testRun];
|
createListOfListsForCobwebTypePlot[x:(_List?((Length[#]>0&&Depth[#]\[Equal]2)&)),debugOn:(_?(#\[Element]Booleans&)):False]:=Module[{tempList={},lengthOfInList,retLength,ret},If[debugOn\[Equal]True,
| lengthOfInList=Length[x];
| Print["Length of input list:
",lengthOfInList]
| ];
| (tempList={tempList,#,#,#,#})&/@x;
| If[debugOn\[Equal]True,
| Print["Out list before flattening:
",tempList]
| ];
|
ret=Delete[Flatten[tempList],{{1},{2},{3},{-3},{-2},{-1}}];
| If[debugOn\[Equal]True,
| retLength=Length[ret];
| Print["Length of out list: ",retLength];
| Print["Out list length equal to 4(n-2) +
| 2?\n",retLength\[Equal]4 (lengthOfInList-2)+2]
| ];
| Partition[ret,2]
| ];
|
testRun[debugOn:(_?(#\[Element]Booleans&)):False]:=Module[{testList},testList=Range[20];
|
Print[createListOfListsForCobwebTypePlot[testList,debugOn]];];
| testRun[True]
|
| Although it seems to work just fine, I'm not
satisfied with it because
| of this line:
| (tempList={tempList,#,#,#,#})&/@x;
|
| It seems very bad to me to keep creating a new
list of objects as more
| elements are added, i.e. in C or C++ I would
allocate the appropriate
| amount of memory up front, and then fill the
'slots'. One list, one
| memory allocation. So, I thought to myself
about how I might
| 'allocate' or 'reserve' memory up front in
Mathematica. What I figured to do,
| was to generate a table object with enough
elements (with dummy values)
| up front and then use the object[[n]]=newValue
paradigm to replace the
| dummy value with a real value. That way,
there's only one list
| allocated up front. Because my input list was
going to contain
| elements all with a head of Integer, I decided
to create the dummy
| table with Integer elements. If my experiment
proved fruitful, I would
| have modified it to contend with other atomic
types as appropriate.
| Here is what my modified and 'streamlined'
function along with its
| accompanying test harness is:
|
|
Clear[createListOfListsForCobwebTypePlotAlt,testRun];
|
createListOfListsForCobwebTypePlotAlt[x:(_List?((Length[#]>0&&Depth[#]==2)&)),debugOn:(_?(#\[Element]Booleans&)):False]:=Module[{tempList={},lengthOfInList,allocLength,allocList,index=1,retLength,ret},
| lengthOfInList=Length[x];
| allocLength=4 lengthOfInList;
| allocList=Table[11,{allocLength}];
| If[debugOn\[Equal]True,
| Print["Length of input list:
",lengthOfInList];
| Print["Length of allocList:
",allocLength]
| ];
|
|
Fold[(allocList[[#1]]=#2;allocList[[#1+1]]=#2;allocList[[#1+2]]=#2;allocList[[#1+3]]=#2;#1+4)&,index,x];
|
ret=Delete[allocList,{{1},{2},{3},{-3},{-2},{-1}}];
| If[debugOn\[Equal]True,
| retLength=Length[ret];
| Print["Length of out list: ",retLength];
| Print["Out list length equal to 4(n-2) +
| 2?\n",retLength\[Equal]4 (lengthOfInList-2)+2];
| ];
| Partition[ret,2]
| ];
|
testRun[debugOn:(_?(#\[Element]Booleans&)):False]:=Module[{testList},testList=Range[20];
|
Print[createListOfListsForCobwebTypePlotAlt[testList,debugOn]];];
| testRun[True]
|
| This produces identical results as the previous
solution. Now, for the
| test:
|
| testList=Range[200000];
|
Timing[Do[createListOfListsForCobwebTypePlot[testList],
{1}]][[1]]
|
Timing[Do[createListOfListsForCobwebTypePlotAlt[testList],
{1}]][[1]]
|
| With results of
| 1.078 Second
| 2.109 Second
|
| much to my chagrin. You may be wondering why
I'm doing this. The
| reason is that I want to learn and establish
proper Mathematica discipline with
| primitive operations such as this, so that I
don't have to break bad
| habits later. I have a feeling the answer is
going to be something
| along the lines of: "There's not much you can
do about it, and in fact
| there really is no memory allocation schemes
that you can take
| advantage of in Mathematica." If that's the
case, I'm fine with that. I just
| want to be sure is all.
|
| Thanks,
|
| Matt
|