Idea: local var inside list_comprehension

classic Classic list List threaded Threaded
5 messages Options
Reply | Threaded
Open this post in threaded view
|

Idea: local var inside list_comprehension

runsun
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
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Idea: local var inside list_comprehension

nophead
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 <[hidden email]> 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
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
tp3
Reply | Threaded
Open this post in threaded view
|

Re: Idea: local var inside list_comprehension

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


_______________________________________________
OpenSCAD mailing list
[hidden email]
http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
-- Torsten
Reply | Threaded
Open this post in threaded view
|

Re: Idea: local var inside list_comprehension

runsun
In reply to this post by nophead
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
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets
Reply | Threaded
Open this post in threaded view
|

Re: Idea: local var inside list_comprehension

runsun
In reply to this post by tp3
@Torsten, your examples demonstrate tail recursion nicely. Thx a lot. I gotta review all my codes :) :)
$ Runsun Pan, PhD
$ libs: scadx, doctest, faces(git), offline doc(git), runscad.py(2,git), editor of choice: CudaText ( OpenSCAD lexer); $ Tips; $ Snippets