(XD::Pnts:RemoveDup)点表消除重复点

守仁格竹GM

st788796 发表于 2013-11-14 12:41
不排序，4W长表可能CAD OVER

原始数据总数：64128  除去重复结果1503
按我发帖的办法处理6万多点，13秒多一点
按照先排序再删除0.5秒
下面为E大函数。0.5秒，效果明显
(defun Pnts:RemoveDups (pts fuzz / ptl)
  (setq pts (vl-sort pts
       '(lambda (p1 p2)
   (if (= (car p1) (car p2))
     (< (cadr p1) (cadr p2))
     (< (car p1) (car p2))
   )
        )
       )
ptl (cons (car pts) ptl)
pts (cdr pts)
)
  (while pts
    (if (equal (car pts) (car ptl) fuzz)
      nil
      (setq ptl (cons (car pts) ptl))
    )
    (setq pts (cdr pts))
  )
  ptl
)

st788796

守仁格竹GM 发表于 2013-11-14 14:03
原始数据总数：64128  除去重复结果1503
按我发帖的办法处理6万多点，13秒多一点
按照先排序再删除0.5 ...

这个排序会有遗漏的
把if = 换成 if equal fuzz

ll_j

守仁格竹GM 发表于 2013-11-14 14:03
原始数据总数：64128  除去重复结果1503
按我发帖的办法处理6万多点，13秒多一点
按照先排序再删除0.5 ...

这个函数有两点遗漏，第一是函数中删除只考虑X相同，没有考虑Y相同，会多删；第二是删除后改变了次序，应该像G版那样，先附加一个序号，然后排序删除后再恢复次序。

ll_j

st788796 发表于 2013-11-14 14:22
这个排序会有遗漏的
把if = 换成 if equal fuzz

我的观点是，排序不要误差，删除时再使用误差，否则就像我那个“间苗”的帖子一样。

st788796

对点而言这个误差就是以基点为圆心，误差为半径，凡圆内及圆上点均认为是equal

守仁格竹GM

ll_j 发表于 2013-11-14 14:31
这个函数有两点遗漏，第一是函数中删除只考虑X相同，没有考虑Y相同，会多删；第二是删除后改变了次序，应 ...

这是排序的一种 并没有遗漏 ，大方向按X，X相同时候按照Y ，这个只是给删除重复点使用，要是纯排序 有多个排序的方案
改变次序 是一个缺陷

ll_j

st788796 发表于 2013-11-14 14:40
对点而言这个误差就是以基点为圆心，误差为半径，凡圆内及圆上点均认为是equal

这种情况的排序不应该是按XY排序，而是按点之间的相互距离来排序，严格地说，在这种情况下，排序就不是一个好办法，也许回到最基本的“遍历”才可以解决这种问题，不过效率又要让人担忧了。

守仁格竹GM

st788796 发表于 2013-11-14 14:22
这个排序会有遗漏的
把if = 换成 if equal fuzz

应该不会有遗漏，都是按照默认精度排序的，最后的精度删除 不能过于粗糙，要是粗糙的离谱 肯定会有遗漏，按照正常人的逻辑思维 不应该有问题

newer

守仁格竹GM 发表于 2013-11-14 12:20
vl-sort 排序应该是 1+2+3+...+(n-1) 这个是最差的情况，再加上最后的相邻相同元素删除 次数也是n 所以 ...

你的测试结果，证明了我说的算法的效率判断。

你的代码，不管是怎么递减，也是两个表在循环，一个表里面哪怕多增加一个元素，整个就多耗费表1整个长度的次数。所以整体上是你N方等级的。何况增加的要很多。

而先排序不同，VL-SORT 整体是N级的，你多加两个类似VL-SORT这样的MAPCAR，也就顶多增加了2次的N而已。在样本数很大的情况下，这个是忽略不计的。

好的代码，应该个大的循环调用，函数调用都控制在N级。这样整体效率才保证。

(while (cdr lst)
    (vl-remove-if '.......)
)

这样的结构是N方的结构。VL-REMOVE-IF本身也是一个循环。

newer

守仁格竹GM 发表于 2013-11-14 14:52
应该不会有遗漏，都是按照默认精度排序的，最后的精度删除 不能过于粗糙，要是粗糙的离谱 肯定会有遗漏， ...

同意，给精度完全是一种适应多情况的技巧，可以给0不就完了，有人总纠结在这细节里面出不来，看不到整体上应该怎么写才更好。

守仁格竹GM

newer 发表于 2013-11-14 15:19
同意，给精度完全是一种适应多情况的技巧，可以给0不就完了，有人总纠结在这细节里面出不来，看不到整体 ...

顺序不打乱的情况 同样上面数据  1.3730秒
(defun Pnts:RemoveDups (pts fuzz / ptsi ptsi_con_lst ptl)
  (setq ptsi (vl-sort-i pts
       '(lambda (p1 p2)
   (if (= (car p1) (car p2))
     (< (cadr p1) (cadr p2))
     (< (car p1) (car p2))
   )
        )
     )
pts (vl-sort pts
       '(lambda (p1 p2)
   (if (= (car p1) (car p2))
     (< (cadr p1) (cadr p2))
     (< (car p1) (car p2))
   )
        )
       )
  )
  (setq ptsi_con_lst (mapcar '(lambda (x y) (cons x y)) ptsi pts)
ptl (cons (car ptsi_con_lst) ptl)
ptsi_con_lst (cdr ptsi_con_lst)
)
  (while ptsi_con_lst
    (if (equal (cdar ptsi_con_lst) (cdar ptl) fuzz)
      nil
      (setq ptl (cons (car ptsi_con_lst) ptl))
    )
    (setq ptsi_con_lst (cdr ptsi_con_lst))
  )
  (mapcar 'cdr (vl-sort ptl '(lambda (p1 p2) (< (car p1) (car p2)))))
)

守仁格竹GM

ll_j 发表于 2013-11-14 14:31
这个函数有两点遗漏，第一是函数中删除只考虑X相同，没有考虑Y相同，会多删；第二是删除后改变了次序，应 ...

{:soso_e113:} 再看看 刚发的帖 删除完 顺序不改变，效率下降了1倍 不过也能接受

守仁格竹GM

实际上 上面的操作 只是单方面的，实际操作中还是得按照每个程序具体操作。
很多时候 都是提前排序处理完毕了， 这样再排序我觉得意义不大了。
E大的分段处理理念 效率其实挺高的

守仁格竹GM

我那个有点啰嗦了 刚发现 G版的意思一样，效率更高 0.9200秒

守仁格竹GM

:lol 不过我又改进了一下0.8740秒
(defun Pnts:RemoveDups (pts fuzz / i ptl)
  (setq i -1
        pts (mapcar '(lambda (X) (cons (setq i (1+ i)) x)) pts)
        pts (vl-sort pts
                     '(lambda (p1 p2)
                        (if (= (cadr p1) (cadr p2))
                          (< (caddr p1) (caddr p2))
                          (< (cadr p1) (cadr p2))
                        )
                      )
            )
        ptl (cons (car pts) ptl)
        pts (cdr pts)
  )
  (while pts
    (if (equal (cdar pts) (cdar ptl) fuzz)
      nil
      (setq ptl (cons (car pts) ptl))
    )
    (setq pts (cdr pts))
  )
  (mapcar 'cdr (vl-sort ptl '(lambda (p1 p2) (< (car p1) (car p2)))))
)