Services & ResourcesWolfram ForumsMathGroup Archive

[Date Index] [Thread Index] [Author Index]

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>