Đến nội dung


Hình ảnh
- - - - -

[Thảo luận] Biện pháp tăng tốc độ trong các chương trình Lisp


  • Please log in to reply
44 replies to this topic

#1 Doan Van Ha

Doan Van Ha

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 5454 Bài viết
Điểm đánh giá: 2626 (tuyệt vời)

Đã gửi 29 July 2013 - 04:11 PM

Nhiều khi đau đầu với việc viết lisp xong mà nó chạy như rùa bò, trong khi nhìn thấy mọi người code những bài toán đồ sộ lại chạy trơn tru.

Lại nhiều khi nghe nói dùng hàm này sẽ chậm, dùng hàm kia sẽ nhanh.

Lại nhiều khi nữa, cũng nghe nói: giải thuật cho bài toán là vấn đề cốt lõi trong việc đua tốc độ.

V.v và v.v…

Thành thử, mạo muội mở topic này để mong được học hỏi mọi người, cũng như cùng nhau học hỏi, phương pháp code lisp sao cho đạt kết quả tối ưu về tốc độ.

1). Hy vọng các bạn có nhiều kinh nghiệm sẽ cùng nhau chia sẻ tại đây.

2). Hy vọng ai có điều chi băn khoăn về tốc độ cũng chia sẻ tại đây để nhận được tư vấn.

Xin mời!


  • 2

* Chỉ nên yêu cầu Lisp khi bạn làm việc đó mất cả ngày nhưng họ chỉ viết 1 giờ. Đừng nêu yêu cầu Lisp khi bạn chỉ làm 1 giờ nhưng bắt họ phải mất cả ngày.

* Nhờ viết lisp cũng như đi khám bệnh. Chỉ gởi căn cước và than sắp chết thì không bác sỹ nào cứu sống được.


#2 Doan Van Ha

Doan Van Ha

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 5454 Bài viết
Điểm đánh giá: 2626 (tuyệt vời)

Đã gửi 15 September 2013 - 04:14 PM

Khá nhiều thời gian trôi qua mà chưa thấy ai mở màn.

Bài toán số 1:

Cho điểm P và một tập gồm N điểm trong không gian.

Tìm điểm Q trong tập N, sao cho khoảng cách PQ là bé nhất?

Bài toán này nếu giải theo “thuật toán tuần tự”, tức là lần lượt tính khoảng cách từ P đến tất cả các điểm Qi của tập N rồi so sánh để chọn thì sẽ rất chậm, nhất là khi tập N đủ lớn.

Vậy, bạn nào biết thì giúp đề xuất một giải thuật để việc tính toán được nhanh hơn?

[Trong thực tế, có rất nhiều bài toán tương tự bài toán này.]


  • 0

* Chỉ nên yêu cầu Lisp khi bạn làm việc đó mất cả ngày nhưng họ chỉ viết 1 giờ. Đừng nêu yêu cầu Lisp khi bạn chỉ làm 1 giờ nhưng bắt họ phải mất cả ngày.

* Nhờ viết lisp cũng như đi khám bệnh. Chỉ gởi căn cước và than sắp chết thì không bác sỹ nào cứu sống được.


#3 phamthanhbinh

phamthanhbinh

    biết lệnh adcenter

  • Moderator
  • PipPipPipPipPipPipPip
  • 6009 Bài viết
Điểm đánh giá: 3113 (tuyệt vời)

Đã gửi 15 September 2013 - 08:13 PM

Khá nhiều thời gian trôi qua mà chưa thấy ai mở màn.

Bài toán số 1:

Cho điểm P và một tập gồm N điểm trong không gian.

Tìm điểm Q trong tập N, sao cho khoảng cách PQ là bé nhất?

Bài toán này nếu giải theo “thuật toán tuần tự”, tức là lần lượt tính khoảng cách từ P đến tất cả các điểm Qi của tập N rồi so sánh để chọn thì sẽ rất chậm, nhất là khi tập N đủ lớn.

Vậy, bạn nào biết thì giúp đề xuất một giải thuật để việc tính toán được nhanh hơn?

[Trong thực tế, có rất nhiều bài toán tương tự bài toán này.]

Hề hề hề,

Xin phép bác DoanvanHa, mình xin nêu một ý tưởng có thể rút ngắn được việc này như sau:

1/- Chia nhóm đối tương được chọn theo vùng chọn thành hai vùng liền kế nhau theo trục x hoặc trục y. Tìm và so sánh khoảng cách từ tâm hai vùng chọn này tới điểm cho trước để lấy vùng chọn thích hợp. Lưu ý kiểm tra để mỗi vùng chọn có tối thiểu 1 đối tượng.

2/- Tiếp tực chia vùng chọn lấy ra thành hai vùng chọn liền kề theo trục y hoặc trục x và làm tương tự cho tới khi trong một vùng chọn được chia ra không có đối tượng nào 

3/- Xác định khoảng cách từ điểm đã cho tới các điểm trong vùng chọn cuối cùng và so sánh chúng để cho ra điểm chọn phù hợp với yêu cầu.


  • 0
Chúc các quý Anh trên diễn đàn luôn khỏe, đẻ thêm được nhiều thứ để mót.

#4 Tue_NV

Tue_NV

    KS Võ Quang Tuệ

  • Moderator
  • PipPipPipPipPipPipPip
  • 4296 Bài viết
Điểm đánh giá: 3805 (đỉnh cao)

Đã gửi 15 September 2013 - 08:57 PM

Hề hề hề,

Xin phép bác DoanvanHa, mình xin nêu một ý tưởng có thể rút ngắn được việc này như sau:

1/- Chia nhóm đối tương được chọn theo vùng chọn thành hai vùng liền kế nhau theo trục x hoặc trục y. Tìm và so sánh khoảng cách từ tâm hai vùng chọn này tới điểm cho trước để lấy vùng chọn thích hợp. Lưu ý kiểm tra để mỗi vùng chọn có tối thiểu 1 đối tượng.

2/- Tiếp tực chia vùng chọn lấy ra thành hai vùng chọn liền kề theo trục y hoặc trục x và làm tương tự cho tới khi trong một vùng chọn được chia ra không có đối tượng nào 

3/- Xác định khoảng cách từ điểm đã cho tới các điểm trong vùng chọn cuối cùng và so sánh chúng để cho ra điểm chọn phù hợp với yêu cầu.

 

Chào bác Bình!

Bài toán đang xác định là "trong không gian" bác ạ, bác quên trục Z mất rồi.....

Cho điểm P và một tập gồm N điểm trong không gian.


  • 1

#5 Skywings

Skywings

    biết lệnh erase

  • Members
  • PipPipPip
  • 102 Bài viết
Điểm đánh giá: 46 (tàm tạm)

Đã gửi 15 September 2013 - 10:49 PM

Chào bác Bình!

Bài toán đang xác định là "trong không gian" bác ạ, bác quên trục Z mất rồi.....

Cho điểm P và một tập gồm N điểm trong không gian.

 

Theo mình thì cách bác Bình khả thi, tập điểm trong không gian có thể bỏ qua Z để quy về mặt phẳng XY và chia vùng kiểm tra. Hàm SSGET có thể dùng để kiểm tra số lượng đối tượng, các điểm trong vùng kiểm tra dù Z khác nhau vẫn được chọn thôi. Dù sao thì cũng phải code thử để so sánh tốc độ thực thi ^^.


  • 0

#6 Tue_NV

Tue_NV

    KS Võ Quang Tuệ

  • Moderator
  • PipPipPipPipPipPipPip
  • 4296 Bài viết
Điểm đánh giá: 3805 (đỉnh cao)

Đã gửi 16 September 2013 - 06:52 AM

Theo mình thì cách bác Bình khả thi, tập điểm trong không gian có thể bỏ qua Z để quy về mặt phẳng XY và chia vùng kiểm tra. Hàm SSGET có thể dùng để kiểm tra số lượng đối tượng, các điểm trong vùng kiểm tra dù Z khác nhau vẫn được chọn thôi. Dù sao thì cũng phải code thử để so sánh tốc độ thực thi ^^.

 

Đang đưa ra bài toán tổng quát là trong không gian, sao có thể bỏ qua Z được bạn hè?

"Hàm SSGET có thể dùng để kiểm tra số lượng đối tượng, các điểm trong vùng kiểm tra dù Z khác nhau vẫn được chọn thôi"

Hàm ssget chọn được các đối tượng đồng phẳng, các điểm trong vùng kiểm tra dù Z khác nhau răng mà chọn được?


  • 0

#7 gia_bach

gia_bach

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 1436 Bài viết
Điểm đánh giá: 1426 (rất tốt)

Đã gửi 16 September 2013 - 07:49 AM

Hề hề hề,

Xin phép bác DoanvanHa, mình xin nêu một ý tưởng có thể rút ngắn được việc này như sau:

1/- Chia nhóm đối tương được chọn theo vùng chọn thành hai vùng liền kế nhau theo trục x hoặc trục y. Tìm và so sánh khoảng cách từ tâm hai vùng chọn này tới điểm cho trước để lấy vùng chọn thích hợp. Lưu ý kiểm tra để mỗi vùng chọn có tối thiểu 1 đối tượng.

2/- Tiếp tực chia vùng chọn lấy ra thành hai vùng chọn liền kề theo trục y hoặc trục x và làm tương tự cho tới khi trong một vùng chọn được chia ra không có đối tượng nào 

3/- Xác định khoảng cách từ điểm đã cho tới các điểm trong vùng chọn cuối cùng và so sánh chúng để cho ra điểm chọn phù hợp với yêu cầu.

Chào bác Bình :

Cách của bác là "phun các điểm đã cho vào Cad, rồi xử lý trong Cad".

- Ưu : tận dụng các hàm của CAD-LISP 

- nhược : mất thêm t/gian "phun" vào CAD và SSGET.

Nếu đi theo hướng này có thể viết hàm SSGET theo đường tròn, rồi cho vòng lặp chạy khi bán kính thay đổi.

(hoặc SSget theo hình cầu nếu tập N là 3D _ hơi bị khó ???).

 

@ HA: để cho đơn giản nên rút gọn tập N về trong mặt phẳng 2D.


  • 0

#8 Doan Van Ha

Doan Van Ha

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 5454 Bài viết
Điểm đánh giá: 2626 (tuyệt vời)

Đã gửi 16 September 2013 - 08:11 AM

@ HA: để cho đơn giản nên rút gọn tập N về trong mặt phẳng 2D.

Vậy thì chúng ta có thể chia thành 2 bài toán:

Bài toán 1a: tập hợp điểm N và P nằm trong 2D (dễ hơn).

Bài toán 1b: tập hợp điểm N và P nằm trong 3D (khó hơn).

Chú ý: các điểm này là các point đã có trên bản vẽ, không cần phun gì nữa.

Vấn đề của bài toán là tìm giải thuật, để từ đó có thể áp dụng cho các bài toán tương tự.

Hy vọng mọi người sẽ đóng góp những giải thuật hay.


  • 0

* Chỉ nên yêu cầu Lisp khi bạn làm việc đó mất cả ngày nhưng họ chỉ viết 1 giờ. Đừng nêu yêu cầu Lisp khi bạn chỉ làm 1 giờ nhưng bắt họ phải mất cả ngày.

* Nhờ viết lisp cũng như đi khám bệnh. Chỉ gởi căn cước và than sắp chết thì không bác sỹ nào cứu sống được.


#9 Skywings

Skywings

    biết lệnh erase

  • Members
  • PipPipPip
  • 102 Bài viết
Điểm đánh giá: 46 (tàm tạm)

Đã gửi 16 September 2013 - 08:48 AM

Đang đưa ra bài toán tổng quát là trong không gian, sao có thể bỏ qua Z được bạn hè?

"Hàm SSGET có thể dùng để kiểm tra số lượng đối tượng, các điểm trong vùng kiểm tra dù Z khác nhau vẫn được chọn thôi"

Hàm ssget chọn được các đối tượng đồng phẳng, các điểm trong vùng kiểm tra dù Z khác nhau răng mà chọn được?

 

Vùng chọn của SSGET chọn được tất cả các điểm trong không gian, không chỉ đồng phẳng. Mình đã test rùi mới nói. Do đó tập điểm 2D hay 3D cũng như nhau thôi.


  • 0

#10 Tue_NV

Tue_NV

    KS Võ Quang Tuệ

  • Moderator
  • PipPipPipPipPipPipPip
  • 4296 Bài viết
Điểm đánh giá: 3805 (đỉnh cao)

Đã gửi 16 September 2013 - 09:03 AM

Vùng chọn của SSGET chọn được tất cả các điểm trong không gian, không chỉ đồng phẳng. Mình đã test rùi mới nói. Do đó tập điểm 2D hay 3D cũng như nhau thôi.

 

Vấn đề ở đây là không phải mình chọn tay (dùng chuột để quét) mà sử dụng để cho máy tự chọn. Hàm ssget với các tham số "C" "WP" "CP"


  • 0

#11 Skywings

Skywings

    biết lệnh erase

  • Members
  • PipPipPip
  • 102 Bài viết
Điểm đánh giá: 46 (tàm tạm)

Đã gửi 16 September 2013 - 09:46 AM

Mình có thể dùng tham số "_W" hoặc "_C" chỉ cần với 2 điểm có thể tạo được vùng chọn chọn được các điểm 3D.


  • 0

#12 hiepttr

hiepttr

    Edu level: li10

  • Members
  • PipPipPipPipPipPipPip
  • 1298 Bài viết
Điểm đánh giá: 518 (tốt)

Đã gửi 16 September 2013 - 10:03 AM

Mình có thể dùng tham số "_W" hoặc "_C" chỉ cần với 2 điểm có thể tạo được vùng chọn chọn được các điểm 3D.

Bác hiểu sai ý bác TueNV rồi !

Mình nói thế này để bác dễ hiểu nhé,

giã sữ gốc 0,0,0 của hệ toạ độ trùng với điểm đang xét, bạn loại trừ trục Z ra thì vô tình điểm có toạ độ (0,0,+"vô cùng") lại có khoảng cách đến điểm đang xét ngắn hơn điểm có toạ độ (1,1,0) ...


  • 0

Có vợ dù dữ dù hiền , bạn đều có lợi
_ Nếu vợ hiền, bạn sẽ là người đàn ông sung sướng
_ Nếu vợ dữ, bạn sẽ thành ... triết gia !

Bergson


#13 Tue_NV

Tue_NV

    KS Võ Quang Tuệ

  • Moderator
  • PipPipPipPipPipPipPip
  • 4296 Bài viết
Điểm đánh giá: 3805 (đỉnh cao)

Đã gửi 16 September 2013 - 10:03 AM

Mình có thể dùng tham số "_W" hoặc "_C" chỉ cần với 2 điểm có thể tạo được vùng chọn chọn được các điểm 3D.

 

Bạn thử chưa? Bạn kiểm tra đối tượng mà bạn chọn đó có đồng phẳng không?

(ssget) với tham số "c" "cp" "wp" chỉ có thể chọn đối tượng đồng phẳng thôi, còn 3D thì không được .........


  • 0

#14 Skywings

Skywings

    biết lệnh erase

  • Members
  • PipPipPip
  • 102 Bài viết
Điểm đánh giá: 46 (tàm tạm)

Đã gửi 16 September 2013 - 10:27 AM

Bác hiểu sai ý bác TueNV rồi !

Mình nói thế này để bác dễ hiểu nhé,

giã sữ gốc 0,0,0 của hệ toạ độ trùng với điểm đang xét, bạn loại trừ trục Z ra thì vô tình điểm có toạ độ (0,0,+"vô cùng") lại có khoảng cách đến điểm đang xét ngắn hơn điểm có toạ độ (1,1,0) ...

 

Mình có nói bỏ luôn Z đâu, chỉ quy về mp XY trong việc chia vùng chọn.

 

 

Bạn thử chưa? Bạn kiểm tra đối tượng mà bạn chọn đó có đồng phẳng không?

(ssget) với tham số "c" "cp" "wp" chỉ có thể chọn đối tượng đồng phẳng thôi, còn 3D thì không được .........

 

Mình đã test rùi, tham số "W" và "C" chắc chắn được, "WP" và "CP" chắc chắn ... ko được ^^. Đoạn code đơn giản để test, bác có thể thử phun vài điểm point lên màn hình và thay đổi Z cho chúng.

 

(defun c:t1 (/ N P1 P2 PNT PNTLST)
  (setq	p1 (getpoint "1st point")
	p2 (getcorner p1 "\n2nd point")
  )
  (setq
;;;    pntLst (ssget "_W" p1 p2)
    pntLst
     (ssget "_C" p1 p2)
  )
  (setq n 0)
  (if pntLst
    (repeat (sslength pntLst)
      (setq pnt (cdr (assoc 10 (entget (ssname pntLst n)))))
      (print pnt)
      (setq n (1+ n))
    )
  )
  (princ "\nTotal selected points: ")
  (princ n)
  (princ)
)

  • 0

#15 hiepttr

hiepttr

    Edu level: li10

  • Members
  • PipPipPipPipPipPipPip
  • 1298 Bài viết
Điểm đánh giá: 518 (tốt)

Đã gửi 16 September 2013 - 10:45 AM

vùng chọn cũng thế thôi

1/- Chia nhóm đối tương được chọn theo vùng chọn thành hai vùng liền kế nhau theo trục x hoặc trục y. Tìm và so sánh khoảng cách từ tâm hai vùng chọn này tới điểm cho trước để lấy vùng chọn thích hợp. Lưu ý kiểm tra để mỗi vùng chọn có tối thiểu 1 đối tượng.

Nếu bạn bỏ qua Z từ đầu tức là đã có thể "sót nghiệm" :D


  • 0

Có vợ dù dữ dù hiền , bạn đều có lợi
_ Nếu vợ hiền, bạn sẽ là người đàn ông sung sướng
_ Nếu vợ dữ, bạn sẽ thành ... triết gia !

Bergson


#16 gia_bach

gia_bach

    biết lệnh adcenter

  • CADViet Team
  • PipPipPipPipPipPipPip
  • 1436 Bài viết
Điểm đánh giá: 1426 (rất tốt)

Đã gửi 16 September 2013 - 11:07 AM

Gửi anh em hàm "phun" ngẫu nhiên 1 số Point để test.

;;generate random points
(defun c:addPoint()
  ;;from internet
  (defun random ()
    (setq seed (if seed
		 (rem (+ (* seed 15625.7) 0.21137152) 1)
		 0.3171943	     )  ))
  (defun random-n (n) (* n (random)))
  ;main
  (repeat 100000 ;2D Point
    (entmake (list (cons 0 "POINT") (cons 10 (list (random-n 100000) (random-n 60000) 0))  )  ) )
  (repeat 5000 ;3D Point
    (entmake (list (cons 0 "POINT") (cons 10 (list (random-n 100000) (random-n 60000) (random-n 300)))  )  ) ))

Và đây là 1 cách mà Hà cho là lâu nhất (duyệt qua toàn bộ selection).

(defun c:test (/ ss pt i e st lst)
  ;By Gia_Bach
  (setq pt (getpoint "pick point")
	ss  (ssget "_x" '((0 . "point")))	
	i  -1
	st (getvar 'millisecs))
  (while (setq e (ssname ss (setq i (1+ i)))) (setq lst (cons (cdr (assoc 10 (entget e))) lst)))
  (setq lst (vl-sort lst (function (lambda (a b) (<= (distance a pt) (distance b pt))))) )
  (entmakex (list '(0 . "LINE") (cons 10 pt) (cons 11 (car lst))))  
  (princ (strcat "\nProgram running time: " (rtos (/ (- (getvar 'millisecs) st) 1000.) 2 4) " msecs."))
 (princ))

  • 2

#17 Skywings

Skywings

    biết lệnh erase

  • Members
  • PipPipPip
  • 102 Bài viết
Điểm đánh giá: 46 (tàm tạm)

Đã gửi 16 September 2013 - 01:48 PM

vùng chọn cũng thế thôi

Nếu bạn bỏ qua Z từ đầu tức là đã có thể "sót nghiệm" :D

Sót là sót thế nào  :huh: ? Có lẽ bạn chưa hiểu ý mình. Nếu bạn cũng cho rằng SSGET ko thể chọn tập điểm 3d thì hãy thử code mình post ở bài #15 nhé, xem có lọt điểm 3d nào trong vùng chọn ko?!

 

@Gia_Bach: cám ơn bác up đoạn code phun điểm random để test thử. Theo mình thì dùng "vl-sort" sẽ mất rất nhiều thời gian để sort điểm tăng dần hay giảm dần, trong khi mục đích chỉ là tìm MIN. Mình dùng phương pháp tìm MIN cổ điển, cũng duyệt qua toàn bộ selection nhưng thời gian ngắn hơn nhiều phương pháp dùng "vl-sort".

 

Mình test với 105000 điểm phun từ hàm Random của bác Gia_Bach:

- vl-sort:    5.7190 secs

- classico: 1.9840 secs.

 

(defun c:test2 (/ CLOSESTPNT DIS DISMIN I N PNT PT SS ST)
  (setq	pt (getpoint "pick point")
	ss (ssget "_x" '((0 . "point")))
	i  -1
	st (getvar 'millisecs)
  )
  ;; Skywings
  (setq	closestPnt (cdr (assoc 10 (entget (ssname ss 0))))
	disMin	   (distance pt closestPnt)
  )
  (setq n 1)
  (if ss
    (repeat (- (sslength ss) 1)
      (setq pnt	(cdr (assoc 10 (entget (ssname ss n))))
	    dis	(distance pt pnt)
	    n	(1+ n)
      )
      (if (< dis disMin)
	(setq disMin dis
	      closestPnt pnt
	)
      )
    )
  )
  (entmakex
    (list '(0 . "LINE") (cons 10 pt) (cons 11 closestPnt))
  )
  (princ
    (strcat "\nProgram running time: "
	    (rtos (/ (- (getvar 'millisecs) st) 1000.) 2 4)
	    " msecs."
    )
  )
  (princ)
)

Bài viết đã được chỉnh sửa nội dung bởi Skywings: 16 September 2013 - 04:53 PM

  • 0

#18 hiepttr

hiepttr

    Edu level: li10

  • Members
  • PipPipPipPipPipPipPip
  • 1298 Bài viết
Điểm đánh giá: 518 (tốt)

Đã gửi 16 September 2013 - 02:43 PM

Sót là sót thế nào  :huh: ? Có lẽ bạn chưa hiểu ý mình. Nếu bạn cũng cho rằng SSGET ko thể chọn tập điểm 3d thì hãy thử code mình post ở bài #15 nhé, xem có lọt điểm 3d nào trong vùng chọn ko?!

Ý mình là thế này - bạn trả lời câu hỏi này thì sẽ hiểu:

Bạn phân ra được 2 vùng chọn >>> bạn xữ lý tiếp thế nào ?!

(ko phải là ko chọn được 3d point nhưng chỉ 1 phương 2d thì ko phản ánh đúng thực chất của 3d)


  • 0

Có vợ dù dữ dù hiền , bạn đều có lợi
_ Nếu vợ hiền, bạn sẽ là người đàn ông sung sướng
_ Nếu vợ dữ, bạn sẽ thành ... triết gia !

Bergson


#19 Skywings

Skywings

    biết lệnh erase

  • Members
  • PipPipPip
  • 102 Bài viết
Điểm đánh giá: 46 (tàm tạm)

Đã gửi 16 September 2013 - 02:48 PM

Ý mình là thế này - bạn trả lời câu hỏi này thì sẽ hiểu:

Bạn phân ra được 2 vùng chọn >>> bạn xữ lý tiếp thế nào ?!

Bạn đọc bài số #3 của bác phamthanhbinh í. Còn nếu bạn vẫn chưa hiểu, chờ bác Bình giải thích nhé!


  • 0

#20 hiepttr

hiepttr

    Edu level: li10

  • Members
  • PipPipPipPipPipPipPip
  • 1298 Bài viết
Điểm đánh giá: 518 (tốt)

Đã gửi 16 September 2013 - 03:06 PM

bạn suy nghĩ vấn đề này tức đã hiểu mình nói gì mà !

Bạn chỉ dựa vào x, y để chọn hoặc bỏ qua 1 vùng xét ???

Chưa nói đến tâm của vùng thì không quyết định k/c của 1 điểm riêng biệt thuộc vùng đến điểm đang xét !


  • 1

Có vợ dù dữ dù hiền , bạn đều có lợi
_ Nếu vợ hiền, bạn sẽ là người đàn ông sung sướng
_ Nếu vợ dữ, bạn sẽ thành ... triết gia !

Bergson