了解使用对象作为哈希值的JavaScript算法的复杂性

Question

我正在尝试想出一种算法来解决以下问题。

给出一组ID

var ids = [8098272281362432, 7824519999782912]; 

查找项目阵列中的所有比赛。

var people = [ 
    { 
     "id": 8098272281362432, 
     "age": 59, 
     "name": "Douglas Hunter" 
    }, 
    { 
     "id": 625873891885056, 
     "age": 1, 
     "name": "Lottie Owen" 
    }, 
    { 
     "id": 7824519999782912, 
     "age": 100, 
     "name": "Maud Wise" 
    }, 
    { 
     "id": 2561552265773056, 
     "age": 115, 
     "name": "Annie Bennett" 
    } 
]; 

方法1 我可以由id（O(n log n)）排序两个阵列，然后通过两个阵列从顶部迭代一次向下（O(n)）

解决这个

var alg1 = function(people, ids) { 
    var matches = []; 

    var sortedPeople = people.sort(function(a, b) { 
    return a.id - b.id 
    }); 
    var sortedIds = ids.sort(function(a, b) { 
    return a - b 
    }); 
    var curPersonIndex = 0; 

    sortedIds.forEach(function(id) { 
    while (sortedPeople[curPersonIndex].id !== id) { 
     curPersonIndex++; 
    } 

    matches.push(sortedPeople[curPersonIndex]); 
    }); 

    return matches; 
}; 

方法2 我虽然可以用O(n)算法通过创建一个id到人的映射来改善这一点，然后我可以查找每个id的人。

var alg2 = function(people, ids) { 
    var matches = []; 

    peopleMap = {}; 

    people.forEach(function(person) { 
    //Is this O(1) or O(log n)? 
    peopleMap[person.id] = person; 
    }); 

    ids.forEach(function(id) { 
    matches.push(peopleMap[id]); 
    }); 

    return matches; 
}; 

但是，当我测试了这两个算法似乎preform大致相同。 ＃1铬更快，＃2在Firefox中稍快。

http://plnkr.co/edit/FidAdBqS98RKebxaIlva?p=preview

我越来越觉得插入场成一个对象是O(log n)不O(1)因为我本来期望。我已阅读了一些有冲突的帖子，但我不确定。我想这可能取决于浏览器。有没有什么办法可以在JavaScript中用O（n）算法一致地解决这个问题？

Answer 1

首先，JavaScript不要求将对象实现为散列（平均值为O(1)查找），而不是使用其他结构（如O(log(n))的BTree）。所以没有人能保证对象属性查找的性能。

但通常人们使用哈希值。这是O(1)。

但正如笑话所说，对于所有意图和目的，log（n）是一个常数。对于Google来说，这是一个稍微大一点的常量。捕捉到真实的真相。 log(1000)和log(1000000000)之间的区别是3倍于CPU的缓存与去RAM访问的东西之间的差别是10倍。虽然理论上O(1)比O(log(n))更好，在实践中数据的大小，我们实际上很可能会遇到，实施细节造成更大的差异。而且要么能赢。

所以你的基准测试没有提到理论缩放规则。而事实上，不同的实现有不同的表现获奖者为您的使用情况下，大约是世界上不幸的事实，你必须在工作中的一个