有这么个需求： 比如，一条长街，门牌号从0 - 1000 0-100，卖鱼 101-203，卖菜 204-500，卖肉 501-1000，卖鸡蛋
各个分段之间是连续的： [0-100],[101-203],[204-500],[501-1000]
然后随便给出一个0-1000的门牌号，如何最快速的知道这个号是卖什么的？ 这个算法是瓶颈，要求速度一定要极致，求各位大神指点。
//门牌号 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(分类);
@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的数据对象放到这个虚拟内存中！
@xujun52011 100一段的话你bridges数组的长度就是40000000，这样会增加你预处理bridges的时间，同时占内存。极限情况你可以选择1个数字一段，那样查询就是O(1)，相当于对40亿做map了存在内存中，光预处理就要扫40亿次。
@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万记录加单键有序索引，速度应该没问题吧
