Re: Tilting at Windmills?
- To: mathgroup at smc.vnet.net
- Subject: [mg62116] Re: Tilting at Windmills?
- From: dh <dh at metrohm.ch>
- Date: Sat, 12 Nov 2005 03:31:13 -0500 (EST)
- References: <dl1jta$1m$1@smc.vnet.net>
- Sender: owner-wri-mathgroup at wolfram.com
Hi Matt,
if your memory needs are not know in advance, there is another soultion
than arrays. You may actually store information as function values.
Instead of
a[[1]]=2
you would write
a[1]=2
here a is now a function. This has the benefit that no memory must be
preallocated and you can use anything you like as an index (like
associative arrays).
You may object that this is more time consuming than simple arrays, but
convince yourself that the difference is astonishing small.
Of course if this is of any use to you depoends a lot of the application.
regards, Daniel
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
>