明经CAD社区

 找回密码
 注册

QQ登录

只需一步,快速开始

搜索
12
返回列表 发新帖
楼主: peraperson

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

[复制链接]
发表于 2015-1-30 11:32 | 显示全部楼层
vectra 发表于 2015-1-29 19:44
无序的两个循环时间复杂度是O(n^2),排序之后,两个表均循环一次即可,时间复杂度是O(n)

我觉得跟排序没有关系
这个问题应该就是一个文字集合里面的每个文字对一个线段中点集合求distance 找出<10的来
“每个文字” “每个线段”
就是2个repeat
发表于 2015-1-30 11:33 | 显示全部楼层
longcashman 发表于 2015-1-30 11:29
这个法子只能判定附近有线但不一定是在中点附近的

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

的确 计算量小了很多
  1. (defun getlinemidptlst (enlst / ent)
  2.   (mapcar '(lambda (en)
  3.              (setq
  4.                ent (entget en)
  5.              )
  6.              (mapcar
  7.                '(lambda        (x y)
  8.                   (* 0.5
  9.                      (+ x y)
  10.                   )
  11.                 )
  12.                (cdr
  13.                  (assoc 10 ent)
  14.                )
  15.                (cdr
  16.                  (assoc 11 ent)
  17.                )
  18.              )
  19.            )
  20.           enlst
  21.   )
  22. );中点表
  23. (defun ss->lst (ss / i enlst)
  24.   (setq i 0)
  25.   (repeat (sslength ss)
  26.     (setq enlst (cons (ssname ss i) enlst))
  27.     (setq i (1+ i))
  28.   )
  29.   enlst
  30. );选择集到表
  31. (defun cc ()
  32.   (setq txtenlst (ss->lst (ssget '((0 . "TEXT")))))
  33.   (setq        textptlst (mapcar '(lambda (en) (cdr (assoc 10 (entget en))))
  34.                           txtenlst
  35.                   )
  36.   )
  37.   (setq        windowlst (mapcar '(lambda (pt)
  38.                              (list (polar pt (* 2 pi) 300)
  39.                                    (polar pt (* 0.5 pi) 300)
  40.                              )
  41.                            )
  42.                           textptlst
  43.                   )
  44.   )

  45.   (repeat (length txtenlst)
  46.     (if        (setq
  47.           ss (ssget "_C" (car (car windowlst)) (cadr (car windowlst)))
  48.         )
  49.       (progn
  50.         (setq midptlst (getlinemidptlst (ss->lst ss)));选择到的直线取中点表
  51.         (foreach midpt midptlst
  52.           (if midpt
  53.             (if        (< 300. (distance midpt (car textptlst)));直线中点与文字插入点的距离
  54.               (vla-put-color (vlax-ename->vla-object (car txtenlst)) 1)
  55.             )
  56.           )
  57.         )
  58.       )
  59.     )
  60.     (setq textptlst (cdr textptlst))
  61.     (setq txtenlst (cdr txtenlst))
  62.     (setq windowlst (cdr windowlst))
  63.   )
  64. )

















发表于 2015-1-30 21:38 | 显示全部楼层
本帖最后由 vectra 于 2015-1-31 20:00 编辑

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

http://bbs.mjtd.com/thread-112925-1-1.html
发表于 2015-2-1 11:03 | 显示全部楼层
vectra 发表于 2015-1-30 21:38
代码实现及评测结果请移步

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

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

本版积分规则

小黑屋|手机版|CAD论坛|CAD教程|CAD下载|联系我们|关于明经|明经通道 ( 粤ICP备05003914号 )  
©2000-2023 明经通道 版权所有 本站代码,在未取得本站及作者授权的情况下,不得用于商业用途

GMT+8, 2024-3-29 00:16 , Processed in 0.142297 second(s), 18 queries , Gzip On.

Powered by Discuz! X3.4

Copyright © 2001-2021, Tencent Cloud.

快速回复 返回顶部 返回列表