[循环套循环]请问如何优化这个算法

longcashman

vectra 发表于 2015-1-29 19:44
无序的两个循环时间复杂度是O(n^2)，排序之后，两个表均循环一次即可，时间复杂度是O（n）

我觉得跟排序没有关系
这个问题应该就是一个文字集合里面的每个文字对一个线段中点集合求distance 找出<10的来
“每个文字” “每个线段”
就是2个repeat

llsheng_73

longcashman 发表于 2015-1-30 11:29
这个法子只能判定附近有线但不一定是在中点附近的

一是选出来进一步用线的中点进行排除，二是还按原来的办法，不断变小第二层循环所涉及的表

longcashman

llsheng_73 发表于 2015-1-30 11:33
一是选出来进一步用线的中点进行排除，二是还按原来的办法，不断变小第二层循环所涉及的表

的确 计算量小了很多

2. (defun getlinemidptlst (enlst / ent)
   
3.   (mapcar '(lambda (en)
   
4.              (setq
   
5.                ent (entget en)
   
6.              )
   
7.              (mapcar
   
8.                '(lambda        (x y)
   
9.                   (* 0.5
   
10.                      (+ x y)
    
11.                   )
    
12.                 )
    
13.                (cdr
    
14.                  (assoc 10 ent)
    
15.                )
    
16.                (cdr
    
17.                  (assoc 11 ent)
    
18.                )
    
19.              )
    
20.            )
    
21.           enlst
    
22.   )
    
23. );中点表
    
24. (defun ss->lst (ss / i enlst)
    
25.   (setq i 0)
    
26.   (repeat (sslength ss)
    
27.     (setq enlst (cons (ssname ss i) enlst))
    
28.     (setq i (1+ i))
    
29.   )
    
30.   enlst
    
31. );选择集到表
    
32. (defun cc ()
    
33.   (setq txtenlst (ss->lst (ssget '((0 . "TEXT")))))
    
34.   (setq        textptlst (mapcar '(lambda (en) (cdr (assoc 10 (entget en))))
    
35.                           txtenlst
    
36.                   )
    
37.   )
    
38.   (setq        windowlst (mapcar '(lambda (pt)
    
39.                              (list (polar pt (* 2 pi) 300)
    
40.                                    (polar pt (* 0.5 pi) 300)
    
41.                              )
    
42.                            )
    
43.                           textptlst
    
44.                   )
    
45.   )
    
46. 
    
47.   (repeat (length txtenlst)
    
48.     (if        (setq
    
49.           ss (ssget "_C" (car (car windowlst)) (cadr (car windowlst)))
    
50.         )
    
51.       (progn
    
52.         (setq midptlst (getlinemidptlst (ss->lst ss)));选择到的直线取中点表
    
53.         (foreach midpt midptlst
    
54.           (if midpt
    
55.             (if        (< 300. (distance midpt (car textptlst)));直线中点与文字插入点的距离
    
56.               (vla-put-color (vlax-ename->vla-object (car txtenlst)) 1)
    
57.             )
    
58.           )
    
59.         )
    
60.       )
    
61.     )
    
62.     (setq textptlst (cdr textptlst))
    
63.     (setq txtenlst (cdr txtenlst))
    
64.     (setq windowlst (cdr windowlst))
    
65.   )
    
66. )
    
67. 
    
68. 
    
69. 
    
70. 
    
71. 
    
72. 
    
73. 
    
74. 
    
75. 
    
76. 
    
77. 
    
78. 
    
79. 
    
80. 
    
81. 
    
82. 
    
83. 
    

(defun getlinemidptlst (enlst / ent)<br />   (mapcar '(lambda (en)<br />              (setq<br />                ent (entget en)<br />              )<br />              (mapcar<br />                '(lambda        (x y)<br />                   (* 0.5<br />                      (+ x y)<br />                   )<br />                 )<br />                (cdr<br />                  (assoc 10 ent)<br />                )<br />                (cdr<br />                  (assoc 11 ent)<br />                )<br />              )<br />            )<br />           enlst<br />   )<br /> );中点表<br /> (defun ss->lst (ss / i enlst)<br />   (setq i 0)<br />   (repeat (sslength ss)<br />     (setq enlst (cons (ssname ss i) enlst))<br />     (setq i (1+ i))<br />   )<br />   enlst<br /> );选择集到表<br /> (defun cc ()<br />   (setq txtenlst (ss->lst (ssget '((0 . "TEXT")))))<br />   (setq        textptlst (mapcar '(lambda (en) (cdr (assoc 10 (entget en))))<br />                           txtenlst<br />                   )<br />   )<br />   (setq        windowlst (mapcar '(lambda (pt)<br />                              (list (polar pt (* 2 pi) 300)<br />                                    (polar pt (* 0.5 pi) 300)<br />                              )<br />                            )<br />                           textptlst<br />                   )<br />   )<br /> <br />   (repeat (length txtenlst)<br />     (if        (setq<br />           ss (ssget "_C" (car (car windowlst)) (cadr (car windowlst)))<br />         )<br />       (progn<br />         (setq midptlst (getlinemidptlst (ss->lst ss)));选择到的直线取中点表<br />         (foreach midpt midptlst<br />           (if midpt<br />             (if        (< 300. (distance midpt (car textptlst)));直线中点与文字插入点的距离<br />               (vla-put-color (vlax-ename->vla-object (car txtenlst)) 1)<br />             )<br />           )<br />         )<br />       )<br />     )<br />     (setq textptlst (cdr textptlst))<br />     (setq txtenlst (cdr txtenlst))<br />     (setq windowlst (cdr windowlst))<br />   )<br /> )<br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br /> <br />

vectra

代码实现及评测结果请移步

http://bbs.mjtd.com/thread-112925-1-1.html

longcashman

vectra 发表于 2015-1-30 21:38
代码实现及评测结果请移步

http://bbs.mjtd.com/thread-112925-1-1.html

分治策略的确比双repeat效率高，原理是让一个点跟某个范围而不是全部的点进行比较。但是分治有合理确定分治范围的问题，而且在实际图纸中应该是ssget得到的周边点范围更小。就是不知道综合时间哪个更快。
直觉上字少线多应该ssget更快。
有时间再验证下。
不管怎么说你都是高手！