MathGroup Archive 2005

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

Search the Archive

Re: Tilting at Windmills?

  • To: mathgroup at smc.vnet.net
  • Subject: [mg62148] Re: [mg62106] Tilting at Windmills?
  • From: gardyloo <gardyloo at mail.wsu.edu>
  • Date: Sat, 12 Nov 2005 03:32:56 -0500 (EST)
  • References: <200511110752.CAA29692@smc.vnet.net>
  • Sender: owner-wri-mathgroup at wolfram.com

  Hi, Matt,

    I didn't look to see what large testLists you were working with, or
I'd never have attempted what I'll post here. But my timings aren't too
bad, for a really naive approach. I don't know how the memory usage
compares to yours, but the last line shows a memory usage of just under
3MB (I think).

Hope this helps!

          Curtis


In[1]:=

parseList[list_?ListQ]:={{list[[#]], list[[#]]}, {list[[#]], list[[#+1]]}}&/@

    Range[Length[list]-1]

In[2]:=

parseList[{a,b,c,d,e,f,g}]

Out[2]=

{{{a,a},{a,b}},{{b,b},{b,c}},{{c,c},{c,d}},{{d,d},{d,e}},{{e,e},{e,f}},{{f,

      f},{f,g}}}

In[3]:=

testList=Range[200000];

In[4]:=

Timing[parseList[testList];]

Out[4]=

{0.232964` Second,Null}

In[5]:=

Take[parseList[testList], 10]

Out[5]=

{{{1,1},{1,2}},{{2,2},{2,3}},{{3,3},{3,4}},{{4,4},{4,5}},{{5,5},{5,6}},{{6,

      6},{6,7}},{{7,7},{7,8}},{{8,8},{8,9}},{{9,9},{9,10}},{{10,10},{10,11}}}

In[6]:=

$Version

Out[6]=

"5.2 for Linux (June 20, 2005)"

In[7]:=
MemoryInUse[]

Out[7]=
2941472



Matt wrote:

>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
>
>
>  
>


  • Prev by Date: Re: Tilting at Windmills?
  • Next by Date: Re: Mathematica 1
  • Previous by thread: Tilting at Windmills?
  • Next by thread: Re: Tilting at Windmills?