javascript - 如何快速标记数据

Question

我有数十亿数据A和数十亿数据B

如果A的项目在B中，则将项目标记为“红色”，如果不是，则将其标记为“蓝色”

我可以像这样想出一个非常缓慢的函数:

var A=[10000000]
,B=[1000000];
for (var m = 0; m < A.length; m++) {
              
  var isInB = false;
  for (var n = 0; n < B.length; n++) {
    if (B[n].id ==A[m].id) {
      isInB = true;
      break;
    }
  }
  
  A[m].color=isInB?"red":"blue";
               
}

Answer 1

您可以使用一个临时集合，然后对其进行测试。这是一个 ES6 实现:

// sample data: primes (A) and Fibonacci numbers (B)
var A = [{id: 1}, {id: 2}, {id: 3}, {id: 5}, {id: 7}, {id: 11}, {id: 13}, {id: 17},
         {id: 19}, {id: 23}];
var B = [{id: 1}, {id: 2}, {id: 3}, {id: 5}, {id: 8}, {id: 13}, {id: 21}, {id: 34}];

// Create a set with all ID values that exist in B:
var bSet = new Set(B.map(b => b.id));
// Enrich A with color property based on that set:
A.forEach(a => a.color = bSet.has(a.id) ? 'red' : 'blue');

console.log(A);

因为这是基于集合的，所以不需要先对数据进行排序。

性能

在比较算法时，我将忽略创建 color 属性所花费的时间，因为两种算法都必须对 A 的所有元素执行此操作。

原算法的时间复杂度为O(n.m)，其中n和m分别为A和B中的元素个数分别。

与原始算法相比，为此使用集合可以提高性能。许多 JavaScript 引擎实现的集合具有接近恒定的插入和查找时间(使用哈希，例如参见 V8 )，尽管如果使用标准搜索树它可能是 O(logn)， n 是集合中元素的数量。我将采用最坏的情况，并假设这两个操作都是 O(logn)。

上述算法将在 O(m.logm) 时间内创建集合，然后在 O(n.logm) 时间内用额外属性填充 A。

这使得总时间复杂度 O((n+m)logm)，优于 O(n.m)。如果常数插入和查找时间适用，那么这将减少到一个简单的 O(n+m) 时间复杂度。