比较两个数组的有效方法

Efficient way to compare two arrays

本文关键字：数组 有效 方法 两个 比较      更新时间：2023-09-26

我正在使用两个数组来完成检查array1中的值是否存在于array2的任务。如果是这样，请删除 array1 中的内容并继续检查，直到 array1 为空。如果它们不存在，只需从函数返回。我正在使用Javascript

我使用经典的两个 for 循环实现了它，它给出了 o（n*2） 的运行时间。我想知道是否有任何其他有效的方法来使用 javascript 支持的任何其他数据结构执行此操作。以下是我目前的实现

for(var j = 0; j < tempArray.length; j++){
     for(var k = 0; k < this.probsSolved.length; k++){
         if(tempArray[j] == this.probsSolved[k]){
             tempArray.splice(j,1);            
             if(tempArray.length <= 0){
                 this.updateAchievements(achID);
                 this.storage.set(achKey,1);
                 return;
             }         
     }
}

问题是我必须调用每 5 秒执行此操作的函数，这对我来说看起来效率非常低。

有人可以建议一种更好的算法或数据结构，它

的性能比我可以使用的上述算法或数据结构更好，如果是这样，我将如何使用。

将array2的元素放在字典数据结构中（以确保查找快速）可能会有所帮助。

请参阅如何在 JavaScript 中进行关联数组/哈希

在伪代码中，我会像下面这样处理：

dict = {}
foreach elem in array2:
    insert elem in dict
foreeach elem in array1:
    if elem in dict:
        remove elem from array1

添加一个替代答案，因为这仍然与我们许多人相关。在寻找一种方法来优化比较两个数组的数组的脚本时，我发现了这个问题，这两个数组都有数万个键。

在我的情况下，它构成了Google脚本的一部分，并且超过了典型数据集的最大执行时间（~5分钟）。进行以下更改将执行时间减少到 10 秒以下。

低效比较（最大 i*j 迭代）：

var list1 = [1, 2, 3, 4, 5, 6];
var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
for (var i in list1) {
    for (var j in list2) {
        if (list1[i] == list2[j]) {
            alert('found ' + list1[i] + ' in both lists');
        }
    }
}

高效比较（最大 i+j 迭代）

var list1 = [1, 2, 3, 4, 5, 6];
var list2 = ['a', 'b', 'c', 3, 'd', 'e'];
var lookup = {};
for (var j in list2) {
    lookup[list2[j]] = list2[j];
}
for (var i in list1) {
    if (typeof lookup[list1[i]] != 'undefined') {
        alert('found ' + list1[i] + ' in both lists');
        break;
    } 
}

在这里找到： https://bytes.com/topic/javascript/insights/699379-optimize-loops-compare-two-arrays

基于其他答案，我编写了一个具有相同复杂性并与具有重复元素的数组兼容的 TS 解决方案。

const areArraysEquivalent = <T extends string | number | symbol>(
  a: T[],
  b: T[]
): boolean => {
  const keysAppears: Record<T, number> = {} as Record<T, number>
  for (const key of a) {
    keysAppears[key] = keysAppears[key] ? (keysAppears[key] as number) + 1 : 1
  }
  for (const key of b) {
    if (!keysAppears[key]) {
      return false
    }
    keysAppears[key] = (keysAppears[key] as number) - 1
  }
  return Object.values(keysAppears).every(value => value === 0)
}
  • ✅ N+M 的复杂度
  • ✅ 兼容重复元素
  • ⚠️ 订单不敏感
  • ❗ 仅与可以作为索引的类型兼容 （ number | string | symbol ）

游乐场链接

相关文章：