求js最高效算法:范围查找
发布于 7 年前 作者 softice 8323 次浏览 最后一次编辑是 5 年前

有这么个需求: 比如,一条长街,门牌号从0 - 1000 0-100,卖鱼 101-203,卖菜 204-500,卖肉 501-1000,卖鸡蛋

各个分段之间是连续的: [0-100],[101-203],[204-500],[501-1000]

然后随便给出一个0-1000的门牌号,如何最快速的知道这个号是卖什么的? 这个算法是瓶颈,要求速度一定要极致,求各位大神指点。

39 回复

实际需求里面,“长街”总长度在40亿左右,大约分为50万组。

每组不定长是吧?

50万组么二分法么。查一个门牌最多19次就能查出来了么。

以门牌号首为界限存入数组也就50w的数组。然后对这个数组进行二分即可。

嗯,而且长度还不太均匀,有的很大,有的很小。。。 …

谢谢指点!不知道数据库里面,类似的算法是不是也是这么实现的?

@SoftICE 这个我就不清楚了😂

数据库内部的机制还是比较复杂的。

总之对你的场景来说 2^19 就超过 50w 了,所以最坏情况 19 次找到。

@XadillaX 谢谢,我试试看。

如果是数据库,建个索引就可以了

准备直接读内存里面处理,数据库太重了,呵呵~~

算法什麼的google一下就好了 之後寫c++ addons 如果性能覺得還不夠,就寫c++ addons的時候搜索算法用匯編(彙編)寫

没必要汇编吧,这个简单的需求时间复杂度是o(logn)的😂

@XadillaX 是的是的 的確沒有必要 樓主說要極致嘛:)

@XadillaX 另外妹子v2ex找工作的帖子,不發照片怎麼能火呢。。。。

@jiangzhuo 不过撸主写个addon还是可以尝试的😂

50W个都放到内存里也没多大吧

基础运算,1+1啊 a>b啊,node和c++差多少?

//门牌号 var numbers = [0,1,2,3,4,5,6…]; //卖什么的 var types = [ { begin : 0, end : 120, type : ‘卖鱼的’ }, { begin : 121, end : 680, type : ‘卖肉的’ }, { begin : 681, end : 990, type : ‘卖X的’ }, { begin : 991, end : 1300, type : ‘卖Y的’ }, … ] //桥梁 var bridges = [ [0, 1, 2, 3]//这里的意思是0-1000这个段中包含了types中的0,1,2,3这四个段 [3…] … ];

比如这个时候给一个数x, 那么 就可以这样了 var idx = Math.floor(x / 1000); bridges[idx].forEach(function(el){ if (x >= el.begin && x<= el.end) { console.log(‘x=’ + el.type); return false; } });

分段倒也可以,而且可以分段+二分。

@SoftICE 如果你只是查找数据,我建议: 1、数据放文件中 2、自己建索引,索引放内存中

最好是hash,最快了,时间复杂度为O(1),与你的数据量关系不大

var 门牌分类索引= { 1:'卖肉的’ 2:'卖肉的’ 3:‘卖肉的’ … 100:‘卖鱼的’ …… 1000:‘卖菜的’ }; var 门牌号 = 100; var 分类 = 门牌分类索引[门牌号]; console.log(分类);

@hainee 40亿的长街你用map?

直接二分好了,没必要预处理bridges数组,极端情况下每次forEach也要查1000次,没二分效率高。

@XadillaX 有啥不行的? 楼主又没说只能在一台机器上,楼主可以做分布式计算啊!如果有10台服务器,那每台也就4亿数据而已!map的键值都采用Int类型,键Int32,值Byte,一共5字节,每台服务器消耗内存5*4亿 = 20亿 = 1907M < 2G,时间复杂度为O(1)! 如果楼主有很多台式机,比如100台,然后有自己的机房,那就更简单了!每台台式机消耗200M内存就能提供时间复杂度为O(1)的高效算法了!当然也可以买100个VPS!阿里云上配置很低的那种(1CPU、512M内存、1M带宽)100个VPS一年也就几万块而已!!

如果不行,只能在一台服务器上,那就弄个40G的固态硬盘,然后把硬盘虚拟成内存,最后把40亿map的数据对象放到这个虚拟内存中!

用线段树,见百度百科。比二分好

@cpsa3 不一定要1000一段啊, 可以100一段啊

@xujun52011 100一段的话你bridges数组的长度就是40000000,这样会增加你预处理bridges的时间,同时占内存。极限情况你可以选择1个数字一段,那样查询就是O(1),相当于对40亿做map了存在内存中,光预处理就要扫40亿次。

线段树优势在于O(logN)复杂度维护数组的变更,光查询没必要用线段树。考虑到建树的复杂度就没有二分好了。

我提个醒,v8内存限制只能用1.4G左右

不是可以设置吗?

@hainee -。 - 50w的数据二分只需要19次即可,而且廉价。如果分布式了,我相信能存储更多的数据。O(LogN)和O(1)差别不大。真要算上分布式的话跟一台机子比起来,O(1)+网络延迟的效率不一定比O(LogN)高。

线段树是不错 -。 - 对于批量更改是个不错的选择。

感谢楼上各位,受益匪浅。等最后对比一下,算法确定了,再和大家汇报。

最好是建索引,索引的算法就是二分法

@XadillaX 首先,你说O(1)和O(LogN)差别不大,我完全不认同。O(1)是与数据量无关的效率恒定、稳定的算法,而O(LogN)是线性增长的,同时O(LogN)在50W时平均查找次数是10次,是O(1)的10倍左右!差别10倍还不大?打个不恰当的比喻:兄弟你你老婆的月收入要是比你大10倍,恐怕你在家就别抬头了,准备伺候女王吧…… 其次,那你算过并发量没?最牛掰的机器能承受多少并发?而且这个还是计算和IO(不管是访问内存还是磁盘)双密集型的!俗话说的好,好汉架不住人多啊!否则Google搜索它也干脆弄一台服务器好了,何必弄那么几百万台服务器呢! 最后,楼主要极致的算法,通常来说一个问题的复杂度是恒定的,一般节省存储空间的算法就比较费时间,而要写出省时间的算法,一般就比较费存储空间。对于服务端来说,最不缺的就是存储空间,扩展存储空间的性价比远高于扩展CPU(这玩意儿不好扩展)!

40亿数据量的原始表不适合用于查询待查门牌号是卖什么的。 因为号段连续,就可以另建门牌号段表,50w记录那个。就是 xujun52011说的var types = [{begin:x,end:y,type:z},…] 你不是放在数据库里面吗?那如果要查门牌号为xxx的是卖什么,就对types的begin建立索引, 然后选择begin小于等于xxx的号段记录中最大的那条。 select top 1 type from types where begin<=xxx order by begin desc 50万记录加单键有序索引,速度应该没问题吧

@cpsa3 我这个方法本来就需要在内存占用跟cpu运算之间权衡.

@hainee 这一点我同意,要时间就只能牺牲空间,而空间更容易解决且更廉价。

@SoftICE 拜托,别在Node主进程里面搞计算密集型,那样会柱塞的!当然你说你就喜欢这样也没关系……

@hainee 好吧,我肤浅了。

毕竟没有工作过,不能想象那种业务场景,也没遇到这种业务需求,没有经验。

回到顶部