Author Topic: (Challenge) To draw the shortest lwpolyline  (Read 45915 times)

0 Members and 1 Guest are viewing this topic.

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1095
  • Marco
Re: (Challenge) To draw the shortest lwpolyline
« Reply #135 on: May 29, 2020, 03:19:13 AM »
I have a problem LISP crashed in BricsCAD with this message :

Code: [Select]
; ----- LISP : Call Stack -----
; [0]...C:TSP-2D-MR-LATEST-NEW
; [1].....DEPTH
; [2].......UNIQUE # 1108 <<--
;
; ----- Error around expression -----
; (EQUAL A B 1.0e-06)
;
; error : out of LISP 'Heap' memory at [gc]
<clip>

Keep in mind that the list with atoms-family  is at the limit of the memory (also in AutoCAD) and depends on your starting atoms-family length:
Code: [Select]
(length(atoms-family 1)) => 5519
:(progn
(_> (gc)
(_> (setq aList (atoms-family 1))
(_> (repeat 11 (setq aList (append aList aList)))
(_> (prompt "\nLength: ") (princ (length aList))
(_> (princ)
(_> )
Length: 11302912

: (progn
(_> (gc)
(_> (setq aList (atoms-family 1))
(_> (repeat 12 (setq aList (append aList aList)))
(_> (prompt "\nLength: ") (princ (length aList))
(_> (princ)
(_> )
; ----- Error around expression -----
; (APPEND ALIST ALIST)
;
; error : out of LISP 'Heap' memory at [gc]

VovKa

  • Swamp Rat
  • Posts: 1280
  • Ukraine
Re: (Challenge) To draw the shortest lwpolyline
« Reply #136 on: May 29, 2020, 06:19:23 AM »
But those are minimal improvements...
i don't have bcad
can you benchmark TSP-2D-MR-LATEST-NEW with different versions of unique?

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #137 on: May 29, 2020, 07:04:01 AM »
But those are minimal improvements...
i don't have bcad
can you benchmark TSP-2D-MR-LATEST-NEW with different versions of unique?

Indeed you are right, but what's the trick???

Code: [Select]
With my (unique) on BricsCAD :

: TSP-2D-MR-LATEST-NEW

Select points, blocks or circles in WCS...
Select entities:
Opposite Corner:
Entities in set: 40
Select entities:
Specify depth number - positive integer - from 0 to 32 <32> :
Specify number of solution attempts per depth iteration - preferable 50 <all> : 100
Specify number of list length processed by (processpt) sub function - preferable 2 <all> : 2

Distance : 19586.78862941693
Elapsed time : 157734 milliseconds...

With your (unique) on BricsCAD :

: TSP-2D-MR-LATEST-NEW

Select points, blocks or circles in WCS...
Select entities:
Opposite Corner:
Entities in set: 40
Select entities:
Specify depth number - positive integer - from 0 to 32 <32> :
Specify number of solution attempts per depth iteration - preferable 50 <all> : 100
Specify number of list length processed by (processpt) sub function - preferable 2 <all> : 2

Distance : 19586.78862941693
Elapsed time : 146703 milliseconds...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #138 on: May 29, 2020, 07:17:38 AM »
This is even more weird :
I changed at the end of my (unique) l into (cdr l) :

Code - Auto/Visual Lisp: [Select]
  1. ...
  2.   (defun depth ( plll m / unique sort trimbynum trimbyperc plr pllll )
  3.  
  4.     (defun unique ( l / x ll )
  5.       (while (setq x (car l))
  6.         (setq ll (cons x ll))
  7.         (setq l (vl-remove-if (function (lambda ( y ) (vl-every (function (lambda ( a b ) (equal a b 1e-6))) y (member (car y) (append x x))))) (cdr l)))
  8.       )
  9.       ll
  10.     )
  11. ...
  12.  

And now instead of TSP beeing faster - it's slower :

Code: [Select]
: TSP-2D-MR-LATEST-NEW

Select points, blocks or circles in WCS...
Select entities:
Opposite Corner:
Entities in set: 40
Select entities:
Specify depth number - positive integer - from 0 to 32 <32> :
Specify number of solution attempts per depth iteration - preferable 50 <all> : 100
Specify number of list length processed by (processpt) sub function - preferable 2 <all> : 2

Distance : 19586.78862941693
Elapsed time : 261766 milliseconds...

I really can'r explain what's going here : It seems that my results are unreliable...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #139 on: May 29, 2020, 07:29:09 AM »
I restarted BricsCAD and now I get this :

Code: [Select]
: TSP-2D-MR-LATEST-NEW

Select points, blocks or circles in WCS...
Select entities:
Opposite Corner:
Entities in set: 40
Select entities:
Specify depth number - positive integer - from 0 to 32 <32> :
Specify number of solution attempts per depth iteration - preferable 50 <all> : 100
Specify number of list length processed by (processpt) sub function - preferable 2 <all> : 2

Distance : 19586.78862941693
Elapsed time : 155390 milliseconds...

This is my (unique) with (cdr l)...
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #140 on: May 29, 2020, 07:34:42 AM »
I restarted BricsCAD and now I get this with VovKa's (unique) :

Code: [Select]
: TSP-2D-MR-LATEST-NEW

Select points, blocks or circles in WCS...
Select entities:
Opposite Corner:
Entities in set: 40
Select entities:
Specify depth number - positive integer - from 0 to 32 <32> :
Specify number of solution attempts per depth iteration - preferable 50 <all> : 100
Specify number of list length processed by (processpt) sub function - preferable 2 <all> : 2

Distance : 19586.78862941693
Elapsed time : 138094 milliseconds...

So it's faster...
What else can you remedy in my routine VovKa?
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #141 on: May 29, 2020, 09:15:35 AM »
I decided to update changes by VovKa and my minor things I spoted to make code more concise, but performance is the same as my last test...
Update is here : http://www.theswamp.org/index.php?topic=30434.msg600027#msg600027

M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #142 on: May 29, 2020, 10:30:35 AM »
I see that VovKa was looking at my revision, but I forgot to add (actually I removed it from unknown reasons) line 77 :
(setq pllll (reverse pllll))

Sorry for my mistake, now should be all as it was before, just fine...

[EDIT : I am still in blunder with this 77 line... It seems that it should be fine and without it. It doesn't matter which order list are processed in (processpt) - all shortest paths are added to pllll - that's important not order in pllll itself... I'll leave line 77, but IMHO there is no need for it actually. So my previous revision was also OK...]

[EDIT : I removed line 77 and added (gc) in both (processpt) and (unique)...]
« Last Edit: June 02, 2020, 06:38:16 PM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

VovKa

  • Swamp Rat
  • Posts: 1280
  • Ukraine
Re: (Challenge) To draw the shortest lwpolyline
« Reply #143 on: May 29, 2020, 11:41:13 AM »
So it's faster...
i benchmarked both functions - your original-while unique and mine unique3
Code: [Select]
_$ (length testlst)
500
_$ (length (unique testlst))
237
_$ (length (unique3 testlst))
237
_$ (BenchMark '((unique testlst) (unique3 testlst)))
Benchmarking ....Elapsed milliseconds / relative speed for 2 iteration(s):

    (UNIQUE3 TESTLST).....1404 / 2.47 <fastest>
    (UNIQUE TESTLST)......3463 / 1 <slowest>
as you can see those small 'technical' changes yield a big speed gain

What else can you remedy in my routine VovKa?
not me but you :)
analyzing other people's code is a hell of a job. don't have time for it

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #144 on: June 03, 2020, 09:17:50 AM »
I have a problem LISP crashed in BricsCAD with this message :

Code: [Select]
; ----- LISP : Call Stack -----
; [0]...C:TSP-2D-MR-LATEST-NEW
; [1].....DEPTH
; [2].......UNIQUE # 1108 <<--
;
; ----- Error around expression -----
; (EQUAL A B 1.0e-06)
;
; error : out of LISP 'Heap' memory at [gc]
<clip>

Keep in mind that the list with atoms-family  is at the limit of the memory (also in AutoCAD) and depends on your starting atoms-family length:
Code: [Select]
(length(atoms-family 1)) => 5519
:(progn
(_> (gc)
(_> (setq aList (atoms-family 1))
(_> (repeat 11 (setq aList (append aList aList)))
(_> (prompt "\nLength: ") (princ (length aList))
(_> (princ)
(_> )
Length: 11302912

: (progn
(_> (gc)
(_> (setq aList (atoms-family 1))
(_> (repeat 12 (setq aList (append aList aList)))
(_> (prompt "\nLength: ") (princ (length aList))
(_> (princ)
(_> )
; ----- Error around expression -----
; (APPEND ALIST ALIST)
;
; error : out of LISP 'Heap' memory at [gc]

According to my tests, on my PC :
AutoCAD 2018 - list length limit : 20,000,000
BricsCAD V20 - list length limit : 10,000,000

So AutoCAD has better chances with this routine, but it's 2-10x slower and it don't crash when limit exceeded but goes into never ending calculations which is bad...

Here is my testing function and my results :

Code - Auto/Visual Lisp: [Select]
  1. ;|
  2. (c:makestartlsts)
  3. *l* and **l** are globals so that you can try upon finish of test, something like this (not to show output) :
  4. (progn (gc) (setq *l* (eval (cons 'append (repeat 27 (setq *r* (cons '*l* *r*)))))) (princ (length *l*)) (princ))
  5. and then finally :
  6. (progn (gc) (setq *l* (append *l* **l**)) (princ (length *l*)) (princ))
  7. (setq *l* nil **l** nil *r* nil)
  8. |;
  9.  
  10. (defun c:makestartlsts nil
  11.   (setq *l* (atoms-family 1))
  12.   (prompt "\nLength - (setq *l* (atoms-family 1)) : ") (princ (length *l*))
  13.   (repeat 7
  14.     (setq *l* (append *l* *l*))
  15.   )
  16.   (setq **l** *l*)
  17.   (prompt "\nLength - repeat 10 - (setq *l* (append *l* *l*)) = (128 x *l*) : ") (princ (length *l*))
  18.   (princ)
  19. )
  20.  
  21. ;;; AutoCAD test ;;;
  22. ;|
  23. Command: MAKESTARTLSTS
  24. Length - (setq *l* (atoms-family 1)) : 5750
  25. Length - repeat 10 - (setq *l* (append *l* *l*)) = (128 x *l*) : 736000
  26. Command:
  27. Command: (progn (gc) (setq *l* (eval (cons 'append (repeat 27 (setq *r* (cons '*l* *r*)))))) (princ (length *l*)) (princ))
  28. 19872000
  29. |;
  30.  
  31. ;;; If I then use this line : (progn (gc) (setq *l* (append *l* **l**)) (princ (length *l*)) (princ)) ;;; AutoCAD don't crash but calculates never ending
  32.  
  33. ;;; BricsCAD test ;;;
  34. ;|
  35. : MAKESTARTLSTS
  36.  
  37. Length - (setq *l* (atoms-family 1)) : 4847
  38. Length - repeat 10 - (setq *l* (append *l* *l*)) = (128 x *l*) : 620416
  39. : (progn (gc) (setq *l* (eval (cons 'append (repeat 32 (setq *r* (cons '*l* *r*)))))) (princ (length *l*)) (princ))
  40.  
  41. ; ----- Error around expression -----
  42. ; (APPEND *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L*)
  43. ;
  44. ; error : out of LISP 'Heap' memory at [gc]
  45. : (progn (gc) (setq *l* (eval (cons 'append (repeat 27 (setq *r* (cons '*l* *r*)))))) (princ (length *l*)) (princ))
  46.  
  47. ; ----- Error around expression -----
  48. ; (GC)
  49. ;
  50. ; error : out of LISP 'Heap' memory at [gc]
  51. |;
  52.  
  53. ;;; Restart BricsCAD ;;;
  54. ;|
  55. : MAKESTARTLSTS
  56.  
  57. Length - (setq *l* (atoms-family 1)) : 4847
  58. Length - repeat 10 - (setq *l* (append *l* *l*)) = (128 x *l*) : 620416
  59. : (progn (gc) (setq *l* (eval (cons 'append (repeat 24 (setq *r* (cons '*l* *r*)))))) (princ (length *l*)) (princ))
  60.  
  61. ; ----- Error around expression -----
  62. ; (APPEND *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L* *L*)
  63. ;
  64. ; error : out of LISP 'Heap' memory at [gc]
  65. |;
  66.  
  67. ;;; Restart BricsCAD ;;;
  68. ;|
  69. : MAKESTARTLSTS
  70.  
  71. Length - (setq *l* (atoms-family 1)) : 4847
  72. Length - repeat 10 - (setq *l* (append *l* *l*)) = (128 x *l*) : 620416
  73. : (progn (gc) (setq *l* (eval (cons 'append (repeat 16 (setq *r* (cons '*l* *r*)))))) (princ (length *l*)) (princ))
  74. 9926656
  75. : (progn (gc) (setq *l* (append *l* **l**)) (princ (length *l*)) (princ))
  76.  
  77. ; ----- Error around expression -----
  78. ; (APPEND *L* **L**)
  79. ;
  80. ; error : out of LISP 'Heap' memory at [gc]
  81. |;
  82.  

Regards, M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

Marc'Antonio Alessi

  • Swamp Rat
  • Posts: 1095
  • Marco
Re: (Challenge) To draw the shortest lwpolyline
« Reply #145 on: June 03, 2020, 10:35:15 AM »
> According to my tests, on my PC :
> AutoCAD 2018 - list length limit : 20,000,000
> BricsCAD V20 - list length limit : 10,000,000

it's pretty much the same on my PC too...

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #146 on: June 05, 2020, 11:09:52 AM »
I discovered that there is no much gain if polyline is updated in each loop by 1 single point if specified depth is less than maximum and calculations of depth start from nil over and over again with each new 1 point update... So I decided to change the code in the way that when depth is calculated, lwpolyline updates with number of points depth calculated and from this update, depth calculations start over from nil, but with more points already processed... So this is now much faster if you for ex. specify preferable values (depth = 3; length of list = 100; processed points = 2)... The result is not as should be with all maximal values which is BTW. impossible to reach if case is with free points more than cca. 10 - allowed list length processed may be over 10,000,000; but the result is satisfactory in relation elapsed time / calculated distance, still not as shortpath.vlx but very satisfactory IMHO...

My code on page 9 updated...
Regards, and stay well, M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #147 on: June 06, 2020, 01:17:22 AM »
I've added one more input - incremental depth...

Code updated I hope finally...

M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #148 on: June 21, 2020, 12:23:53 PM »
Hi, here is my new input...
I searched for a ways this could be done in less time, but I found that this is only possible if searching is reduced to point clouds that don't go over 9 points... I coded for all cases - if you want exact solution, you must specify complete point cloud - selection of all points and if it's over 9 points, then you'll have to wait for a long time (if it's even possible to complete the task) - it is strongly recommended that you do not specify in input more than 9 points and if there are many points, then 9 points specification is preferable... Still my already posted code is IMHO the best, but it may prove that the task could be completed in less time, but with less reliability of resulting solution... Until someone convert posted lisp to something else - arx, dll; here is my protected vlx that is alternative to shortpath.vlx... The command to invoke is TSP-2D-PTCLOUDS - the same as the name of vlx... But in almost all cases shortpath.vlx beat my version both in speed and solutions... Still I've found one example where my version found better solution and with my posted lisp (look previous postings) with more exhaustive inputs there was found even better solution... I am still not sure if this is exact solution as there were many points above 10 (18) - convex hull simplified somewhat things and so the green solution was found... When it comes to my vlx - convex hull is used only in finding starting solution - after that all points are considered in finding better - if there is better, so not much help from convex hull... Already posted lisp is still the best if you don't hurry, only someone has to make it even faster by coding other than LISP...

So now no code as it would spoil latest lisp version which is the best IMO, just protected vlx and dwg where shortpath.vlx was beaten - both with white after specified point cloud 9 with my vlx and green solution after long time processing with latest lisp here posted...

BTW. LISP version may prove even faster than my vlx if convex hull is complex and there left small number of free inside points from reasons I explained, so it is the good way for correct solving TSP, just it would be better if programmed other than LISP...

I wish you good luck if you try to improve LISP and (or) you found a ways for solution different than proposed in this topic...
M.R.
« Last Edit: June 25, 2020, 11:24:27 AM by ribarm »
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube

ribarm

  • Water Moccasin
  • Posts: 2412
  • Marko Ribar, architect
Re: (Challenge) To draw the shortest lwpolyline
« Reply #149 on: June 24, 2020, 11:29:55 AM »
Just to inform... I found some lacks in portion with check of lines intersections, so I updated both *.vlx and posted lisp... It is strongly suggested that you copy+paste lisp in your file and update old one...

Regards, M.R.
Marko Ribar, d.i.a. (graduated engineer of architecture)

:)

M.R. on Youtube