cad.net 排序和搜索(扫描线的必要测试)

你有种再说一遍

没想到二分法居然真的那么快...
不过大家大概率都是偷懒写Linq的FirstOrDefault的啦,
因为迭代器接口在C#是最多的.
只能说优化方向可以往排序+二分这方面考虑.
https://www.cnblogs.com/JJBox/p/18688118

不过...
扫描线算法上面,二分法次数是2n根扫描线,
因为要搜前一根,搜后一根,再夹选中间.
我内部还做了很多骚操作,
例如二分搜最左最右用跳两步,而不是一步...

现在感觉还是太慢了...
我来算一算:
100w数据类二分法是50ns一次.
也就是一秒只能串行执行两千万次int32的二分法.

50w条扫描线.不重叠是100w条曲线(最坏)
50ns*100w=5000w(ns)=0.05秒.
*2 = 0.1秒...
好像还能接受哦...

又不过...
double字节数多一倍...
*2 = 0.2秒...

横扫+竖扫
*2 = 0.4秒...

奇数闭合区和偶数闭合区(这一步我甚至还没有做)
*2 = 0.8秒...

未加入:
串行读取数据库时间.
求交点时间.
foreach状态机耗时.
构造代理类,访问属性和拷贝数据时间...
现在还有底边排序和中点排序两个排序能不能合并的难点.

管中窥豹都可以算到那么耗时了...
如果不用并行你能跑进五秒内已经超神了...
不用数据结构更是无稽之谈...

而且你可以看到,
为什么存在爆内存的情况,因为想要搜得快就要拷贝副本.
这个可以监控内存来实现各种降级...

不太晓得如何用SIMD来改造,
毕竟完全实现在容器和多线程下,
而且对边成组的合并居然要单线程,真的想破我脑袋了...
目前只是原理验证了,实际上还有块变换到最外层这种东西,
还有工作量!

不过...
大多数情况扫描线数还是很少的,也就万级别.
而且我们还有大杀器,制作索引.


修复:
https://www.cnblogs.com/JJBox/p/18652906
通过对颜色的处理,来判断是否能够加入.
减少了一个_set使用,并且这是原子性的.
还发现之前处理过的东西,居然忘记处理了,写到现在才想起来,

类的空参数构造,是美好的,因为它能够序列化.
初始化超级多段线时候,
可能整个组是横区或者竖区,加入其他斜组并染色+100了,
因此这种组已经没用了,要排除.
总算想起来了...

czb203

感觉惊惊大佬就是程序天才

你有种再说一遍

真是累死狗了,
通过对颜色的处理,就可以减少hashset的使用,
但是不知道是否存在多线程问题...

你有种再说一遍

感觉可以用C++重构了...

你有种再说一遍

这个功能太大了啊,感觉还得写一阵子...
存在并发的地方感觉不是很爽...
完整功能的代码量好像有点高啊,
我已经用Linq减少代码量了,
优化缓存命中这种设计都已经忘记了...
要不还是别写了...

橡皮

你有种再说一遍 发表于 2025-1-25 16:53
这个功能太大了啊,感觉还得写一阵子...
存在并发的地方感觉不是很爽...
完整功能的代码量好像有点高啊,我 ...

加油坚持就是胜利！

gzxl

你有种再说一遍 发表于 2025-1-25 16:53
这个功能太大了啊,感觉还得写一阵子...
存在并发的地方感觉不是很爽...
完整功能的代码量好像有点高啊,我 ...

我见到最高效的代码：
几万行代码几乎就三个关键字 int float double，还有自己定义的struct(结构体)、最底层的api， 没有其他的。

你有种再说一遍

或许组的合并不应该采用集合论操作呢?
要是能变成一个矩阵?用上SIMD才是关键啊...
难怪真的应了那句话,复杂的情况只能用复杂的方案?

你有种再说一遍

如何把C#写成C++模样?
https://www.cnblogs.com/InCerry/ ... &order=1&desc=false

或许只能指望这种骚操作才行
1,[SkipLocalsInit] 数据不需要清零.NET5才有.
2,紧凑型布局.结构体是"干净"的,它不存储方法表,而是在CLR元数据内.
3,非托管堆申请内存,不触发STW时间.
4,利用ref不拷贝值对象数据,而是引用.
5,文章是X64测试的,在32位需要自行测试.

他居然是朝着一亿个对象做的.
学习SIMD的时候知道改成指针调用数组比Span更快.
不过这个和十亿行天文台挑战还不太一样,
居然用了非托管堆进行,显然更深入底层,

正如评论区说的,
百分之一的代码写这种,就能得到媲美C++性能,
其他部分只需要注重业务流程.
所以你可以大胆地先满足业务,再优化性能.