Re: Tilting at Windmills?
- To: mathgroup at smc.vnet.net
- Subject: [mg62138] Re: [mg62106] Tilting at Windmills?
- From: Bob Hanlon <hanlonr at cox.net>
- Date: Sat, 12 Nov 2005 03:32:28 -0500 (EST)
- Reply-to: hanlonr at cox.net
- Sender: owner-wri-mathgroup at wolfram.com
createListOfListsForCobwebTypePlot[data_]:= Partition[Drop[Drop[Flatten[ Table[#,{4}]&/@data],3],-3],2]; data=ToExpression[Table["x"<>ToString[k],{k,5}]] {x1,x2,x3,x4,x5} createListOfListsForCobwebTypePlot[data] {{x1, x2}, {x2, x2}, {x2, x3}, {x3, x3}, {x3, x4}, {x4, x4}, {x4, x5}} data=Range[200000]; createListOfListsForCobwebTypePlot[data]//Timing//First 0.447221 Second Bob Hanlon > > From: "Matt" <anonmous69 at netscape.net> To: mathgroup at smc.vnet.net > Date: 2005/11/11 Fri AM 02:52:32 EST > Subject: [mg62138] [mg62106] Tilting at Windmills? > > 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,x n} > 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 > >