Idea: local var inside list_comprehension
I've carried out some speed tests to compare the performance of list
comprehension and recursion. The preliminary result shows that list comp. is
much much faster than recursion. The difference is huge especially at large
data set. In some cases recursion hangs the computer but list comp can
finish in 1~2 sec.
But there are cases that recursion is needed. A simple sum( list ) function
will require recursion, because we can't carry the result of
list[i]+list[i+1] to the next iteration.
So I have an idea: how about an internal variable to represent the result of
the previous iteration ?
Let's say, @ = result of the previous iteration
function sum( list ) = [ for( i=[0:len(list)-1] ) i==0?list[i]:(@+list[i]) ]
[ len(list)-1] ;
sum( [2,3,4] ) = [ 2,5,9][2] = 9;
$ Runsun Pan, PhD
$ -- OpenScad_DocTest: doc and unit test ( Github , Thingiverse )
$ -- hash parameter model: here , here
$ -- Linux Mint 17.1 Rebecca x64 + OpenSCAD 2015.03.15/2015.04.01.nightly
--
View this message in context: http://forum.openscad.org/Idea-local-var-inside-list-comprehension-tp12446.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
Better to optimise tail recursion to be iteration than make the language
more complicated and ugly. I thought that had already been done though?
On 20 April 2015 at 20:39, runsun runsun@gmail.com wrote:
I've carried out some speed tests to compare the performance of list
comprehension and recursion. The preliminary result shows that list comp.
is
much much faster than recursion. The difference is huge especially at
large
data set. In some cases recursion hangs the computer but list comp can
finish in 1~2 sec.
But there are cases that recursion is needed. A simple sum( list ) function
will require recursion, because we can't carry the result of
list[i]+list[i+1] to the next iteration.
So I have an idea: how about an internal variable to represent the result
of
the previous iteration ?
Let's say, @ = result of the previous iteration
function sum( list ) = [ for( i=[0:len(list)-1] ) i==0?list[i]:(@+list[i])
]
[ len(list)-1] ;
sum( [2,3,4] ) = [ 2,5,9][2] = 9;
$ Runsun Pan, PhD
$ -- OpenScad_DocTest: doc and unit test ( Github , Thingiverse )
$ -- hash parameter model: here , here
$ -- Linux Mint 17.1 Rebecca x64 + OpenSCAD 2015.03.15/2015.04.01.nightly
--
View this message in context:
http://forum.openscad.org/Idea-local-var-inside-list-comprehension-tp12446.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
OpenSCAD mailing list
Discuss@lists.openscad.org
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
On 04/20/2015 10:17 PM, nop head wrote:
Better to optimise tail recursion to be iteration than make the
language more complicated and ugly. I thought that had already
been done though?
Simple tail recursion elimination is supported (functions only,
not for modules):
function rec_add(i = 0) = i <= 0 ? 0 : i + rec_add(i - 1);
echo(rec_add(10000));
=> ERROR: Recursion detected calling function 'rec_add'
function tail_rec_add(i = 0, result = 0) = i <= 0 ? result : tail_rec_add(i - 1, result + i);
echo(tail_rec_add(10000));
=> ECHO: 5.0005e+07
Note that there is currently still a limit for the iteration
count, but it's much higher than the limit caused by stack
size for the recursive call.
ciao,
Torsten.
You are right !!! Tail recursion is very fast, indeed. I adjusted my code and
it's much faster. It's still 3x slower than the list comprehension at very
large data set, but is very impressive already. Good enough. Thx, man.
$ Runsun Pan, PhD
$ -- OpenScad_DocTest: doc and unit test ( Github , Thingiverse )
$ -- hash parameter model: here , here
$ -- Linux Mint 17.1 Rebecca x64 + OpenSCAD 2015.03.15/2015.04.01.nightly
--
View this message in context: http://forum.openscad.org/Idea-local-var-inside-list-comprehension-tp12446p12449.html
Sent from the OpenSCAD mailing list archive at Nabble.com.
@Torsten, your examples demonstrate tail recursion nicely. Thx a lot. I gotta
review all my codes :) :)
$ Runsun Pan, PhD
$ -- OpenScad_DocTest: doc and unit test ( Github , Thingiverse )
$ -- hash parameter model: here , here
$ -- Linux Mint 17.1 Rebecca x64 + OpenSCAD 2015.03.15/2015.04.01.nightly
--
View this message in context: http://forum.openscad.org/Idea-local-var-inside-list-comprehension-tp12446p12450.html
Sent from the OpenSCAD mailing list archive at Nabble.com.