不負相思意
2018-09-04 13:13:59
百萬條數據的排序。環(huán)境是nodejs,有個object,里面的東西很簡單,就是 key=>value 格式而已let keys = Object.keys(data);光這一步我執(zhí)行就費了一秒鐘的時間了。循環(huán)一次,耗費了1.5秒。還有得搞嗎?我不知道人家那種一秒鐘不到,把數據排列并且搜索的怎么弄的,太神奇了。下面的回答關注點都在需求上面了。詳細說一下。1、首先是nodejs環(huán)境,不是真正的前端。這個我上面沒有說,但不影響解決問題。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存儲應該是一個不錯的解決方案,但環(huán)境不允許。環(huán)境允許的話,我使用mysql之類的存儲就好了。
1 回答

炎炎設計
TA貢獻1808條經驗 獲得超4個贊
let keys = Object.keys(data);
這一句相當于遍歷所有的元素,用時間復雜度表示為O(n*x),x為查找一個元素所需要的平均時間復雜度。js的{}
類型應該采用了一種平衡樹,平衡樹查找一次最好的復雜度也是O(logn),也就是說上面這一句的時間復雜度最好也得是O(nlogn),因為{}
類型還要有其他的一些方法,所有平衡樹的性能并不會是最好的,實際運行的時間必然會高于理論估計的O(nlogn)。
而題主你目前的實際情況是:data是一個有100w數據量級別集合,你需要對鍵值進行排序,js的這一句執(zhí)行一次卻需要1.5s 。
解決方法:
js就是慢,換一種語言去處理你的這個索引集合,比如C++之類的。缺點就是js如果需要不同的鍵值順序,每次都得重新計算;如果存儲的數據進行了修改或者刪除,這個索引也得重新計算。
數據庫也是可以建立索引來提高搜索速度的;
實際上,
{}
存儲的數據本來就是有序的,這個可以查一下排序二叉樹,對于輸出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)的方法都執(zhí)行1.5s, 而這個已經是理論的最低限度了。
添加回答
舉報
0/150
提交
取消