javascript - 理解使用对象作为散列的 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"
    }
];

方法一我可以通过按 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我虽然可以通过创建 ID 到人的映射来使用 O(n) 算法改进这一点，然后我可以为每个 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;
};

然而，当我对此进行测试时，这两种算法的表现似乎大致相同。 #1 在 chrome 中更快，#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 ))。所以没有人能保证对象属性查找的性能。

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

但正如笑话所说，无论出于何种意图和目的，log(n) 都是一个常数。对于 Google 来说，它是一个稍大的常量。 这捕获了一个真实的事实。 log(1000) 和 log(1000000000) 之间的差异是 3 倍。访问 CPU 缓存中的内容与访问 RAM 之间的差异是 10 倍. 虽然理论上 O(1) 优于 O(log(n))，但在实践中我们实际可能遇到的数据大小，实现细节产生更大的不同。两者都可以获胜。

因此您的基准测试对理论缩放规则没有任何用处。事实上，不同的实现对您的用例有不同的性能赢家，这是您必须在其中工作的世界的不幸事实之一。