2022-09-29 01:36 上海交通大学 搜索算法 发布于上海
关注
2022-09-29 午夜随笔之叕来送idea/专利了
这次还是一个匹配/搜索/查询算法领域，
又是难产而亡，还是将花落谁家呢？
让我们拭目以待。
0. 问题简介
值域：[1,1000000] 正整数
被查询数据/数据库/算法输入/数据集：一千万个 pair
查询：输入一个value比如50万，快速找出value大于等于50万的所有id
要求：方便更新、查询快、适合多个维度/属性上的AND查询 (比如要同时满足另一个维度上所有value大于等于75万的id，或者还要满足在第三个维度上有定义value的id(非空))
1. 现有算法
设置1000个桶（动态数组），桶号从1开始编号，第一个桶存储value位于[1,1000]的pairs，第二个桶存储value位于[1001,2000]的pairs，最后一个桶存储value位于[999001,1000000]的pairs
查询：比如查询value为505000，则桶号52~100里的id即为满足条件的查询结果，另外51号桶里value大于505000的id也是查询结果，用一千万位的位集存储这些id是否出现，每个维度共享这个位集，即可解决问题。
2. 不足与改进
如果存在热点，则pair会集中存在于某些桶里，导致当查询值落入这些桶时需要挨个比较很多次。
比如500001~510000之间的pair有800万个，则对于这个区间里的查询值，每次需要比较800万次，因为插入时就是直接append到桶的最后一个位置，每个桶上都是无序动态数组，需要挨个比较，不能二分。
改进
把按值域宽度等分来划分区间改成按负载等分来划分区间，让每个查询的比较次数相同，性能稳定
这种等负载区间不会因为割裂热点带来什么负面影响（本来以为会有什么缺点呢，或者是还没找到？）
具体看图片///
这时算落入哪个区间不能O(1)了，而是O(n)。
小小变动，不成敬意，来自某次面试。
但这是很底层的一个改动，位于其上的算法会由之而变
比如HEM的负载累增位集可以变成区间累增了，因为区间已经是负载均衡的了，不需要再加一层动态了。
双向选择优化不存在动静模式了，因为此时的静态即区间数/桶数可以等价于动态的负载。
但都需要过一段时间等热点偏移了就重新构建一下索引，当然在插入时实时调整也不是不可以：
某个区间内的点
这次还是一个匹配/搜索/查询算法领域，
又是难产而亡，还是将花落谁家呢？
让我们拭目以待。
0. 问题简介
值域：[1,1000000] 正整数
被查询数据/数据库/算法输入/数据集：一千万个 pair
查询：输入一个value比如50万，快速找出value大于等于50万的所有id
要求：方便更新、查询快、适合多个维度/属性上的AND查询 (比如要同时满足另一个维度上所有value大于等于75万的id，或者还要满足在第三个维度上有定义value的id(非空))
1. 现有算法
设置1000个桶（动态数组），桶号从1开始编号，第一个桶存储value位于[1,1000]的pairs，第二个桶存储value位于[1001,2000]的pairs，最后一个桶存储value位于[999001,1000000]的pairs
查询：比如查询value为505000，则桶号52~100里的id即为满足条件的查询结果，另外51号桶里value大于505000的id也是查询结果，用一千万位的位集存储这些id是否出现，每个维度共享这个位集，即可解决问题。
2. 不足与改进
如果存在热点，则pair会集中存在于某些桶里，导致当查询值落入这些桶时需要挨个比较很多次。
比如500001~510000之间的pair有800万个，则对于这个区间里的查询值，每次需要比较800万次，因为插入时就是直接append到桶的最后一个位置，每个桶上都是无序动态数组，需要挨个比较，不能二分。
改进
把按值域宽度等分来划分区间改成按负载等分来划分区间，让每个查询的比较次数相同，性能稳定
这种等负载区间不会因为割裂热点带来什么负面影响（本来以为会有什么缺点呢，或者是还没找到？）
具体看图片///
这时算落入哪个区间不能O(1)了，而是O(n)。
小小变动，不成敬意，来自某次面试。
但这是很底层的一个改动，位于其上的算法会由之而变
比如HEM的负载累增位集可以变成区间累增了，因为区间已经是负载均衡的了，不需要再加一层动态了。
双向选择优化不存在动静模式了，因为此时的静态即区间数/桶数可以等价于动态的负载。
但都需要过一段时间等热点偏移了就重新构建一下索引，当然在插入时实时调整也不是不可以：
某个区间内的点
全部评论
豆丁爱吃🐟
北京理工大学 财务
楼主厉害啊
相关推荐
不愿透露姓名的神秘牛友
07-18 17:25
不午睡会死仙人Zz：分享一个自己做的GitHub面试题整理项目0voice/Campus_recruitment_interview_questions，积德积德，许愿自己和大家都能过面
点赞 评论 收藏
分享
投递小米集团等公司7个岗位
06-18 20:47
广西大学 单片机 点赞 评论 收藏
分享