avatar-decorate
廿陆畵生 level
快手_向量检索平台工程师 identity
获赞
1107
粉丝
763
关注
1
看过 TA
1.2W
男
上海交通大学
2023
搜索算法
IP属地：北京
前Shopee逐风计划信息检索算法工程师实习生
私信
关注
发布(278) 在招职位 刷题
头像 头像
廿陆畵生
2022-12-21 18:18
快手_向量检索平台工程师
此情可待成追忆
2022-12-21 打饭有感之乌鸦反哺！​​今年的两篇论文都在说HEM算法，需要在每个属性上做两次位集运算，​比如对于5，6，7，8里的桶，要找HVE上的G1和LVE上的G2，分别和全局位集做一次或运算，对于9，10，11，12里的桶，要找HVE上的G2和LVE上的G1，分别和全局位集做一次或运算。​对于事件落入的某个cell（桶），之前是要找两个位集，做两次或运算的，其实hve上的位集和lve上的位集是一一配对的！只需要存这两个位集的并集就好，也就是在一开始插入订阅时就把这两个位集当成一个来标记这样一来，直接妥妥地少了一半的或运算次数，缓存也少了一半空间占用！​​奈何子欲养而亲不待，会议论文已见刊，期刊论文昨天已提交审稿意见回复，毕业论文这一部分已经翻译好还得赶后面的。​​这是在买晚饭时想到的，下午是在想如何解释把HEM应用于包分类领域设计一个新算法，解释了协议号属性上的逻辑，直接给每个协议号设一个位集，以为相当于HEM上桶数c等于组数g，瞬间发现不等价，HEM上的组是前缀桶或者后缀桶，那么，把包分类协议号上这个穷举做法又折回去应用到HEM上呢？那可不就是为每个桶单独设置一个位集嘛？于是就自然想到了把现有的两个位集合并起来，也发现了它们一直存在着一一对应关系没注意到！一年半了！​​只是遗憾地是双重选择策略用不了了，但双重选择就是为了用一半的缓存实现相同的加速效果，现在缓存也减半了，或运算还可以进一步减半！
0 点赞 评论 收藏
转发
头像 头像
廿陆畵生
2022-12-20 01:20
快手_向量检索平台工程师
2022.12.20 午夜随笔（洗澡）
2022.12.20 午夜随笔（洗澡）之一年了，终于把TAMA转化为反向匹配成为了可能 有人说，我们每天都在见证历史，有人说，我每天都在沉淀历史。 （700字小作文） 从前，它是叫“方向匹配基本定理（二）”的，即基于同一个数据结构，去找出匹配的谓词，就可以设计出正向匹配算法，去找出不匹配的谓词，就可以设计出反向匹配算法。 基于反向REIN的数据结构可以设计出正向fREIN算法， 基于反向HEM的数据结构可以设计出正向fHEM算法， 基于BG-Tree数据结构可以设计出正向和反向匹配算法fBG-Tree，bBG-Tree 但基于TAMA数据结构没能设计出反向匹配算法， 由于不够通用...
0 点赞 评论 收藏
转发
头像 头像
廿陆畵生
2022-12-19 23:32
已编辑
快手_向量检索平台工程师
0 点赞 评论 收藏
转发
头像 头像
廿陆畵生
2022-12-19 18:34
快手_向量检索平台工程师
2022年12月19日考古纪实
​2022年12月19日考古纪实这种学术垃圾要扔进毕业论文里吗？​今天实现了这个2022年4月26号提出、5月3号挥笔构思出伪代码的RLE编码优化，这是一种新的ACL报文查询算法。不出意外地出意外了，慢了很多，毕竟还是算术运算，不如逻辑运算，更何况前几天刚证明64位与运算比 比较运算 都要快一些，https://www.zhihu.com/question/572870633/answer/2805274563RLE不仅难以更新维护，内存大，时空不稳定，平均还要执行一万多次比较和+1运算，不知道还有哪个企业在用这种数据结构。真的逼我用二分吗。昨天的聚合优化，当二级缓存失效需要检查一级缓存时，称为发生了一次“聚合失败”，这时类似于发生一次中断，trap，保留当前上下文，把自己挂起，停下来去做其他工作，拿到其他工作的结果后再决定还要不要继续往下做。 #C++# #C++实习# #C++工程师# #毕业论文# #研究生#
投递知乎等公司10个岗位
0 点赞 评论 收藏
转发
头像 头像
廿陆畵生
2022-12-18 19:10
快手_向量检索平台工程师
包分类查找算法之聚合压缩位集优化
一种基于位集的包分类\报文查找\ACL表查询\网络数据包路由转发算法昨天才开始实现今年4月26号提出的这个RLE编码优化的前半段（聚合位集），今天测了下性能提升了50%11属性-32聚合比-正向位集搜索（k11-AFBS，Aggregation Forward Bitset Search）类似多级缓存体系一大堆实验，一大堆坑，谁爱跑谁填去，我不管了第二套数据集上，乱序后平均386纳秒(之前790纳秒)，不乱序平均334纳秒(之前600纳秒)，去掉第3个数据集后剩下16个数据集不乱序平均187纳秒k11-AFBS 与运算次数从 1944 减少到 168，比较次数从 3892 减少到 210，聚合成功32次，聚合失败2.7次，聚合成功率92.3%，检查次数没变化，平均 3.97 次检查。（RLE编码很难更少了吧... 可以直接对一级位集缓存编码，也可以只对二级位集缓存编码，）最快的是第三套数据集（强局部性）中的第9个数据集，69纳秒聚合压缩比从1上升到32，内存从157MB下降到81MB，查找时间从1148纳秒减少到419纳秒，再引入高效位运算__builtin_ctzl后减少到386纳秒，聚合比再翻倍到64后没效果了，再翻倍到128的话要改代码了。
0 点赞 评论 收藏
转发
头像 头像
廿陆畵生
2022-12-16 00:31
快手_向量检索平台工程师
单凡一开始b[0][bi]就是0，就不需要做&运算了，上面的注释的版本先检查，非0才运算，到0或执行10次运算即止下面的版本一上来就运算，再判断是不是0，如果本来就是0，就不需要做多余的&运算，所以理论上注释的版本更优。然而现实是，统计出来的运算次数没变化，好吧，就算不可能一开始就初始化为0，但运算次数没变，速度怎么慢了这么多？从1.835us到1.269us还有一个做 | 或运算的版本，图4，也是变慢了。​​其实有大量的情况是0，可以一次与运算都不要做的：图5。​​代码在https://github.com/shiwanghua/PacketClassification/blob/2d13bd91e0d701f432b3c0e8e9d1cf424259209a/20221003-GraduationDesign/HEMBitsetsSearch/HEMBS.cpp#L320 (34257)#C++# 
0 点赞 评论 收藏
转发
头像 头像
廿陆畵生
2022-12-11 01:55
快手_向量检索平台工程师
第93场双周赛之预言成真（图九）
第93场单周赛进行的时候骑，摩，托踢碎了，两，颗，牙（图一）于是出了好多血，挂了好多彩（图二图三）看了一个半小时大佬的代码，试出了top1和top3的代码中的错误（图456）。第三题想半天最后还是靠直觉猜的。第四题把答案里的二分之一判定拿到外面来判断是否有合理解了这个全球第一的美国人的代码好像是错的初看觉得简洁，越看越不对劲然后拿第一个用例加了个4和6，结果就不一致了这个全球第三的来自新加坡的也是错的补位时没判断不等于两个位置的数，基于第二个样例互换前两个位置的元素即可试出来： [2,2,2,1,3] [2,1,2,3,3] 答案少了2，因为取了1而不是3 #C++# #周赛# #力扣# #世界杯#
0 点赞 评论 收藏
转发
工具箱
牛客网
牛客企业服务