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

ll_j · 发表于 2013-11-14 09:45:02

newer 发表于 2013-11-14 08:27
vl-remove-if这个函数要遍历整个表的，所以这个算法的时间效率上应该是N平方级的

不管用什么方法。排序也好，计算重复也好，删除重复也好，总归都是要遍历整个表的。
先排序可以避免重复遍历，使用向前判别迭代对于已经排序的表不需要遍历，但避免重复遍历的代价就是代码稍繁琐。
不研究API，所以不知道晓东用了什么函数来排序，但不管如何，遍历是少不了的。
使用vl函数在对效率要求不算很严苛的时候是有优点的，可以使得代码很简洁，也很易懂，当然，效率也不至于差到不能容忍的地步。

newer · 发表于 2013-11-14 10:10:03

ll_j 发表于 2013-11-14 09:45
不管用什么方法。排序也好，计算重复也好，删除重复也好，总归都是要遍历整个表的。
先排序可以避免重复 ...

不是代码简洁不简洁的事，而是算法本身设计的事，
前提，一个VL-REMOVE是肯定不能删除所有重复的，不好的算法，即使有长有短，数量级上也是要遍历表N*N次

举个例子：

100个点，可能最坏程序要执行100X100=10000次

假设其中就10个不同的点，遍历100个点，排好序，那么你只需执行10次操作就删除了所有的重复点，

整个算法执行了100+10=110次。

要是1000个点，就是1010 个VL-REMOVE 对 1百万个vl-remove的差别，越大差别越大，平方关系。

牢固 · 发表于 2013-11-14 10:12:16

本帖最后由牢固于 2013-11-14 10:16 编辑

一般点表除重点后，要求不打乱点表的顺序，如果打乱了原表的顺序，似乎就没什么实际意义！加载11.9号的API和XD-LISP-LIB.VLX后，函数库缺少XD::UCS:CoordSys函数，无法测试，不知道老大提供的这个除重函数是否能保留原点表的顺序！
下面是我的点表除重函数，先利用排序，减少循环次数，算法是N次的！除重后还要恢复点表顺序！

(defun gxl-ListDumpPoint (pl Fuzz / l n i)
(setq i -1
pl (mapcar '(lambda (X) (list x (setq i (1+ i)))) pl)
pl
(vl-sort
pl
'(lambda (a b)
(if (equal (caar a) (caar b) fuzz)
(< (cadar a) (cadar b))
(< (caar a) (caar b))
)
)
)
)
(while pl
(setq l (cons (setq n (car pl)) l)
pl (cdr pl)
)
(while (and pl (equal (car n) (caar pl) fuzz))
(setq pl (cdr pl))
)
)
(mapcar
'car
(vl-sort
l
'(lambda (a b)
(< (cadr a) (cadr b))
)
)
)
)

newer · 发表于 2013-11-14 10:17:10

牢固发表于 2013-11-14 10:12
一般点表除重点后，要求不打乱点表的顺序，如果打乱了原表的顺序，似乎就没什么实际意义！加载11.9号的API ...

http://bbs.xdcad.net/thread-671606-1-1.html

和这个思路差不多。

ll_j · 发表于 2013-11-14 10:31:10

newer 发表于 2013-11-14 10:10
不是代码简洁不简洁的事，而是算法本身设计的事，
前提，一个VL-REMOVE是肯定不能删除所有重复的，不好 ...

太过计较算法，其实并不那么可怕。
首先，排序本身就需要多次遍历（可能是不完全遍历），不管怎样的排序算法，这一步都是少不了的，于是，你的110次中的100次本身就是站不住脚的。其次，vl-remove方法，遍历次数并不是100×100，而是100＋99＋98＋...。这两项加起来，就看出差距并不那么大了吧？
表除重后再恢复次序，还需要再一次排序，差别就更小了。

守仁格竹GM · 发表于 2013-11-14 11:04:23

newer 发表于 2013-11-14 10:10
不是代码简洁不简洁的事，而是算法本身设计的事，
前提，一个VL-REMOVE是肯定不能删除所有重复的，不好 ...

我列的哪个 lst 是逐渐的递减的不是 n平方的关系

newer · 发表于 2013-11-14 11:07:18

守仁格竹GM 发表于 2013-11-14 11:04
我列的哪个 lst 是逐渐的递减的不是 n平方的关系

级别上是N的平方，不管你递减的，随着数量级的增加，还是平方的级别往上增加。

newer · 发表于 2013-11-14 11:10:26

ll_j 发表于 2013-11-14 10:31
太过计较算法，其实并不那么可怕。
首先，排序本身就需要多次遍历（可能是不完全遍历），不管怎样的排序 ...

不管是递减多少，随着样本点的数量级的增加，都是平方级的增加，因为算法两两的比较。

排序后，不管数量级如何增加，也能固定控制在几个N的范围，是N的级别，差别是天上地下。

讨论这么多，不是讨论VL函数效率如何，是讨论VL函数放在代码结构里面，这个结构的效率如何。

ll_j · 发表于 2013-11-14 11:24:35

newer 发表于 2013-11-14 11:10
不管是递减多少，随着样本点的数量级的增加，都是平方级的增加，因为算法两两的比较。

排序后，不管数 ...

你这样说就简单了，不考虑vl的效率，只考虑自己代码的效率，那么，还讨论什么vl-remove的不好呢，如果vl-remove使用的不是遍历，而是“摘取”，那么，使用vl-remove的效率也就谈不上不好了。
你所说的两两比较，这是最老的办法，这是在已经排序的基础上的，这种基础是怎么来的呢？相信基本的max函数和min函数也是需要遍历，而且有理由相信，自己使用min函数来“排序”，效率不会比vl的排序效率更高。
我的看法是，追求算法，但不要严苛于算法，或许不算最佳的算法在某种情况下却是最优的。

newer · 发表于 2013-11-14 11:34:00

ll_j 发表于 2013-11-14 11:24
你这样说就简单了，不考虑vl的效率，只考虑自己代码的效率，那么，还讨论什么vl-remove的不好呢，如果vl- ...

VL-REMOVE是整个循环代码里面的一行，现在讨论是你的代码要执行N平方级别次数的VL-REMOVE,还是执行N级别次数的VL-REMOVE的问题。

通俗说，是执行几十万次REMOVE还是几千次的差别，这个和VL-REMOVE无关。排序，VL-SORT肯定是N级别的。

做前，一定要先VL-SORT。

ll_j · 发表于 2013-11-14 11:55:51

newer 发表于 2013-11-14 11:34
VL-REMOVE是整个循环代码里面的一行，现在讨论是你的代码要执行N平方级别次数的VL-REMOVE,还是执行N级别 ...

排序的vl-sort肯定不是N基本的，不管怎样的排序算法。
吃饭了，不说了。{:soso_e100:}

newer · 发表于 2013-11-14 12:03:38

ll_j 发表于 2013-11-14 11:55
排序的vl-sort肯定不是N基本的，不管怎样的排序算法。
吃饭了，不说了。

快速排序是N*LOG(N)，这个就是大家都说的“N”，比N方要差一个级别。样本数越大差别越大。

守仁格竹GM · 发表于 2013-11-14 12:20:40

本帖最后由守仁格竹GM 于 2013-11-14 13:01 编辑

newer 发表于 2013-11-14 12:03
快速排序是N*LOG(N)，这个就是大家都说的“N”，比N方要差一个级别。样本数越大差别越大。

vl-sort 排序应该是 1+2+3+...+(n-1) 这个是最差的情况，再加上最后的相邻相同元素删除次数也是n 所以最差情形是1+2+3+...+(n-1)+n
vl-remove-if 假设完全没有重复,按递减除了lst ,n+（n-1）+（n-2）+...+2 结果应该是一样的
同样的遇到重复时候都是减少的

st788796 · 发表于 2013-11-14 12:41:58

守仁格竹GM 发表于 2013-11-14 12:20
vl-sort 排序应该是 1*2*3*...*(n-1)
vl-remove-if 假设完全没有重复,按递减除了lst n*（n-1）*（n-2）* ...

不排序，4W长表可能CAD OVER

守仁格竹GM · 发表于 2013-11-14 12:58:54

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

我说的那个考虑未必正确，打断时候我也是采取了先排序的方法，效率确实不低，但是不知道我那样思考问题出在了哪里，
大概应该是非极端状况下的效率问题确实有提高很多

账号		自动登录	找回密码
密码			立即注册

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

点评

点评

点评

点评

点评

点评

点评

点评

点评

点评