[removed] Set Data Structure: intersect

问题:

Trying to get two data sets to intersect but I can't do it :(. For example, in my code below, intersecting mySet and mySet2 should yield "1" since they both have a value of "1" in their set.

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 and Set 2 both have "1" in it but my function (intersection_destructive) doesn't return it. I'm not sure how to intersect them, I searched stackoverflow and found intersection_destructive but it didn't work for me, I also tried:

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

as per this: Simplest code for array intersection in javascript

but I get an error on "filter" when I try to run it.

回答1:

Sadly as you've figured out there's no native intersection or union operations. It's not terribly complex to find the intersection though:

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

回答2:

To get the intersection, you can iterate the items of a set and check if they belong to the other one:

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

In ES7 you can simplify it with array comprehensions or generator comprehensions:

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

回答3:

You have been trying array intersections methods. You cannot use them on ES6 sets. Instead, use

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;
}

回答4:

From the example: intersection_destructive takes 2 ARRAYS not 2 SETS. Here is your code working with the intersection_destructive example.

// 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]

回答5:

This will work on both Sets and Arrays. It will return whatever the type of set1 is. Arguments can be mixed types.

/**
 * 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);
}

I built it for working with Sets, but then I realized it's probably more expensive to convert an array into a set just so I can use .has on it once than to just use .includes.

回答6:

To use the Array.filter() is a useful pattern. You need to convert your sets to array's using Array.from(). Also make sure that you filter through smaller set into the bigger one. see 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;
}