Chuyển đến nội dung
Diễn đàn CADViet
  • Thông báo

    • Nguyen Hoanh

      CADViet đã hoàn tất nâng cấp   14/09/2017

      Chào các bạn, CADViet đã hoàn tất việc nâng cấp lên phiên bản mới. Tất cả các chức năng đã hoạt động theo kỳ vọng của ban quản trị. Nếu có vấn đề gì cần phản hồi, các bản post ở đây nhé: Trân trọng, Nguyễn Hoành.
Đăng nhập để thực hiện theo  
Doan Van Ha

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

Các bài được khuyến nghị

Skywings    46

(ssget "_C" p1 p2) chỉ chọn được đối tượng point nằm trên p1, p2 mà thôi......

Bác đã test chưa!? Mình test vẫn chọn được điểm với Z>=0 hay Z<0 :) !!

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Tue_NV    3.841

Bác đã test chưa!? Mình test vẫn chọn được điểm với Z>=0 hay Z<0 :) !!

 

Đã test rồi, test hồi hôm qua cơ, rồi mới hồi âm ngay từ bài viết thứ 2 (bài viết của bác Bình)

 

P/S : Tìm ra rồi, do bạn test trên 2D, Tue_NV test trên không gian 3D. (SW Iso metric)

Và bài toán tổng quát là trong không gian -> nên phải test trên không gian 3D

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Skywings    46

Lạ nhỉ :huh: , mình vẫn chọn được, cho dù SW Iso metric hay một góc view 3D bất kỳ, SSGET với tham số "C" hoặc "W" vẫn chọn được tất cả điểm 3D trong vùng chọn của nó.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Doan Van Ha    2.678

Tôi test thì kết quả thế này: bất kể Z là gì, miễn nó nằm trong vùng chọn thì sẽ được chọn hết.

Đây là bản vẽ để test.

http://www.cadviet.com/upfiles/3/67029_test_select_3d.dwg

Bác Tue_NV test khác thì gởi bản vẽ ấy lên cho mọi người ngâm cứu với.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Tue_NV    3.841

Vậy là rõ rồi, nó phụ thuộc vào khung nhìn VIEW, trong view này thì chọn được, trong view kia thì không chọn được

Tỉ dụ : có 3 toạ độ: 0(0 0 0), A(0 20 0) , B (0 10 10)

Trong mp Oxy bạn chọn theo hàm ssget với tham số "c" điểm 0 và A thì chắc chắn điểm B được chọn

Nhưng trong không gian Oxyz  ssget với tham số "c" điểm 0 và A thì điểm B sẽ không được chọn nữa

Kiểu như trong file Bac HA, mình xoay khung nhìn (Orbit) đi thì cũng với 2 điểm chọn đó -> kết quả chọn sẽ khác liền.....

=> Nó phụ thuộc vào khung nhìn 

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Doan Van Ha    2.678

Vậy là rõ rồi, nó phụ thuộc vào khung nhìn VIEW, trong view này thì chọn được, trong view kia thì không chọn được

Tỉ dụ : có 3 toạ độ: 0(0 0 0), A(0 20 0) , B (0 10 10)

Trong mp Oxy bạn chọn theo hàm ssget với tham số "c" điểm 0 và A thì chắc chắn điểm B được chọn

Nhưng trong không gian Oxyz  ssget với tham số "c" điểm 0 và A thì điểm B sẽ không được chọn nữa

Kiểu như trong file Bac HA, mình xoay khung nhìn (Orbit) đi thì cũng với 2 điểm chọn đó -> kết quả chọn sẽ khác liền.....

=> Nó phụ thuộc vào khung nhìn 

Đỏ: khung này không tạo thành hình chữ nhật?

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Tue_NV    3.841

Đỏ: khung này không tạo thành hình chữ nhật?

 

Là 3 điểm trong không gian......

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Skywings    46

Mình thấy vấn đề này đã bắt đầu đi khá xa topic rùi. Mình và bác Hà chỉ muốn chứng minh là trong vùng chọn tạo bởi 2 điểm thì SSGET "C" có thể chọn được các điểm 3d, không nhất thiết phải là đồng phẳng hay nằm "trên" 2 điểm góc đó. Trường hợp file của bác Hà, với 2 điểm cố định, thì khi xoay view, vùng chọn có thể bị nhỏ đi và một số điểm lọt ra ngoài. Vấn đề xác định 2 điểm góc ứng với từng view để có thể bao hết các điểm đã là vấn đề khác.

 

Với Lisp của bác Bình mình test thử thấy chưa ổn định lắm, với 105000 điểm tạo ra từ lisp bác Gia_Bach, khi chọn điểm ở vùng góc trái dưới có trường hợp rơi vào vòng lặp vô hạn, và một số điểm cho kết quả không chính xác (điểm 2d).

  • Vote tăng 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
phamthanhbinh    3.123

Mình thấy vấn đề này đã bắt đầu đi khá xa topic rùi. Mình và bác Hà chỉ muốn chứng minh là trong vùng chọn tạo bởi 2 điểm thì SSGET "C" có thể chọn được các điểm 3d, không nhất thiết phải là đồng phẳng hay nằm "trên" 2 điểm góc đó. Trường hợp file của bác Hà, với 2 điểm cố định, thì khi xoay view, vùng chọn có thể bị nhỏ đi và một số điểm lọt ra ngoài. Vấn đề xác định 2 điểm góc ứng với từng view để có thể bao hết các điểm đã là vấn đề khác.

 

Với Lisp của bác Bình mình test thử thấy chưa ổn định lắm, với 105000 điểm tạo ra từ lisp bác Gia_Bach, khi chọn điểm ở vùng góc trái dưới có trường hợp rơi vào vòng lặp vô hạn, và một số điểm cho kết quả không chính xác (điểm 2d).

Hề hề hề,

Thực tình mình cũng chưa test hết các trường hợp. Song mình trộm nghĩ khả năng vòng lặp chạy vô hạn là rất ít bởi vùng chọn sẽ được thu hẹp dần và nhất định sẽ tới lúc vùng chọn không chứa điểm nào, tức là tập ss bằng nil.

Nếu vòng lặp chạy vô hạn tức có nghĩ là điểm cho trước trùng với một hay nhiều điểm trong tập hợp điểm này. Khi đó không cần xét cũng khẳng định được rằng khoảng cách nhỏ nhất sẽ là 0.

Về việc điểm tìm được chưa chính xác thì mình nghĩ là có nhẽ cách chọn vùng như của mình chưa hợp lý chăng???

Theo thiển ý của mình, nếu điểm cho trước nằm ngoài vùng chọn của tập hợp các điểm đã cho thì kết quả có thể chuẩn xác. Song nếu điểm cho trước nằm trong vùng chọn chứa tập hợp điểm này thì có nhẽ sẽ có sai số do việc lấy tập hợp điểm dể xét chưa phải là bao đủ góc 360 độ quanh điểm cho trước.

Như vậy nều ta thay đổi cách lấy vùng chọn có nhẽ sẽ cho kết quả chuẩn xác hơn.

Mình sẽ thử viết lại theo hướng này.

Mong các bác đèn giời soi xét.

Và đây là kết quả:

Với cùng một bản vẽ fun điểm từ lisp của bác giabach, nếu sử dụng lisp test của bác giabach thì thời gian sẽ hết khoảng 13.000ms Còn nếu sử dụng lisp dưới đây sẽ cho thời gian hết khoảng 1.000 ms và kết quả hầu như trùng nhau.

Các bác thử xem nhé.

http://www.cadviet.com/upfiles/3/5194_mindis_1.lsp

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
hiepttr    523

Mặc dù level lisp chủa mình vẫn còn rất thấp, nhưng mình mạo muội góp ý như thế này:

- Mình thấy cái lisp của bác Bình có thể cho kết quả sai trong trường hợp đặc biệt mình nêu sau:

Giã sử, điểm đầu tiên trong tập chọn ss là điểm B và tập ss gồm chỉ 2 điểm A & B (hình dưới)

>>> tập ss1 chỉ có B >>> PB được kẻ ra >>> sai

80156_abp.jpg

- Đề nghị bác một hướng như sau (vì level chưa đạt nên ko thể biến ý tưởng thành lisp đc, mong bác thông cảm)

+ Dùng vòng lặp + hàm polar ---> tạo polygon n cạnh >>> gần giống đường tròn, để tạo hàm ssget "CP" theo bán kính (ý tưởng bác Gia_bạch) Số cạnh có thể để người dùng tuỳ chọn hoặc là bác cân nhắc, tuỳ vào độ chính xác yêu cầu d_ trong hình (vì n lớn thì độ chính xác cao song lisp sẽ chạy chậm)

80156_p.jpg

+ Bán kính đầu tiên nhập vào có thể lấy bằng k/c từ p đến điểm đầu như Bác đã làm.

+ Để khắc phục cái nhược điểm bác đã nêu (khi điểm chọn đủ xa thì giường như ko loại đc điểm nào ra khỏi tập ss ban đầu)

có thể làm như sau:

* Với lần chon thứ nhất (R = k/c điểm đầu trong tập ss đến p):

1. Nếu sslength>0 >>> gán R = R/2,

2. Nếu sslength = 0 (thường chỉ xảy ra khi chọn sai số lớn & lọt vào trường hợp như hình dưới, khi điểm A là điểm đầu tiên trong tập ss & A nằm lệch vị trí các đỉnh của polygon chọn) ---> kết luận luôn điểm A gần nhất, thoát chương trình.

80156_a.jpg

* Với các lần chọn sau:

1. Nếu sslength>0 >>> gán R = R/2

2. Nếu sslength = 0 >>> gán R = (R + R last) / 2 .

Và nếu sau m lần lặp bán kính liên tục mà sslength của tập chọn >0 & ko đổi >>> kết thúc vòng lặp R (hoặc là ấn định bước nhảy min cho vòng lặp R để thoát khỏi vòng lặp)

>>>>>>>>>>lấy ss cuối để xét

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
phamthanhbinh    3.123

Mặc dù level lisp chủa mình vẫn còn rất thấp, nhưng mình mạo muội góp ý như thế này:

- Mình thấy cái lisp của bác Bình có thể cho kết quả sai trong trường hợp đặc biệt mình nêu sau:

Giã sử, điểm đầu tiên trong tập chọn ss là điểm B và tập ss gồm chỉ 2 điểm A & B (hình dưới)

>>> tập ss1 chỉ có B >>> PB được kẻ ra >>> sai

80156_abp.jpg

- Đề nghị bác một hướng như sau (vì level chưa đạt nên ko thể biến ý tưởng thành lisp đc, mong bác thông cảm)

+ Dùng vòng lặp + hàm polar ---> tạo polygon n cạnh >>> gần giống đường tròn, để tạo hàm ssget "CP" theo bán kính (ý tưởng bác Gia_bạch) Số cạnh có thể để người dùng tuỳ chọn hoặc là bác cân nhắc, tuỳ vào độ chính xác yêu cầu d_ trong hình (vì n lớn thì độ chính xác cao song lisp sẽ chạy chậm)

80156_huong.jpg

+ Bán kính đầu tiên nhập vào có thể lấy bằng k/c từ p đến điểm đầu như Bác đã làm.

+ Để khắc phục cái nhược điểm bác đã nêu (khi điểm chọn đủ xa thì giường như ko loại đc điểm nào ra khỏi tập ss ban đầu)

có thể làm như sau:

* Với lần chon thứ nhất (R = k/c điểm đầu trong tập ss đến p):

1. Nếu sslength>0 >>> gán R = R/2,

2. Nếu sslength = 0 (thường chỉ xảy ra khi chọn sai số lớn & lọt vào trường hợp như hình dưới, khi điểm A là điểm đầu tiên trong tập ss & A nằm lệch vị trí các đỉnh của polygon chọn) ---> kết luận luôn điểm A gần nhất, thoát chương trình.

80156_111.jpg

* Với các lần chọn sau:

1. Nếu sslength>0 >>> gán R = R/2

2. Nếu sslength = 0 >>> gán R = (R + R last) / 2 .

Và nếu sau m lần lặp bán kính liên tục mà sslength của tập chọn >0 & ko đổi >>> kết thúc vòng lặp R (hoặc là ấn định bước nhảy min cho vòng lặp R để thoát khỏi vòng lặp)

>>>>>>>>>>lấy ss cuối để xét

Hề hề hề,

Rất tiếc là không nhìn thấy cái hình vẽ của bác, nên mình cũng chưa hình dung ra lỗi. Bởi vì theo mình nghĩ thì trong ví dụ bác đưa ra khi Kc PB > PA. Như vậy với việc chọn tập SS dựa trên vùng chọn là một hình vuông có tâm là p thì rõ ràng điểm A phải xuất hiện ngay trong tập ss ở bước lặp đầu tiên rồi. Sang  bước lặp thứ hai giả sử điểm A không năm trong tập ss mới tức là tập ss là nil. Khi đó ta phải xét khoảng cách PA và PB vì tập ss1 lúc này có hai phần tử cơ mà.

vậy thì sẽ không có chuyện lisp sẽ nối ngay PB được.

Có thể mình chưa hiểu rõ ý bác song mình cứ suy luận mò như vậy. trúng trất mong bác chỉ rõ thêm.....

Còn về góp ý của bác, mình nghĩ kết quả có nhẽ không khác bao nhiêu vì cái vùng chọn hình vuông của mình lớn hơn cái vùng chọn là polygon hay thậm chì là hình tròn bán kính PB bác ạ. Bởi cái hình tròn này là nội tiếp trong hình vuông mà mình dùng để chọn. Hình vuông này có tâm là P và mỗi cạnh dài là 2d bác ạ.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
anhcos    177

Góp vui với các bác một tí:

Capture1-1_zps242ce447.png

Bộ này dù rất cũ nhưng thông tin thì còn nhiều thứ phải học, link tải ở đây.

Nhờ có mấy bác mà mình mới lục lại 2 quyển sách này, bỏ xó em nó lâu quá rồi, giờ mới thấy có nhiều thứ mình phải đọc lại...

 

@DVH: tập 1 có nói về thuật toán tìm kiếm nhị phân đó.

  • Vote tăng 6

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
hiepttr    523

@Bác PTB: Srr, mình nhầm :D .

Ah, còn cái đề nghị khi length ss1 = 0 thì chọn ra ngoài như ý của mình thì sao ?! Có dùng đc ko ?

  • Vote giảm 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
phamthanhbinh    3.123

@Bác PTB: Srr, mình nhầm :D .

Ah, còn cái đề nghị khi length ss1 = 0 thì chọn ra ngoài như ý của mình thì sao ?! Có dùng đc ko ?

Hề hề hề,

Sorry bác, mình kích nhầm nút trừ mất rồi, chả biết phục hồi thế nào nữa.

Vì mình sử dụng hàm ssget với tham số "c" nên chắc chắn lần đầu tiên của vòng lặp sẽ khó có chuyện nó là nil bác ạ  Còn nếu (sslength ss) là 1 thì chắc chắn bước lặp thứ 2 sẽ là 0 và ta chỉ cần lấy 1 khoảng cách để mà so sánh thôi và kết quả sẽ ra là duy nhất.

Do tập ss1 luôn là tập ss chứa các điểm cuối cùng trước khi tập này trở thành nil ở bước lặp cuối nên tập ss1 không thể có (sslength ss1) = 0 được bác ạ.

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
hiepttr    523

ý mình là khi tập ss nil, bác có thể chưa vội gán ss1 = ss last mà bác hãy cho nó mở rộng vùng chọn ra ngoài với phạm vi bằng 1/2 tổng vùng chọn ss ko nil & vùng chọn nil

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Doan Van Ha    2.678

@anhcos: thank bạn cho 2 cuốn sách. Về "tìm kiếm nhị phân" thì ngay hôm đó mình đã tìm đọc và đã hiểu. Tuy nhiên, phương pháp này chỉ áp dụng cho tập đã sắp xếp.

@PTB:

1). Bác phải bổ sung thêm trường hợp: khi d=0 thì dừng ngay, không lặp liếc gì hết, chứ nếu không nó sẽ thiên thu.

2). Rất khó có thể nói là lisp của bác hay của bác Gia_bach nhanh hơn, bởi lisp của bác mang tính "hên xui" nhiều. Ngộ nhỡ 100.000 points nằm ở Bình Dương, còn point (ssname ss 0) nó nằm ở Hoa Kỳ >> khi đó không máy tính nào chịu nỗi!

3). Những bài toán tốc độ cần phải mang tính ổn định, chứ không nên nhanh chậm tùy thuộc cơ may >> giải pháp thu hẹp hoặc nới rộng vùng chọn sau từng lần xem ra không khả thi lắm, bởi khi tập chọn đủ lớn thì việc phải chọn đối tượng nhiều lần cũng làm chậm quá trình xử lý đáng kể.

  • Vote tăng 1

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
phamthanhbinh    3.123

@anhcos: thank bạn cho 2 cuốn sách. Về "tìm kiếm nhị phân" thì ngay hôm đó mình đã tìm đọc và đã hiểu. Tuy nhiên, phương pháp này chỉ áp dụng cho tập đã sắp xếp.

@PTB:

1). Bác phải bổ sung thêm trường hợp: khi d=0 thì dừng ngay, không lặp liếc gì hết, chứ nếu không nó sẽ thiên thu.

2). Rất khó có thể nói là lisp của bác hay của bác Gia_bach nhanh hơn, bởi lisp của bác mang tính "hên xui" nhiều. Ngộ nhỡ 100.000 points nằm ở Bình Dương, còn point (ssname ss 0) nó nằm ở Hoa Kỳ >> khi đó không máy tính nào chịu nỗi!

3). Những bài toán tốc độ cần phải mang tính ổn định, chứ không nên nhanh chậm tùy thuộc cơ may >> giải pháp thu hẹp hoặc nới rộng vùng chọn sau từng lần xem ra không khả thi lắm, bởi khi tập chọn đủ lớn thì việc phải chọn đối tượng nhiều lần cũng làm chậm quá trình xử lý đáng kể.

Hề hề hề,

1/- Thank bác phát hiện ra lỗi này vì mình cũng không xét đến nó.

2/- Thực ra mình nghĩ bài toán nào cũng có giới hạn sử dụng của nó. Ví như không thể dùng nguyên lý đòn bẩy của Asimet để bẩy trái đấy này đi..... Đúng là với vì dụ bác đưa ra thì khó có máy tính nào chạy theo kịp. Song nếu giả thiết rằng cái điểm cho trước nằm ở ngay rốn tượng nữ thần tự do thì có nhẽ cũng sẽ có kết quả sau khoảng vài năm bác nhể. Vì phạm vi tư duy của mình có giới hạn nên không thể nghĩ tới những điều quá to. Mình chỉ cố gắng theo khả năng thôi chứ cố quá nhiều khi sụm bã chè mất.

3/- Có nhẽ cách nghĩ của mình chưa hợp lý nên chưa thể có được giải pháp tối ưu. Đành chờ mọi người làm để mót vậy.....

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
Doan Van Ha    2.678

Chúng ta tạm gác “Bài toán số 1” ở đây, với 2 thuật toán khá tốt:

1). Của Skywings: phù hợp trong trường hợp tổng quát, sự phân bố điểm là ngẫu nhiên.

2). Của Phamthanhbinh: phù hợp trong trường hợp sự phân bố điểm tập trung, không có những điểm nằm quá xa trọng tâm của chúng.

Rất có thể sẽ có thuật toán thứ 3, tốt hơn? Đang chờ!

 

Bài toán số 2:

Mời các bạn tiếp tục đưa ra giải thuật cho bài toán này:

Cho tập N điểm trên mặt phẳng.

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

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác
phamthanhbinh    3.123

Chúng ta tạm gác “Bài toán số 1” ở đây, với 2 thuật toán khá tốt:

1). Của Skywings: phù hợp trong trường hợp tổng quát, sự phân bố điểm là ngẫu nhiên.

2). Của Phamthanhbinh: phù hợp trong trường hợp sự phân bố điểm tập trung, không có những điểm nằm quá xa trọng tâm của chúng.

Rất có thể sẽ có thuật toán thứ 3, tốt hơn? Đang chờ!

 

Bài toán số 2:

Mời các bạn tiếp tục đưa ra giải thuật cho bài toán này:

Cho tập N điểm trên mặt phẳng.

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

Hề hề hề,

Hình như cái này có trong tài liệu về các thuật toán của bác anhcos gửi thì phải....

Chia sẻ bài đăng này


Liên kết tới bài đăng
Chia sẻ trên các trang web khác

Tạo một tài khoản hoặc đăng nhập để nhận xét

Bạn cần phải là một thành viên để lại một bình luận

Tạo tài khoản

Đăng ký một tài khoản mới trong cộng đồng của chúng tôi. Điều đó dễ mà.

Đăng ký tài khoản mới

Đăng nhập

Bạn có sẵn sàng để tạo một tài khoản ? Đăng nhập tại đây.

Đăng nhập ngay

Đăng nhập để thực hiện theo  

×