直线首尾连接-四叉树版

yupeng_dyp

dcl1214 发表于 2024-8-10 20:49
我的疑问是四叉树能满足的为啥二叉树不能满足，非要纠结速度，那我就随便修改一句代码，然后上传，你测试 ...

我采用四叉树的方式19W线图元，其中构建四叉树300多毫秒，执行选择在2毫秒左右，高频查寻用四叉树还是不错的

你有种再说一遍

yupeng_dyp 发表于 2024-8-11 15:34
我采用四叉树的方式19W线图元，其中构建四叉树300多毫秒，执行选择在2毫秒左右，高频查寻用四叉树还是不 ...

我觉得这是优化很好的案例,
现在是单点链选你才觉得2ms好,筛选全图链条看看,
你会发现四叉树DFS算法挺慢的,

不计算你构造树的时间复杂度,因为你要重复用树的话就可能不是一次构造的.
选择时间复杂度:
全图是n,直线两个点是2,一次选择是log4(n).
也就是你起码2n*log4(n),会随着规模增长而增长.
为了扔掉这个2n,就筛选碰撞区先.
他敲lisp不懂没关系,你敲c#要懂时间复杂度计算,不然你怎么优化呢...

yupeng_dyp

你有种再说一遍 发表于 2024-8-11 19:09
yupeng_dyp 发表于 2024-8-11 15:34
我采用四叉树的方式19W线图元，其中构建四叉树300多毫秒，执行选择在2 ...

我就是重度IFox用户，用的就是其内的四叉树，不过他那个用lisp优化到0.06秒左右也很厉害呀，如果是算上构建四叉树的时间，就是0.3秒左右了，如果在命令中只是执行一次查寻就有些不理想，构建四叉树的时间超过0.1秒就能感觉到命令执行有卡顿了，所以只有在5W图元以内才能流畅。当然如果是在命令中高频查寻的话，四叉树是很好的，比如 Jig 中实时查寻光标附近的对象、计算相交等；你之前说的后台构建一个四叉树感觉也不太理想，总不能每打开一个图就后台构建吧，有些大图几十上百万的图元，会不方便，内存消耗也是问题

gzxl

好像贴主的话题给你们直接忽略了。

橡皮

dcl1214 发表于 2024-8-10 20:49
我的疑问是四叉树能满足的为啥二叉树不能满足，非要纠结速度，那我就随便修改一句代码，然后上传，你测试 ...

你这个原理应该就是数据库得筛选选择，建议用这个图测试

橡皮

yupeng_dyp 发表于 2024-8-12 10:36
我就是重度IFox用户，用的就是其内的四叉树，不过他那个用lisp优化到0.06秒左右也很厉害呀，如果 ...

以他这个插件来说一次查询的时间和选择的线连接串连得线得数量正相关（基本就是线性关系），我推测就是简单地数据库查询，当然他把点集做一些排序或什么处理然后检索处理效率会更高。
下边是我用四叉树测试得结果（MP4不能上传，懒得转了）：

dcl1214

yupeng_dyp 发表于 2024-8-12 10:36
我就是重度IFox用户，用的就是其内的四叉树，不过他那个用lisp优化到0.06秒左右也很厉害呀，如果 ...

既然你提到了高频查询，这就是数据库的优势了，数据库支持索引法，以及树结构查询，你要查询一根直线的关联，数据库瞬间返回来；你将线段的10  11两个值录入 到数据库的时候，瞬间启动500个线程来分析，每个线程一个线段作为起点，同时查询自身线段是否被其它线程分析出来了，如果当前线程里面发现有线段出现在其他线程里面，当前线程根据情况结束或者进入下一个线程分析；最终分析出来的结果可以用组号区分，同属一个组号的，就是一组周边集合

你有种再说一遍

yupeng_dyp 发表于 2024-8-12 10:36
我就是重度IFox用户，用的就是其内的四叉树，不过他那个用lisp优化到0.06秒左右也很厉害呀，如果 ...

只能说你没有继续想下去,令人失望,
60ms就觉得很好?那你一次链选2ms,我也觉得不好呢,
如果是10w图元都是链条呢?直接成20w毫秒?200秒?

量大自然加速方案都不一样,100w又会怎么样?
迷恋四叉树的后果自然就是忽略了其他方案了.
起码并行你就没有做到...
起码你又没有分析有序数组比二叉树还快...

后台四叉树就慢?
那cad自己不构建嘛?你也嫌弃cad慢?
那你自己不想想加速方案?不会异步构建吗?
不会等到第一次调用四叉树命令才立即完成树吗?
怎么没有我,你们就不会做事情了?

你是既追求四叉树,又不想后台建树?
你觉得开上百万图元的图纸会缺那一两秒?
它渲染时间才是慢吧.要不把渲染也拿掉算了?
那我建议你不要开就好了嘛...

你有种再说一遍

dcl1214 发表于 2024-8-12 15:10
既然你提到了高频查询，这就是数据库的优势了，数据库支持索引法，以及树结构查询，你要查询一根直线的关 ...

计算机没有迷信的,
数据库并没有神奇的能力可以给你瞬间返回,
数据库无非也是Map,二分,多叉树结构,
每种查询都有相应的时间复杂度.

真正的问题不是上面,因为大家都是多叉树,
真正的问题是ssget的执行步骤:
1,进入lisp解析器.
2,进入选择集条件解析器,拆分条件.
3,进入界面显示缓冲区.
4,进入八叉树.
5,再过滤其他条件.
6,聚合元素.
还存在各种边界检查的成本...
如果一次60ms,那么10w次是非常巨大的消耗.

我们多叉树就是二级索引.
这就是为什么我们自己构建四叉树,比自带的树还快.
因为可以减少边界检查,数值类型替换,减少栈帧等加速方案.
即使如此,每次选择仍然要2ms,如果10w次就是200秒.

有序数组比多叉树还要快很多,
CPU对于顺序访问比起跳跃访问是有各种优化的,
例如缓存预读,分支流水线技术.
这就是我为什么经常diss lisp的链表问题,它将导致大量的cache miss.
这里可以看见什么是CPU友好,什么是内存友好,什么是磁盘友好.
这就是为什么高频查询做有序数组更好,因为这是CPU密集任务.
尤其是图形学上面,渲染和缓存命中是比任何一种数据库优化技术还注重性能.
同时有序数组是窗口搜索,线性速度,
也就是n*log(n),比2n*log4(n)快多了

多线程存在锁粒度/伪共享/上下文切换的问题,
并非你单纯认为的能并行查询那么简单,
尤其是数据库讲究取舍,不会像图形学那么极限,
行式数据库和列式数据库的优缺点就非常能说明问题,
你觉得数据库有魅力,
是因为lisp难以自行实现上面的代码,
这就封堵了你对于后面知识点的获取,
例如volatile关键字,内存屏障,锁粒度,并发容器等等...

多线程重点是对数据切割,
能够利用多个核心的寄存器实现并行,
并非无脑使用超越核心数的线程数,
因为它将被转为虚拟线程,然后反复切换线程上下文,
造成大量浪费没必要的时间.

你可以去看看十亿行天文台数据挑战,SQL版本的方案是非常慢的...
写代码总是更灵活的,更能写出一个比cad自身还快的方案.
不然就只会调用cad了...

轮回

dcl1214 发表于 2024-8-10 20:49
我的疑问是四叉树能满足的为啥二叉树不能满足，非要纠结速度，那我就随便修改一句代码，然后上传，你测试 ...

只能选择视口内的！！！！！！！！首尾相连的线段很多很长，没在视口内的，根本选不到啊！！！！