js(javascript)的查找性能详解
时间:2014-09-09 10:34 来源: 我爱IT技术网 作者:山风
前言：
不久前，有个人问我一个问题，“你如何通过计算机用最快速度在一个经过排序的数组中找到指定的值”，当时我的答案就是写一个二分查找算法来找，但是他说这不算最快，最快是将数组序列化成json，然后再找，好像大概的意思是利用js底层的c++实现来完成查找，他同时指出这样做的代价是耗损内存。因为只是口头聊了一下，我后来想来想去还不太明白他的具体的实现方式。在想的过程，我按照我自己明白的几种做法做了一些性能比较。
一、准备数据：
- var arr = [], start = 0, end = 0;
- for(var i = 0, l = 9999999; i < l; i++){
- arr.push(i);
- };
- var getTimeDiff = function(time1, time2){
- return (time2 - time1) / 1e3;
- }
二、查找途径
2~1: 顺序表查找
- var searchSeq = function(arr, key){
- for(var i = arr.length - 1; arr[i] != key; i--);
- return i;
- }
- start = new Date().getTime();
- searchSeq(arr, 999998);
- end = new Date().getTime();
- document.write('searchSeq: ' + getTimeDiff(start, end) + '</br>');
2~2: 二分查找
- var searchBin = function(arr, key){
- var low = 0;
- var high = arr.length;
- while(low < high){
- var mid = Math.floor( (low + high) / 2 );
- if (arr[mid] == key){
- return mid;
- }else if(arr[mid] > key){
- high = mid - 1;
- }else{
- low = mid + 1;
- }
- }
- }
- start = new Date().getTime();
- searchBin(arr, 999998);
- end = new Date().getTime();
- document.write('searchBin: ' + getTimeDiff(start, end) + '</br>');
2~3: indexOf查找
- var searchByC = function(arr, key){
- return arr.indexOf(key);
- }
- start = new Date().getTime();
- searchByC(arr, 999998);
- end = new Date().getTime();
- document.write('searchByC: ' + getTimeDiff(start, end) + '</br>');
三、性能结果
浏览器由上至下依次为chrome 32.0.1700.76 、 IE10、FF27.0.1
结果：最快的是二分查找，其次是indexOf查找、顺序查找。
我的想法：
indexOf查找的思路与顺序查找都是一样的，都是逐一查找的，之所以indexOf会更快是因为它的实现是c++，同样的复杂度，c++的实现会跑得更快，但再跑得快，都不如用二分查找来得快，因为它是一个区间一个区间找的，找的量会少得多，所以跑得最快的。至于那个人说的序列化成json的方式，我还在思索中，或者有机会再找他具体聊一下。
题外话：
从结果看出，其实IE10的性能表现最佳，其次是chrome，firefox，这结果多少有点出乎意外，IE10应该被肯定。
- 评论列表（网友评论仅供网友表达个人看法，并不表明本站同意其观点或证实其描述）
-