JavaScript：设置数据结构：交集

Question

我试图让两个数据集相交，但是我做不到。例如，在下面的代码中，将我的Set和mySet2相交应该得到“1”，因为它们的集合中都有值“1”。

var mySet = new Set();
var mySet2=new Set();
mySet.add(1);
mySet.add(2);
mySet.add("HELLOOOOO");
mySet2.add("hi");
mySet2.add(1);


var a = Array(mySet, mySet2);
console.log(a);

mySet.forEach(function(value) {
    console.log(value);
});


mySet2.forEach(function(value) {
    console.log(value);
});

function intersection_destructive(a, b)
{
    var result = new Array();
    while( mySet.length > 0 && mySet2.length > 0 )
    {
        if      (mySet[0] < mySet2[0] ){ mySet.shift(); }
        else if (mySet[0] > mySet2[0] ){ mySet2.shift(); }
        else /* they're equal */
        {
            result.push(mySet.shift());
            mySet2.shift();
        }
    }

    return result;
}

Set 1和Set 2中都有"1"，但我的函数（intersection_destructive）没有返回它。我不知道如何求交集，我在stackoverflow上搜索并找到了intersection_destructive，但它对我没有起作用。我还尝试了：

array1.filter(function(n) {
    return array2.indexOf(n) != -1
});

根据这个：JavaScript中数组交集的最简代码

但是当我尝试运行它时，filter 函数出现了错误。

- Snorlax

---

“Set”没有“shift”，“push”和“filter”方法？你正在使用数组的代码。 - Bergi

可能相关的链接: https://dev59.com/Xl0Z5IYBdhLWcg3wvCWd#31129482 - user663031

也许我们可以通过保持数组排序来更高效地完成任务，而不是使用集合(set)。 - Abhishek Choudhary

请参见 https://dev59.com/kXI-5IYBdhLWcg3wYnOQ#73064403。 - serv-inc

Answer 1

很遗憾，正如你所发现的，JavaScript没有原生的交集或并集操作。不过找到交集也不是特别复杂：

let a = new Set([1,2,3])
let b = new Set([1,2,4])
let intersect = new Set([...a].filter(i => b.has(i)));
console.log(...intersect)

- Kit Sunde

---

线性的n次方。由于它仍将进行迭代。 - qwerty_igor

制作集合a是没有意义的，因为您无论如何都要对其进行迭代。 - Paul Rooney

Answer 2

要获取交集，您可以迭代一个集合的项目并检查它们是否属于另一个集合。

var intersect = new Set();
for(var x of mySet1) if(mySet2.has(x)) intersect.add(x);

在ES7中，您可以使用数组推导式或生成器推导式来简化它：

var intersect = new Set((for (x of mySet1) if (mySet2.has(x)) x));

- Oriol

---

@Snorlax 抱歉，那是非标准的JS1.7语法。我已经包含了如何使用ES6和提议的ES7语法来实现它。 - Oriol

我非常希望那些推导能够创建一个迭代器，而不是一个数组。 - Bergi

@Bergi 喜欢生成器推导式吗？它会表现更好吗？ - Oriol

@Oriol：是的，这对于集合来说非常完美 :-) 省略中间数组肯定会有更好的性能，但我不能对实际实现做出任何评论。 - Bergi

由于生成器推导式未被纳入标准，所以无法接受@JacobIRR。 - Patrick Roberts

Answer 3

根据目前的第三阶段提案https://github.com/tc39/proposal-set-methods，您可以使用以下代码：

mySet.intersection(mySet2);

const set1 = new Set([1, 2, 3]);
const set2 = new Set([1, 2, 4]);

const intersect = set1.intersection(set2);
console.log(...intersect);

<script src="https://unpkg.com/core-js-bundle@3.27.1/minified.js"></script>

在那之前，您可以使用Immutable.js的Set，它启发了这个提案：

Immutable.Set(mySet).intersect(mySet2);

- serv-inc

Answer 4

交集的一种技术是取最小集合，并在其他集合中检查每个值，如果任何一个集合不包含该值，则删除该值。尽管运行时的复杂度为 O(n x m)，其中n是集合长度，m是集合数，但如果集合长度不都相同，则n很可能要小得多。

function setsIntersection(...sets) {
  if (sets.length < 1) {
    return new Set();
  }

  let min_size = sets[0].size;
  let min_set_index = 0;

  for (let i = 1; i < sets.length; i++) {
    const size = sets[i].size;
    if (size < min_size) {
      min_size = size;
      min_set_index = i;
    }
  }

  const temp_swap_set = sets[0];

  sets[0] = sets[min_set_index];
  sets[min_set_index] = temp_swap_set;

  const result = new Set(sets[min_set_index]);
  for (let i = 1; i < sets.length; i++) {
    for (const v of result) {
      if (!sets[i].has(v)) {
        result.delete(v);
      }
    }
  }
  return result;
}

- rovyko

---

这似乎是偶然运行的，因为第二个循环会跳过第一个元素并停在第一个最小基数集，但由于第一个循环错误地在集合上使用长度属性（而不是大小），所以这没有关系，因为第一个循环实际上什么也没做，我们总是使用第一个集合。 - grddev

很好的发现，但是这会失败，因为第一个集合被跳过了比较（例如{1, 100, 200}，{1, 2, 3}，{1, 2}）。我们可以通过将第一个集合与最小的集合交换来解决这个问题。 - rovyko

啊，对了，我本来也想把循环的起始值改为零，但这样也可以。 - grddev

Answer 5

你一直在尝试使用数组交集方法，但这些方法不能用于 ES6 集合。相反，使用

function intersect(...sets) {
    if (!sets.length) return new Set();
    const i = sets.reduce((m, s, i) => s.size < sets[m].size ? i : m, 0);
    const [smallest] = sets.splice(i, 1);
    const res = new Set();
    for (let val of smallest)
        if (sets.every(s => s.has(val)))
             res.add(val);
    return res;
}

- Bergi

---

找到最小值值得吗？它将具有较少的值进行迭代，但在其他值中查找可能会更慢。 - Oriol

@Oriol: 我认为是这样，因为这样可以少查找。如果我们有两组尺寸为 m 和 n 的集合，即使对于对数访问，m<<n => m * log(n) < n * log(m)（根据规范，has 是次线性的）。当然，为了获得原始速度，我可能需要将那个 every 内联。 - Bergi

Answer 6

您可以迭代该集合，并创建一个新的包含共同值的集合。

const
    intersectSets = (a, b) => {
        const c = new Set;
        a.forEach(v => b.has(v) && c.add(v));
        return c;
    },
    a = new Set([1, 2, 3]),
    b = new Set([1, 2, 4]),
    c = new Set([1, 2, 4, 5]),
    n = new Set([1, 2]);

console.log(...[a, b, c, n].reduce(intersectSets));

- Nina Scholz

Answer 7

这将适用于集合和数组。它将返回set1的类型。参数可以是混合类型。

/**
 * Returns the intersection of ES6 Set objects. i.e., returns a new set with only elements contained in all the given sets.
 * 
 * @param {Set|Array} set1 First set
 * @param {Array<Array|Set>} sets Other sets
 * @returns {Set|Array} Intersection
 */
export function intersection(set1, ...sets) {
    if(!sets.length) {
        return set1;
    }
    const tmp = [...set1].filter(x => sets.every(y => Array.isArray(y) ? y.includes(x) : y.has(x)));
    return Array.isArray(set1) ? tmp : new Set(tmp);
}

我最初是为了处理集合而构建它，但后来我意识到，仅仅为了使用一次.has方法而将数组转换为集合可能更加耗费资源，不如直接使用.includes方法。

- mpen

---

似乎需要从参数中删除spread → intersection(set1, sets) - razon

Answer 8

来自示例：intersection_destructive需要2个数组而不是2个集合。这是使用intersection_destructive示例的您的代码。

// These must be sorted arrays!
var mySet = [1,2,6];
var mySet2 = [1,2,5];

// Takes 2 Arrays
// array properties: shift
function intersection_destructive(a, b)
{
    var result = [];
    while( a.length > 0 && b.length > 0 )
    {
        if      (a[0] < b[0] ){ b.shift(); }
        else if (a[0] > b[0] ){ b.shift(); }
        else /* they're equal */
        {
            result.push(a.shift());
            b.shift();
        }
    }

    return result;
};

var result = intersection_destructive(mySet, mySet2);
console.log(result); // Output: [1,2]

- dannypaz

---

谢谢，完美地解决了问题。但是有一件事情让我困扰，为什么当我这样做时：var mySet = new Set(); var mySet2=new Set(); mySet.add(1); mySet.add(2); mySet.add("HELLOOOOO"); mySet2.add("hi"); mySet2.add(1); 结果为空，但是当我像你一样声明集合并加载数组时，它返回1？ - Snorlax

另外，如果我在两个集合中都放入6，则代码不会打印出任何相似的值，它会忽略它。 - Snorlax

'Set'对象没有'shift()'方法，这可能是为什么它返回空值的原因。对于第二个问题：如果你将数组改为[1,2,5]和[1,2,6] - 结果将会是[1,2]。根据示例，数组需要排序。如果你在数组末尾添加6，你将会收到[1]而不是预期的值。 - dannypaz

@Snorlax 请查看最近的编辑并尝试在本地运行代码。 - dannypaz

Answer 9

两个数组的交集

function intersection(arr1, arr2) {
  const set2 = new Set(arr2)
  const com = arr1.filter(a => set2.has(a))
  return [...new Set(com)]
}


console.log(intersection([1, 2, 3], [1, 2, 4])) // [ 1, 2 ]
console.log(intersection([1, 2, 4], [2, 2, 4, 4])) // [ 2, 4 ]

- Anjan Talatam

Answer 10

使用Array.filter()是一个有用的模式。您需要使用Array.from()将集合转换为数组。此外，请确保在较小的集合中进行筛选，然后再筛选到更大的集合中。 查看fiddle

var mySet = new Set();
var mySet2=new Set();
mySet.add(1);
mySet.add(2);
mySet.add("HELLOOOOO");
mySet2.add("hi");
mySet2.add(1);

console.log(intersection_destructive(mySet, mySet2));

function intersection_destructive(a, b)
{

    // filter over the shorter set and convert sets to Array's so we have filter
    if (a.length > b.length) {
        var array1 = Array.from(a);
        var array2 = Array.from(b);
    } else {
        var array1 = Array.from(b);
        var array2 = Array.from(a);
    }

    var result = array1.filter(function(n) {
        return array2.indexOf(n) != -1
    });

    return result;
}

- Victory