I am stuck. I got an implementation of quicksort as an example of list comprehension in the manual: > function quicksort(arr) = > !(len(arr)>0) ? [] : > let( pivot = arr[floor(len(arr)/2)], > lesser = [ for (y = arr) if (y < pivot) y ], > equal = [ for (y = arr) if (y == pivot) y ], > greater = [ for (y = arr) if (y > pivot) y ] > ) > concat( quicksort(lesser), equal, quicksort(greater) ); It works well for very large random arrays and, in the worst case, for arrays with length at least 3000 without stack overflow. Usually the partitions of quicksort are in two subarrays. So I tweaked the code to get: > function quicksort1(arr) = > !(len(arr)>0) ? [] : > let( pivot = arr[floor(len(arr)/2)], > lesser = [ for (y = arr) if (y <= pivot) y ], > greater = [ for (y = arr) if (y > pivot) y ] > ) > concat( quicksort1(lesser), quicksort1(greater) ); where the partition "equal" is included in the partition "lesser". The trouble is that this last version is not working: I get a stack overflow for any non void array. And I don't see why. -- View this message in context: http://forum.openscad.org/Quicksort-tp17044.html Sent from the OpenSCAD mailing list archive at Nabble.com.

In the first implementation there is always at least one element that gets taken away from the sorting (the pivot), so that you will always finish. In quicksort1 when the array has just 1 element it gets always selected as pivot, always included in lesser and you get infinite recursion. > I am stuck. I got an implementation of quicksort as an example of > list > comprehension in the manual: > > > function quicksort(arr) = > > !(len(arr)>0) ? [] : > > let( pivot = arr[floor(len(arr)/2)], > > lesser = [ for (y = arr) if (y < pivot) y ], > > equal = [ for (y = arr) if (y == pivot) y ], > > greater = [ for (y = arr) if (y > pivot) y ] > > ) > > concat( quicksort(lesser), equal, quicksort(greater) ); > > It works well for very large random arrays and, in the worst case, for > arrays with length at least 3000 without stack overflow. > Usually the partitions of quicksort are in two subarrays. So I > tweaked the code to get: > > > function quicksort1(arr) = > > !(len(arr)>0) ? [] : > > let( pivot = arr[floor(len(arr)/2)], > > lesser = [ for (y = arr) if (y <= pivot) y ], > > greater = [ for (y = arr) if (y > pivot) y ] > > ) > > concat( quicksort1(lesser), quicksort1(greater) ); > > where the partition "equal" is included in the partition "lesser". > The trouble is that this last version is not working: I get a stack > overflow for any non void array. And I don't see why. > > > > -- > View this message in context: > http://forum.openscad.org/Quicksort-tp17044.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

Bingo! Why I didn't see that? Well, I think I hadn't fully grasped quicksort algorithm. :( Meanwhile, I got a version of quicksort which seems to have the pattern of tail recursion: > function qs(arr, arr_out=[]) = > !(len(arr)>0) ? > arr_out : > qs( arr = high_part(arr), > arr_out = concat(qs( low_part(arr), arr_out ), > middle_part(arr)) ); > > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y ]; > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y ]; > function pivot (arr) = arr[floor(len(arr)/2)]; I were able to sort a worst case array of length 5000 in 48sec with qs(). The previous quicksort() function fail with stack overflow for lengths lesser than 4000. However, it is much slower: for a random array with 40000 values, qs() required 60 sec while quicksort() spent just 4sec. -- View this message in context: http://forum.openscad.org/Quicksort-tp17044p17051.html Sent from the OpenSCAD mailing list archive at Nabble.com.

Interesting. With 40000 random numbers I also get 4s with quicksort but qs takes 3 minutes 37 seconds for me. I translated it into Python to try to see what the difference is, OpenScad desperately needs echo() in functions! import random import time def pivot(arr): return arr[int(len(arr)/2)] def high_part(arr): p = pivot(arr) return [y for y in arr if y > p] def middle_part(arr): p = pivot(arr) return [y for y in arr if y == p] def low_part(arr): p = pivot(arr) return [y for y in arr if y < p] def qs(arr, arr_out=[], n = 0): #print n, arr return arr_out if len(arr) == 0 else qs(high_part(arr), qs(low_part(arr), arr_out, 2) + middle_part(arr), 1) def quicksort(arr, n = 0): #print n, arr if len(arr) == 0: return [] pivot = arr[int(len(arr)/2)] lesser = [y for y in arr if y < pivot] equal = [y for y in arr if y == pivot] greater = [y for y in arr if y > pivot] return quicksort(lesser, 2) + equal + quicksort(greater, 1) list = [random.random() for x in xrange(40000)] t0 = time.time() qs(list) t1 = time.time() quicksort(list) t2 = time.time() print "qs:", round(t1 - t0, 3), "quicksort:", round(t2 - t1, 3) There is also a big difference in timings: qs: 5.632 quicksort: 0.256 I hoisted the pivot calculations out of the loops and I did the same in the openscad version with let but it made no difference. If I add the commented out print statements and use a small array of integers it prints exactly the same calls and intermediate results, so I can't explain the big time difference. Perhaps there are more list copies due to passing arr_out forward. On 12 April 2016 at 03:02, Ronaldo <rcmpersiano@gmail.com> wrote: > Bingo! Why I didn't see that? Well, I think I hadn't fully grasped > quicksort > algorithm. :( > > Meanwhile, I got a version of quicksort which seems to have the pattern of > tail recursion: > > > function qs(arr, arr_out=[]) = > > !(len(arr)>0) ? > > arr_out : > > qs( arr = high_part(arr), > > arr_out = concat(qs( low_part(arr), arr_out ), > > middle_part(arr)) ); > > > > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y ]; > > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; > > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y ]; > > function pivot (arr) = arr[floor(len(arr)/2)]; > > I were able to sort a worst case array of length 5000 in 48sec with qs(). > The previous quicksort() function fail with stack overflow for lengths > lesser than 4000. However, it is much slower: for a random array with 40000 > values, qs() required 60 sec while quicksort() spent just 4sec. > > > > -- > View this message in context: > http://forum.openscad.org/Quicksort-tp17044p17051.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 >

Since middle_part is generally one number it seems that arr_out just increases by one entry at a time, which is not very efficient for long lists. I think quicksort wins because it is joining up bigger chunks. On 12 April 2016 at 11:39, nop head <nop.head@gmail.com> wrote: > Interesting. > > With 40000 random numbers I also get 4s with quicksort but qs takes 3 > minutes 37 seconds for me. > > I translated it into Python to try to see what the difference is, OpenScad > desperately needs echo() in functions! > > import random > import time > > def pivot(arr): > return arr[int(len(arr)/2)] > > def high_part(arr): > p = pivot(arr) > return [y for y in arr if y > p] > > def middle_part(arr): > p = pivot(arr) > return [y for y in arr if y == p] > > def low_part(arr): > p = pivot(arr) > return [y for y in arr if y < p] > > def qs(arr, arr_out=[], n = 0): > #print n, arr > return arr_out if len(arr) == 0 else qs(high_part(arr), > qs(low_part(arr), arr_out, 2) + middle_part(arr), 1) > > def quicksort(arr, n = 0): > #print n, arr > if len(arr) == 0: return [] > pivot = arr[int(len(arr)/2)] > lesser = [y for y in arr if y < pivot] > equal = [y for y in arr if y == pivot] > greater = [y for y in arr if y > pivot] > return quicksort(lesser, 2) + equal + quicksort(greater, 1) > > list = [random.random() for x in xrange(40000)] > > t0 = time.time() > qs(list) > t1 = time.time() > quicksort(list) > t2 = time.time() > > print "qs:", round(t1 - t0, 3), "quicksort:", round(t2 - t1, 3) > > There is also a big difference in timings: qs: 5.632 quicksort: 0.256 > > I hoisted the pivot calculations out of the loops and I did the same in > the openscad version with let but it made no difference. > > If I add the commented out print statements and use a small array of > integers it prints exactly the same calls and intermediate results, so I > can't explain the big time difference. Perhaps there are more list copies > due to passing arr_out forward. > > > On 12 April 2016 at 03:02, Ronaldo <rcmpersiano@gmail.com> wrote: > >> Bingo! Why I didn't see that? Well, I think I hadn't fully grasped >> quicksort >> algorithm. :( >> >> Meanwhile, I got a version of quicksort which seems to have the pattern of >> tail recursion: >> >> > function qs(arr, arr_out=[]) = >> > !(len(arr)>0) ? >> > arr_out : >> > qs( arr = high_part(arr), >> > arr_out = concat(qs( low_part(arr), arr_out ), >> > middle_part(arr)) ); >> > >> > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y ]; >> > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; >> > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y ]; >> > function pivot (arr) = arr[floor(len(arr)/2)]; >> >> I were able to sort a worst case array of length 5000 in 48sec with qs(). >> The previous quicksort() function fail with stack overflow for lengths >> lesser than 4000. However, it is much slower: for a random array with >> 40000 >> values, qs() required 60 sec while quicksort() spent just 4sec. >> >> >> >> -- >> View this message in context: >> http://forum.openscad.org/Quicksort-tp17044p17051.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 >> > >

In nophead's benchmark, Python is 15.6 times faster for quicksort, and 38.5 times faster for qs. I attribute this to the fact that Python compiles to bytecode. We should be able to get a 10x speedup pretty easily with a bytecode compiler, even before doing much performance tuning. Note that Python is slow compared to Javascript, which has insane amounts of performance optimization. On 12 April 2016 at 06:39, nop head <nop.head@gmail.com> wrote: > Interesting. > > With 40000 random numbers I also get 4s with quicksort but qs takes 3 > minutes 37 seconds for me. > > I translated it into Python to try to see what the difference is, OpenScad > desperately needs echo() in functions! > > import random > import time > > def pivot(arr): > return arr[int(len(arr)/2)] > > def high_part(arr): > p = pivot(arr) > return [y for y in arr if y > p] > > def middle_part(arr): > p = pivot(arr) > return [y for y in arr if y == p] > > def low_part(arr): > p = pivot(arr) > return [y for y in arr if y < p] > > def qs(arr, arr_out=[], n = 0): > #print n, arr > return arr_out if len(arr) == 0 else qs(high_part(arr), > qs(low_part(arr), arr_out, 2) + middle_part(arr), 1) > > def quicksort(arr, n = 0): > #print n, arr > if len(arr) == 0: return [] > pivot = arr[int(len(arr)/2)] > lesser = [y for y in arr if y < pivot] > equal = [y for y in arr if y == pivot] > greater = [y for y in arr if y > pivot] > return quicksort(lesser, 2) + equal + quicksort(greater, 1) > > list = [random.random() for x in xrange(40000)] > > t0 = time.time() > qs(list) > t1 = time.time() > quicksort(list) > t2 = time.time() > > print "qs:", round(t1 - t0, 3), "quicksort:", round(t2 - t1, 3) > > There is also a big difference in timings: qs: 5.632 quicksort: 0.256 > > I hoisted the pivot calculations out of the loops and I did the same in > the openscad version with let but it made no difference. > > If I add the commented out print statements and use a small array of > integers it prints exactly the same calls and intermediate results, so I > can't explain the big time difference. Perhaps there are more list copies > due to passing arr_out forward. > > > On 12 April 2016 at 03:02, Ronaldo <rcmpersiano@gmail.com> wrote: > >> Bingo! Why I didn't see that? Well, I think I hadn't fully grasped >> quicksort >> algorithm. :( >> >> Meanwhile, I got a version of quicksort which seems to have the pattern of >> tail recursion: >> >> > function qs(arr, arr_out=[]) = >> > !(len(arr)>0) ? >> > arr_out : >> > qs( arr = high_part(arr), >> > arr_out = concat(qs( low_part(arr), arr_out ), >> > middle_part(arr)) ); >> > >> > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y ]; >> > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; >> > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y ]; >> > function pivot (arr) = arr[floor(len(arr)/2)]; >> >> I were able to sort a worst case array of length 5000 in 48sec with qs(). >> The previous quicksort() function fail with stack overflow for lengths >> lesser than 4000. However, it is much slower: for a random array with >> 40000 >> values, qs() required 60 sec while quicksort() spent just 4sec. >> >> >> >> -- >> View this message in context: >> http://forum.openscad.org/Quicksort-tp17044p17051.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 >> > > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >

Yes but is it worth it as most of time the geometry generation is many orders of magnitude slower? Why would one want to qsort 40000 numbers in an OpenScad script anyway? On 12 April 2016 at 13:36, doug moen <doug@moens.org> wrote: > In nophead's benchmark, > Python is 15.6 times faster for quicksort, > and 38.5 times faster for qs. > > I attribute this to the fact that Python compiles to bytecode. We should > be able to get a 10x speedup pretty easily with a bytecode compiler, even > before doing much performance tuning. Note that Python is slow compared to > Javascript, which has insane amounts of performance optimization. > > On 12 April 2016 at 06:39, nop head <nop.head@gmail.com> wrote: > >> Interesting. >> >> With 40000 random numbers I also get 4s with quicksort but qs takes 3 >> minutes 37 seconds for me. >> >> I translated it into Python to try to see what the difference is, >> OpenScad desperately needs echo() in functions! >> >> import random >> import time >> >> def pivot(arr): >> return arr[int(len(arr)/2)] >> >> def high_part(arr): >> p = pivot(arr) >> return [y for y in arr if y > p] >> >> def middle_part(arr): >> p = pivot(arr) >> return [y for y in arr if y == p] >> >> def low_part(arr): >> p = pivot(arr) >> return [y for y in arr if y < p] >> >> def qs(arr, arr_out=[], n = 0): >> #print n, arr >> return arr_out if len(arr) == 0 else qs(high_part(arr), >> qs(low_part(arr), arr_out, 2) + middle_part(arr), 1) >> >> def quicksort(arr, n = 0): >> #print n, arr >> if len(arr) == 0: return [] >> pivot = arr[int(len(arr)/2)] >> lesser = [y for y in arr if y < pivot] >> equal = [y for y in arr if y == pivot] >> greater = [y for y in arr if y > pivot] >> return quicksort(lesser, 2) + equal + quicksort(greater, 1) >> >> list = [random.random() for x in xrange(40000)] >> >> t0 = time.time() >> qs(list) >> t1 = time.time() >> quicksort(list) >> t2 = time.time() >> >> print "qs:", round(t1 - t0, 3), "quicksort:", round(t2 - t1, 3) >> >> There is also a big difference in timings: qs: 5.632 quicksort: 0.256 >> >> I hoisted the pivot calculations out of the loops and I did the same in >> the openscad version with let but it made no difference. >> >> If I add the commented out print statements and use a small array of >> integers it prints exactly the same calls and intermediate results, so I >> can't explain the big time difference. Perhaps there are more list copies >> due to passing arr_out forward. >> >> >> On 12 April 2016 at 03:02, Ronaldo <rcmpersiano@gmail.com> wrote: >> >>> Bingo! Why I didn't see that? Well, I think I hadn't fully grasped >>> quicksort >>> algorithm. :( >>> >>> Meanwhile, I got a version of quicksort which seems to have the pattern >>> of >>> tail recursion: >>> >>> > function qs(arr, arr_out=[]) = >>> > !(len(arr)>0) ? >>> > arr_out : >>> > qs( arr = high_part(arr), >>> > arr_out = concat(qs( low_part(arr), arr_out ), >>> > middle_part(arr)) ); >>> > >>> > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y ]; >>> > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; >>> > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y ]; >>> > function pivot (arr) = arr[floor(len(arr)/2)]; >>> >>> I were able to sort a worst case array of length 5000 in 48sec with qs(). >>> The previous quicksort() function fail with stack overflow for lengths >>> lesser than 4000. However, it is much slower: for a random array with >>> 40000 >>> values, qs() required 60 sec while quicksort() spent just 4sec. >>> >>> >>> >>> -- >>> View this message in context: >>> http://forum.openscad.org/Quicksort-tp17044p17051.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 >>> >> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >

I dunno, why would anyone want to triangulate a polygon? I've been thinking about performance issues while reading that thread. I agree that triangulating a polygon is not the sort of task that OpenSCAD was designed for. I think that some of this is driven by the fact that OpenSCAD provides a limited set of primitive shapes, and if you want to go beyond that, you need to use polyhedron(). And if you really push the limits of what can be expressed with polyhedron(), then you can get into requiring these complex calculations. I'd like to provide an easier way than polyhedron() for constructing complex mathematically defined shapes. I think Functional Representation would be a great thing to support. Of course, that opens up an even bigger can of worms than simply speeding up the interpreter using a byte code compiler. On 12 April 2016 at 09:06, nop head <nop.head@gmail.com> wrote: > Yes but is it worth it as most of time the geometry generation is many > orders of magnitude slower? Why would one want to qsort 40000 numbers in an > OpenScad script anyway? > > On 12 April 2016 at 13:36, doug moen <doug@moens.org> wrote: > >> In nophead's benchmark, >> Python is 15.6 times faster for quicksort, >> and 38.5 times faster for qs. >> >> I attribute this to the fact that Python compiles to bytecode. We should >> be able to get a 10x speedup pretty easily with a bytecode compiler, even >> before doing much performance tuning. Note that Python is slow compared to >> Javascript, which has insane amounts of performance optimization. >> >> On 12 April 2016 at 06:39, nop head <nop.head@gmail.com> wrote: >> >>> Interesting. >>> >>> With 40000 random numbers I also get 4s with quicksort but qs takes 3 >>> minutes 37 seconds for me. >>> >>> I translated it into Python to try to see what the difference is, >>> OpenScad desperately needs echo() in functions! >>> >>> import random >>> import time >>> >>> def pivot(arr): >>> return arr[int(len(arr)/2)] >>> >>> def high_part(arr): >>> p = pivot(arr) >>> return [y for y in arr if y > p] >>> >>> def middle_part(arr): >>> p = pivot(arr) >>> return [y for y in arr if y == p] >>> >>> def low_part(arr): >>> p = pivot(arr) >>> return [y for y in arr if y < p] >>> >>> def qs(arr, arr_out=[], n = 0): >>> #print n, arr >>> return arr_out if len(arr) == 0 else qs(high_part(arr), >>> qs(low_part(arr), arr_out, 2) + middle_part(arr), 1) >>> >>> def quicksort(arr, n = 0): >>> #print n, arr >>> if len(arr) == 0: return [] >>> pivot = arr[int(len(arr)/2)] >>> lesser = [y for y in arr if y < pivot] >>> equal = [y for y in arr if y == pivot] >>> greater = [y for y in arr if y > pivot] >>> return quicksort(lesser, 2) + equal + quicksort(greater, 1) >>> >>> list = [random.random() for x in xrange(40000)] >>> >>> t0 = time.time() >>> qs(list) >>> t1 = time.time() >>> quicksort(list) >>> t2 = time.time() >>> >>> print "qs:", round(t1 - t0, 3), "quicksort:", round(t2 - t1, 3) >>> >>> There is also a big difference in timings: qs: 5.632 quicksort: 0.256 >>> >>> I hoisted the pivot calculations out of the loops and I did the same in >>> the openscad version with let but it made no difference. >>> >>> If I add the commented out print statements and use a small array of >>> integers it prints exactly the same calls and intermediate results, so I >>> can't explain the big time difference. Perhaps there are more list copies >>> due to passing arr_out forward. >>> >>> >>> On 12 April 2016 at 03:02, Ronaldo <rcmpersiano@gmail.com> wrote: >>> >>>> Bingo! Why I didn't see that? Well, I think I hadn't fully grasped >>>> quicksort >>>> algorithm. :( >>>> >>>> Meanwhile, I got a version of quicksort which seems to have the pattern >>>> of >>>> tail recursion: >>>> >>>> > function qs(arr, arr_out=[]) = >>>> > !(len(arr)>0) ? >>>> > arr_out : >>>> > qs( arr = high_part(arr), >>>> > arr_out = concat(qs( low_part(arr), arr_out ), >>>> > middle_part(arr)) ); >>>> > >>>> > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y ]; >>>> > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; >>>> > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y ]; >>>> > function pivot (arr) = arr[floor(len(arr)/2)]; >>>> >>>> I were able to sort a worst case array of length 5000 in 48sec with >>>> qs(). >>>> The previous quicksort() function fail with stack overflow for lengths >>>> lesser than 4000. However, it is much slower: for a random array with >>>> 40000 >>>> values, qs() required 60 sec while quicksort() spent just 4sec. >>>> >>>> >>>> >>>> -- >>>> View this message in context: >>>> http://forum.openscad.org/Quicksort-tp17044p17051.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 >>>> >>> >>> >>> _______________________________________________ >>> OpenSCAD mailing list >>> Discuss@lists.openscad.org >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>> >>> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >

But polyhedron triangulates facets for you. Any why would you need 40000 vertices in a facet? On 12 April 2016 at 14:20, doug moen <doug@moens.org> wrote: > I dunno, why would anyone want to triangulate a polygon? I've been > thinking about performance issues while reading that thread. I agree that > triangulating a polygon is not the sort of task that OpenSCAD was designed > for. > > I think that some of this is driven by the fact that OpenSCAD provides a > limited set of primitive shapes, and if you want to go beyond that, you > need to use polyhedron(). And if you really push the limits of what can be > expressed with polyhedron(), then you can get into requiring these complex > calculations. > > I'd like to provide an easier way than polyhedron() for constructing > complex mathematically defined shapes. I think Functional Representation > would be a great thing to support. Of course, that opens up an even bigger > can of worms than simply speeding up the interpreter using a byte code > compiler. > > On 12 April 2016 at 09:06, nop head <nop.head@gmail.com> wrote: > >> Yes but is it worth it as most of time the geometry generation is many >> orders of magnitude slower? Why would one want to qsort 40000 numbers in an >> OpenScad script anyway? >> >> On 12 April 2016 at 13:36, doug moen <doug@moens.org> wrote: >> >>> In nophead's benchmark, >>> Python is 15.6 times faster for quicksort, >>> and 38.5 times faster for qs. >>> >>> I attribute this to the fact that Python compiles to bytecode. We should >>> be able to get a 10x speedup pretty easily with a bytecode compiler, even >>> before doing much performance tuning. Note that Python is slow compared to >>> Javascript, which has insane amounts of performance optimization. >>> >>> On 12 April 2016 at 06:39, nop head <nop.head@gmail.com> wrote: >>> >>>> Interesting. >>>> >>>> With 40000 random numbers I also get 4s with quicksort but qs takes 3 >>>> minutes 37 seconds for me. >>>> >>>> I translated it into Python to try to see what the difference is, >>>> OpenScad desperately needs echo() in functions! >>>> >>>> import random >>>> import time >>>> >>>> def pivot(arr): >>>> return arr[int(len(arr)/2)] >>>> >>>> def high_part(arr): >>>> p = pivot(arr) >>>> return [y for y in arr if y > p] >>>> >>>> def middle_part(arr): >>>> p = pivot(arr) >>>> return [y for y in arr if y == p] >>>> >>>> def low_part(arr): >>>> p = pivot(arr) >>>> return [y for y in arr if y < p] >>>> >>>> def qs(arr, arr_out=[], n = 0): >>>> #print n, arr >>>> return arr_out if len(arr) == 0 else qs(high_part(arr), >>>> qs(low_part(arr), arr_out, 2) + middle_part(arr), 1) >>>> >>>> def quicksort(arr, n = 0): >>>> #print n, arr >>>> if len(arr) == 0: return [] >>>> pivot = arr[int(len(arr)/2)] >>>> lesser = [y for y in arr if y < pivot] >>>> equal = [y for y in arr if y == pivot] >>>> greater = [y for y in arr if y > pivot] >>>> return quicksort(lesser, 2) + equal + quicksort(greater, 1) >>>> >>>> list = [random.random() for x in xrange(40000)] >>>> >>>> t0 = time.time() >>>> qs(list) >>>> t1 = time.time() >>>> quicksort(list) >>>> t2 = time.time() >>>> >>>> print "qs:", round(t1 - t0, 3), "quicksort:", round(t2 - t1, 3) >>>> >>>> There is also a big difference in timings: qs: 5.632 quicksort: 0.256 >>>> >>>> I hoisted the pivot calculations out of the loops and I did the same in >>>> the openscad version with let but it made no difference. >>>> >>>> If I add the commented out print statements and use a small array of >>>> integers it prints exactly the same calls and intermediate results, so I >>>> can't explain the big time difference. Perhaps there are more list copies >>>> due to passing arr_out forward. >>>> >>>> >>>> On 12 April 2016 at 03:02, Ronaldo <rcmpersiano@gmail.com> wrote: >>>> >>>>> Bingo! Why I didn't see that? Well, I think I hadn't fully grasped >>>>> quicksort >>>>> algorithm. :( >>>>> >>>>> Meanwhile, I got a version of quicksort which seems to have the >>>>> pattern of >>>>> tail recursion: >>>>> >>>>> > function qs(arr, arr_out=[]) = >>>>> > !(len(arr)>0) ? >>>>> > arr_out : >>>>> > qs( arr = high_part(arr), >>>>> > arr_out = concat(qs( low_part(arr), arr_out ), >>>>> > middle_part(arr)) ); >>>>> > >>>>> > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y ]; >>>>> > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y ]; >>>>> > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y ]; >>>>> > function pivot (arr) = arr[floor(len(arr)/2)]; >>>>> >>>>> I were able to sort a worst case array of length 5000 in 48sec with >>>>> qs(). >>>>> The previous quicksort() function fail with stack overflow for lengths >>>>> lesser than 4000. However, it is much slower: for a random array with >>>>> 40000 >>>>> values, qs() required 60 sec while quicksort() spent just 4sec. >>>>> >>>>> >>>>> >>>>> -- >>>>> View this message in context: >>>>> http://forum.openscad.org/Quicksort-tp17044p17051.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 >>>>> >>>> >>>> >>>> _______________________________________________ >>>> OpenSCAD mailing list >>>> Discuss@lists.openscad.org >>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>>> >>>> >>> >>> _______________________________________________ >>> OpenSCAD mailing list >>> Discuss@lists.openscad.org >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>> >>> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >

Only Ronaldo can explain why one would need quicksort and polygon triangulation in OpenSCAD. He started both of those threads. Maybe he will explain. You might need 40,000 vertices in a polygon as an end cap for a tube, either a really accurate circle, or some other shape. Fractal geometry is another general reason for needing lots of vertices. On 12 April 2016 at 10:07, nop head <nop.head@gmail.com> wrote: > But polyhedron triangulates facets for you. Any why would you need 40000 > vertices in a facet? > > > On 12 April 2016 at 14:20, doug moen <doug@moens.org> wrote: > >> I dunno, why would anyone want to triangulate a polygon? I've been >> thinking about performance issues while reading that thread. I agree that >> triangulating a polygon is not the sort of task that OpenSCAD was designed >> for. >> >> I think that some of this is driven by the fact that OpenSCAD provides a >> limited set of primitive shapes, and if you want to go beyond that, you >> need to use polyhedron(). And if you really push the limits of what can be >> expressed with polyhedron(), then you can get into requiring these complex >> calculations. >> >> I'd like to provide an easier way than polyhedron() for constructing >> complex mathematically defined shapes. I think Functional Representation >> would be a great thing to support. Of course, that opens up an even bigger >> can of worms than simply speeding up the interpreter using a byte code >> compiler. >> >> On 12 April 2016 at 09:06, nop head <nop.head@gmail.com> wrote: >> >>> Yes but is it worth it as most of time the geometry generation is many >>> orders of magnitude slower? Why would one want to qsort 40000 numbers in an >>> OpenScad script anyway? >>> >>> On 12 April 2016 at 13:36, doug moen <doug@moens.org> wrote: >>> >>>> In nophead's benchmark, >>>> Python is 15.6 times faster for quicksort, >>>> and 38.5 times faster for qs. >>>> >>>> I attribute this to the fact that Python compiles to bytecode. We >>>> should be able to get a 10x speedup pretty easily with a bytecode compiler, >>>> even before doing much performance tuning. Note that Python is slow >>>> compared to Javascript, which has insane amounts of performance >>>> optimization. >>>> >>>> On 12 April 2016 at 06:39, nop head <nop.head@gmail.com> wrote: >>>> >>>>> Interesting. >>>>> >>>>> With 40000 random numbers I also get 4s with quicksort but qs takes 3 >>>>> minutes 37 seconds for me. >>>>> >>>>> I translated it into Python to try to see what the difference is, >>>>> OpenScad desperately needs echo() in functions! >>>>> >>>>> import random >>>>> import time >>>>> >>>>> def pivot(arr): >>>>> return arr[int(len(arr)/2)] >>>>> >>>>> def high_part(arr): >>>>> p = pivot(arr) >>>>> return [y for y in arr if y > p] >>>>> >>>>> def middle_part(arr): >>>>> p = pivot(arr) >>>>> return [y for y in arr if y == p] >>>>> >>>>> def low_part(arr): >>>>> p = pivot(arr) >>>>> return [y for y in arr if y < p] >>>>> >>>>> def qs(arr, arr_out=[], n = 0): >>>>> #print n, arr >>>>> return arr_out if len(arr) == 0 else qs(high_part(arr), >>>>> qs(low_part(arr), arr_out, 2) + middle_part(arr), 1) >>>>> >>>>> def quicksort(arr, n = 0): >>>>> #print n, arr >>>>> if len(arr) == 0: return [] >>>>> pivot = arr[int(len(arr)/2)] >>>>> lesser = [y for y in arr if y < pivot] >>>>> equal = [y for y in arr if y == pivot] >>>>> greater = [y for y in arr if y > pivot] >>>>> return quicksort(lesser, 2) + equal + quicksort(greater, 1) >>>>> >>>>> list = [random.random() for x in xrange(40000)] >>>>> >>>>> t0 = time.time() >>>>> qs(list) >>>>> t1 = time.time() >>>>> quicksort(list) >>>>> t2 = time.time() >>>>> >>>>> print "qs:", round(t1 - t0, 3), "quicksort:", round(t2 - t1, 3) >>>>> >>>>> There is also a big difference in timings: qs: 5.632 quicksort: 0.256 >>>>> >>>>> I hoisted the pivot calculations out of the loops and I did the same >>>>> in the openscad version with let but it made no difference. >>>>> >>>>> If I add the commented out print statements and use a small array of >>>>> integers it prints exactly the same calls and intermediate results, so I >>>>> can't explain the big time difference. Perhaps there are more list copies >>>>> due to passing arr_out forward. >>>>> >>>>> >>>>> On 12 April 2016 at 03:02, Ronaldo <rcmpersiano@gmail.com> wrote: >>>>> >>>>>> Bingo! Why I didn't see that? Well, I think I hadn't fully grasped >>>>>> quicksort >>>>>> algorithm. :( >>>>>> >>>>>> Meanwhile, I got a version of quicksort which seems to have the >>>>>> pattern of >>>>>> tail recursion: >>>>>> >>>>>> > function qs(arr, arr_out=[]) = >>>>>> > !(len(arr)>0) ? >>>>>> > arr_out : >>>>>> > qs( arr = high_part(arr), >>>>>> > arr_out = concat(qs( low_part(arr), arr_out ), >>>>>> > middle_part(arr)) ); >>>>>> > >>>>>> > function high_part (arr) = [ for (y = arr) if (y > pivot(arr)) y >>>>>> ]; >>>>>> > function middle_part(arr) = [ for (y = arr) if (y == pivot(arr)) y >>>>>> ]; >>>>>> > function low_part (arr) = [ for (y = arr) if (y < pivot(arr)) y >>>>>> ]; >>>>>> > function pivot (arr) = arr[floor(len(arr)/2)]; >>>>>> >>>>>> I were able to sort a worst case array of length 5000 in 48sec with >>>>>> qs(). >>>>>> The previous quicksort() function fail with stack overflow for lengths >>>>>> lesser than 4000. However, it is much slower: for a random array with >>>>>> 40000 >>>>>> values, qs() required 60 sec while quicksort() spent just 4sec. >>>>>> >>>>>> >>>>>> >>>>>> -- >>>>>> View this message in context: >>>>>> http://forum.openscad.org/Quicksort-tp17044p17051.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 >>>>>> >>>>> >>>>> >>>>> _______________________________________________ >>>>> OpenSCAD mailing list >>>>> Discuss@lists.openscad.org >>>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>>>> >>>>> >>>> >>>> _______________________________________________ >>>> OpenSCAD mailing list >>>> Discuss@lists.openscad.org >>>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>>> >>>> >>> >>> _______________________________________________ >>> OpenSCAD mailing list >>> Discuss@lists.openscad.org >>> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >>> >>> >> >> _______________________________________________ >> OpenSCAD mailing list >> Discuss@lists.openscad.org >> http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org >> >> > > _______________________________________________ > OpenSCAD mailing list > Discuss@lists.openscad.org > http://lists.openscad.org/mailman/listinfo/discuss_lists.openscad.org > >