Topic: (Challenge) To draw the shortest lwpolyline

[VovKa]

But those are minimal improvements...

i don't have bcad
can you benchmark TSP-2D-MR-LATEST-NEW with different versions of unique?

[ribarm]

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


[ribarm]

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

[ribarm]

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

[ribarm]

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?

[ribarm]

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.

[ribarm]

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)...]

[VovKa]

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]

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.

[Marc'Antonio Alessi]

> 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]

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.

[ribarm]

I've added one more input - incremental depth...

Code updated I hope finally...

M.R.

[ribarm]

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.

[ribarm]

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.

[ribarm]

I figured this out : Maybe someone really needs this faster... So I had a time to combine posted codes and I managed to improve shortpath.vlx results... Results are better, but in cost of speed... But all in all I used all fast codes I saw and now I suppose that it's acceptable... So finally this is what I came with, but I must warn you : don't take everything for grand... The results are better, but not reliable like it's supposed to be (my last code I posted), but who the hell can wait to eternity to get a result that is satisfactory enough... And just not to forget, thanks to Mr. Evgeniy Elpanov and chlh_jd who both provided very well codes for us to develop based on them... I know - I haven't stated inside LISP from where codes (subs) originates, but I modified them myself and they are obvious for reader so I believe that anyone can recognize them... So I dwarfed shortpath.vlx which is BTW. not open source and is old enough so I can say with very much confident that that file is no longer efficient - IMO it used E.E. subs combined with chlh_jd's in very direct way... (when you check results - it's almost exact copy of chlh_jd's code posted in this topic)

So here is my LISP and I hope you'll find it somewhat more useful then I do, but anyway it was fun to code it...
Regards, M.R.

[EDIT : There were some lacks in localizing variables of sub functions... I'll reattach LSP - there were 7 downloads till now...]