javascript - nodejs百万条数据的排序

问题描述

问 题

百万条数据的排序。环境是nodejs，有个object，里面的东西很简单，就是 key=>value 格式而已

let keys = Object.keys(data);

光这一步我执行就费了一秒钟的时间了。

循环一次，耗费了1.5秒。

还有得搞吗？
我不知道人家那种一秒钟不到，把数据排列并且搜索的怎么弄的，太神奇了。

-----------------补充----------------------

下面的回答关注点都在需求上面了。详细说一下。

1、首先是nodejs环境，不是真正的前端。这个我上面没有说，但不影响解决问题。

2、下面的回答都角度都是什么先展示几页啥的，我没说展示百万条数据，我只是排序，搜索。
比如，我搜索 key=abc ， 第 100条，列出 50个数据，按照key排序列出， 你难道不是从这100万条数据去搜索、排序吗？难道你要从前50条里面去操作吗？

我操作100万条，我可没说展示100万条。。。这个得看清楚。

3、具体情况是这样的。底层数据存储使用leveldb，leveldb都是存储在硬盘里面，单个key搜索还是挺快的。但是你要搞个排序、分页，他得把100万条数据从硬盘里面一个一个读取，然后你再进行操作。

按照他那样，读取完一次，估计4分钟。从硬盘读取，速度肯定很慢了，不过他也有好处，内存占用小。不然你10G的东西，都一次性拿出来再操作，可想而知……

所以，解决的办法，自己生成索引。把索引放到一个文件里面，查询的时候一次性加载进来，放到内存，这样就比你把100万篇文章从硬盘一个一个找出来再排序高效很多。
比如 id=>dateline 这样的形式，保存id和时间，如果你想按照时间进行排序，那么就可以对索引进行排序，比如取出50个id出来，然后再去硬盘读取这50个就行了

因为索引文件很小，只是保存了一些简单得不能再简单的数据，所以百万条数据，加起来不过几十MB，这样内存占用也是很低的。

4、像这种情况，索引使用Redis存储应该是一个不错的解决方案，但环境不允许。环境允许的话，我使用mysql之类的存储就好了。

解决方案

let keys = Object.keys(data);

这一句相当于遍历所有的元素，用时间复杂度表示为O(n*x)，x为查找一个元素所需要的平均时间复杂度。js的{}类型应该采用了一种平衡树，平衡树查找一次最好的复杂度也是O(logn)，也就是说上面这一句的时间复杂度最好也得是O(nlogn)，因为{}类型还要有其他的一些方法，所有平衡树的性能并不会是最好的，实际运行的时间必然会高于理论估计的O(nlogn)。

而题主你目前的实际情况是：data是一个有100w数据量级别集合，你需要对键值进行排序，js的这一句执行一次却需要1.5s 。

解决方法：

1. js就是慢，换一种语言去处理你的这个索引集合，比如C++之类的。缺点就是js如果需要不同的键值顺序，每次都得重新计算；如果存储的数据进行了修改或者删除，这个索引也得重新计算。

2. 数据库也是可以建立索引来提高搜索速度的；

3. 实际上，{}存储的数据本来就是有序的，这个可以查一下排序二叉树，对于输出100w的前50个数据这种问题，只需要：

   var num = 0;
   for(var x in data){
   if(num < 50) num++;
   else break;
   // your code used to deal data[x]
   }
      

看了一下题主的其他评论，得知题主的目标：根据某一键值的将数据排序，取第x个，数据量高达100w。

那无论如何都得读100w条数据，我感觉没法再大幅度提升速度了，算法复杂度O(nlogn)的方法都执行1.5s, 而这个已经是理论的最低限度了。

这篇关于javascript - nodejs百万条数据的排序的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！