Tilting at Windmills?
- To: mathgroup at smc.vnet.net
- Subject: [mg62106] Tilting at Windmills?
- From: "Matt" <anonmous69 at netscape.net>
- Date: Fri, 11 Nov 2005 02:52:32 -0500 (EST)
- Sender: owner-wri-mathgroup at wolfram.com
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
- Follow-Ups:
- Re: Tilting at Windmills?
- From: gardyloo <gardyloo@mail.wsu.edu>
- Re: Tilting at Windmills?