Re: Re: programming competition
- To: mathgroup at smc.vnet.net
- Subject: [mg4915] Re: [mg4866] Re: programming competition
- From: "w.meeussen" <w.meeussen.vdmcc at vandemoortele.be>
- Date: Fri, 4 Oct 1996 00:17:48 -0400
- Sender: owner-wri-mathgroup at wolfram.com
At 22:42 26-09-96 -0400, you wrote:
>Xah wrote:
>>Problem:
>>Suppose you have a ordered list {p1, p2, ... , pn} where points has the form
>>{x,y}. You want to modify the list so any neighboring points will have a
>distance
>>less or equal to a given value maxLength. You do this by adding points in
>between
>>points. For example, suppose p3 and p4 has length greater than maxLength.
>Your new
>>list should then be
>>{p1, p2, p3, newP1, newP2,..., newPm, p4, p5, ... , pn} where
>>newP1, ...newPm lies on the line p3 p4.
>
>This was Xah's list of points:
>
>In[26]:=
> li = Join[ {{0,0},{1,1}}, Table[{i,1}, {i,1,2,1/5}], {{2,1}, {3,3}}];
>
>Xah gave linearInterpolate[] as a solution.
>
(****************** portion deleted ************************)
>
>In[34]:=
> linearInterpolate2[ li, .3]
>Out[34]=
> {{0.2, 0.2}, {0.4, 0.4}, {0.6, 0.6}, {0.8, 0.8}, {0, 0}, {1, 1},
>
> 6 7 8 9
> {1, 1}, {-, 1}, {-, 1}, {-, 1}, {-, 1}, {2, 1}, {2.125, 1.25},
> 5 5 5 5
>
> {2.25, 1.5}, {2.375, 1.75}, {2.5, 2.}, {2.625, 2.25},
>
> {2.75, 2.5}, {2.875, 2.75}, {2, 1}, {3, 3}}
(****************** portion deleted ************************)
>
>This is better, but it still doesn't give the answer in the form Xah
>specified; the new points are not positioned in the list between the points
>they're being interpolated between, i. e. they are not
>{p1, p2, p3, newP1, newP2,..., newPm, p4, p5, ... , pn}.
>
>With Lichtblau's and Hayes' admonitions to use procedural programming
>to solve procedural problems ringing freshly in my ears, I offer the
>following:
>
(****************** portion deleted ************************)
>In[70]:=
> insertPoints[li, .3]
>Out[70]=
> {{0, 0}, {0.212132, 0.212132}, {0.424264, 0.424264},
>
> {0.636396, 0.636396}, {0.848528, 0.848528}, {1., 1.}, {1., 1.},
>
> {1.2, 1.}, {1.4, 1.}, {1.6, 1.}, {1.8, 1.}, {2., 1.}, {2., 1.},
>
> {2.13416, 1.26833}, {2.26833, 1.53666}, {2.40249, 1.80498},
>
> {2.53666, 2.07331}, {2.67082, 2.34164}, {2.80498, 2.60997},
>
> {2.93915, 2.8783}, {3., 3.}}
>
>Xah's description of the problem didn't say anything about having the
>points evenly spaced, so they're not. But it would be simple to modify
>one line of code so they were evenly spaced.
>
>As Lichtblau points out, repeated copying of lists makes the problem
>O(n^2).
>
>In[137]:=
> pointsList1 = Table[{Random[], Random[]}, {100}];
> pointsList2 = Table[{Random[], Random[]}, {1000}];
>
>In[139]:=
> linearInterpolate2[ pointsList1, .3]; // Timing
> linearInterpolate2[ pointsList2, .3]; // Timing
>Out[139]=
> {3.8 Second, Null}
>Out[140]=
> {15.75 Second, Null}
>
>Avoiding copying of lists keeps the problem to O(n)
>
>In[143]:=
> insertPoints[pointsList1, .3]; // Timing
> insertPoints[pointsList2, .3]; // Timing
>Out[143]=
> {2.4 Second, Null}
>Out[144]=
> {4.25 Second, Null}
>
>I periodically need to do fairly complicated operations on
>small lists. Using the list manipulation functions may make the
>problem O(n^2), but for small lists this doesn't really matter.
>Using Append[], Rest[], and similar functions simplifies the
>code and makes it easier to develop and debug, compared to
>using a procedural approach and trying to write the fastest
>code possible. In Xah's and Richard Gaylord's (actually, Don
>Piele's) problems it was easier to develop a solution using
>a procedural approach, but it is often easier to use an approach
>that results in slower code. What I ask from Mathematica is that
>the code be as clear and self-documenting as possible, the
>development process be as short and painless as possible, and
>the result be correct. If speed were that important to me
>I'd be writing in a compiled language. The problem with many
>blocks of code is not that they're slow, but that
>they're confusing. This makes it more difficult to debug
>and be sure of getting a correct result. Overall, I think
>top-down design and attention to formatting are more important
>that speed. Because of it's clarity, I liked Paul Abbott's pattern
>matching approach to the Gaylord-Piele problem. It worked fine
>on short lists and you could tell at a glance what the code was
>doing.
>
>--
>Bob Hall | "Know thyself? Absurd direction!
>rhall2 at gl.umbc.edu | Bubbles bear no introspection." -Khushhal Khan Khatak
>
>
>
>
Bob,
it seems to be a kind of problem suitable to a rule-based attack :
for a simplified one-dimensional case :
test=Table[n+Random[Real,{1,10}],{n,0,1000,10}]
a rule "rule1" is defined that shows the inserted numbers as lists :
rule1={a___,b_/;NumberQ[b],c_/;NumberQ[c],d___}/;Abs[b-c]>dif:>
{a,Range[b,c-dif,dif],c,d}
Timing[test//.rule1]
{2.242 Second, {{6.00759, 9.00759, 12.0076}, {15.7191},
... etc ...
{963.993, 966.993}, {972.051, 975.051, 978.051}, {982.462, 985.462, 988.462},
{993.766, 996.766, 999.766, 1002.77, 1005.77}, 1009.67}}
a simple Flatten[] gets rid of the extra list-envelopments.
So far, still lean & mean, don't you think?
Now, in two dimensions, why not use complex numbers, and keep the same
strategy ?
testc=Table[{n+Random[Real,{1,10}],n+Random[Real,{1,10}]},{n,0,1000,10}]
rule2={a___, b_/;NumberQ[b], c_/;NumberQ[c], d___} /; Abs[b-c]>dif :>
{a, Range[b,c-(c-b) dif/Abs[c-b], (c-b) dif/Abs[c-b]], c, d}
we only need to switch between {x,y} and x+Iy and back :
Timing[{Re[#],Im[#]}&/@Flatten[Apply[(#1+I #2) &, testc,1]//.rule2]]
gives:
{5.013 Second, {{6.67336, 4.32093}, {8.47046, 6.72311}, {10.2675, 9.12529},
... etc ...
{917.71, 920.338}, {921.006, 924.902}, {923.581, 926.442}, {926.156,
927.982}, {928.73, 929.522},
{931.97, 931.459}, {933.657, 933.94}, {935.344, 936.421}, {937.031,
938.901}, {938.718, 941.382},
{940.406, 943.863}, {943.143, 947.888}, {945.831, 949.221}, {948.518,
950.554}, {951.281, 951.925},
{953.626, 953.796}, {955.972, 955.667}, {958.317, 957.537}, {960.662,
959.408}, {963.008, 961.279},
{965.353, 963.149}, {968.588, 965.73}, {969.662, 968.532}, {970.735,
971.333}, {971.808, 974.135},
{973.642, 978.922}, {976.562, 979.608}, {979.483, 980.293}, {982.403,
980.979}, {985.324, 981.665},
{989.648, 982.68}, {990.212, 985.627}, {990.775, 988.574}, {991.339,
991.52}, {991.902, 994.467},
{992.545, 997.828}, {995.042, 999.49}, {997.54, 1001.15}, {1000.04,
1002.81}, {1002.92, 1004.73}}}
I admit that it took me some time to get the Range[...] arguments right
(needs rule delayed ":>", not ReplaceAll "->" to avoid unpleasant and
unhelpful red remarks about the arguments not being Integers (silly, they
need't be Integers at all). Also, I fell into the infinite regression twice
(because of //. ).
All in all, the ReplaceRepeated just scans over the list once, because the
replacement generates no numbers, but lists.
Final remark :
it would be more elegant if a condition like
b_Number
were allowed, in stead of
b_/;NumberQ[b]
I lost quite some time on that.
Wouter.
==== [MESSAGE SEPARATOR] ====