[OpenSCAD] Programming in Functional OpenSCAD

Ronaldo Persiano rcmpersiano at gmail.com
Wed Jan 31 05:46:28 EST 2018


Under my initial hyphotesis that copies are made, an insertion or deletion
from a 2-3 tree with N element would be O(N). And to build a tree from
scratch the time would be O(N^2). It is hard to get good time estimates
with the OpenSCAD system but I got worst than linear time building trees by
insertion of 2500-30000 elements.

To minimize stack overflows I have used the tail recursive versions:

function treeinsert(tree,value)=
   (0==len(tree))?
      [value]  :
      (treeinsertiterate(tree,value))[1] ;

function treeinsertlisti(tr,list,i)=
   (i==0)?
      treeinsert(tr,list[0]) :
      treeinsertlisti(treeinsert(tr,list[i]),list,i-1)  ;


BTW, your insertion code does not deal well with some sequences having
repeated values.

ECHO: foo = [40, 57, 65, 14, 65, 80, 82, 65]

ECHO: bar = [[14, 40], 57, [65], 80, [65]]




2018-01-30 21:59 GMT-02:00 NateTG <nate-openscadforum at pedantic.org>:

> > OpenSCAD uses references to reference-counted, immutable values. Multiple
> variables can point to the same immutable list object. There is no need for
> OpenSCAD to make copies of lists, since there are no operations for
> mutating
> a list. AFAIK; I haven't read all the code in the interpreter.
>
> The 2-3 tree implementation should only replace the nodes on the insertion
> or removal path which should individually take a fixed amount of time.  I
> don't understand how it will take O( N^2 ) time and would really like to
> understand.  (Even if OpenSCAD is copying the lists every time, it seems
> like it should be at worst O(N (log N)^2).)
>
>
>
>
>
>
>
>
>
> --
> Sent from: http://forum.openscad.org/
>
> _______________________________________________
> OpenSCAD mailing list
> Discuss at lists.openscad.org
> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://lists.openscad.org/pipermail/discuss_lists.openscad.org/attachments/20180131/8e88d9e6/attachment-0002.html>


More information about the Discuss mailing list