求js最高效算法：范围查找

实际需求里面，“长街”总长度在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++差多少？

@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一段啊

@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运算之间权衡.

//门牌号 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; } });

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

hash table

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

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

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

@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)高。

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

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

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

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

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

@hainee 好吧，我肤浅了。

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