获取n个数组的交集
Get the intersection of n arrays
使用 ES6 的 Set，给定两个数组，我们可以像这样得到交集：
let a = new Set([1,2,3])
let b = new Set([1,2,4])
let intersect = new Set([...a].filter(i => b.has(i)));
如何得到n个数组的交集？
更新：
对于以下用例，我正在努力解决这个问题。我有一个至少包含一个元素的二维数组。
parts.forEach(part => {
intersection = new Set()
})
如何得到parts中每个元素（数组）的交集？
假设您有一些函数 function intersect(set1, set2) {...} 可以使两个集合相交，您可以使用 reduce:
获得集合数组的交集
function intersect(a, b) {
return new Set(a.filter(i => b.has(i)));
}
var sets = [new Set([1,2,3]), ...];
var intersection = sets.reduce(intersect);
您可以使用 Array 方法的组合创建一个 intersect 辅助函数，例如 .filter()、.map() 和 .every()。
此答案的灵感来自 Xufox 的上述评论，他提到在 filter 谓词中使用 Array#every。
function intersect (first = [], ...rest) {
rest = rest.map(array => new Set(array))
return first.filter(e => rest.every(set => set.has(e)))
}
let parts = [
[1, 2, 3],
[1, 2, 4],
[1, 5, 2]
]
console.log(
intersect(...parts)
)
ES6还有一个while
这是一种很容易因处理量过多而导致长时间滞后的函数类型。毫无疑问甚至优先使用 ES6 和数组方法（如 reduce、filter 等）而不是简单的老式循环（如 while 和 for）更是如此。
计算多个集合的交集时，如果发现某个项目不属于交集，则每次迭代完成的工作量应该会减少。因为 forEach 不能中断，所以您仍然被迫迭代所有元素。添加一些代码以避免在发现当前项目不属于时进行搜索可以提高性能，但这是一个真正的问题。
还有一种趋势是创建全新的数据集，只是为了从数组、集合或映射中删除单个项目。这是一个非常糟糕的习惯，随着人们采用 ES5 方式，我看到越来越多。
获取n个集合的交集。
所以对于手头的问题。找到许多集合的交集。
解决方案 B
典型的 ES6 解决方案
function intersectB(firstSet, ...sets) {
// function to intercept two sets
var intersect = (a,b) => {
return new Set([...a].filter(item => b.has(item)))
};
// iterate all sets comparing the first set to each.
sets.forEach(sItem => firstSet = intersect(firstSet, sItem));
// return the result.
return firstSet;
}
var sets = [new Set([1,2,3,4]), new Set([1,2,4,6,8]), new Set([1,3,4,6,8])];
var inter = intersectB(...sets);
console.log([...inter]);
效果很好，简单的测试用例执行时间不到一毫秒。但在我的书中，这是一个效率低下的内存占用结，几乎在每一行创建数组和集合，并在结果已知时迭代整个集合。
让我们再做一些工作。 100 套，最多 10000 个项目，超过 10 个测试，每个测试都有不同数量的匹配项目。大多数拦截将 return 空集。
警告会导致页面挂起整整一秒...:(
// Create a set of numbers from 0 and < count
// With a odds for any number occurring to be odds
// return as a new set;
function createLargeSet(count,odds){
var numbers = new Set();
while(count-- > 0){
if(Math.random() < odds){
numbers.add(count);
}
}
return numbers;
}
// create a array of large sets
function bigArrayOfSets(setCount,setMaxSize,odds){
var bigSets = [];
for(var i = 0; i < setCount; i ++){
bigSets.push(createLargeSet(setMaxSize,odds));
}
return bigSets;
}
function intersectB(firstSet, ...sets) {
var intersect = (a,b) => {
return new Set([...a].filter(item => b.has(item)))
};
sets.forEach(sItem => firstSet = intersect(firstSet, sItem));
return firstSet;
}
var testSets = [];
for(var i = 0.1; i <= 1; i += 0.1){
testSets.push(bigArrayOfSets(100,10000,i));
}
var now = performance.now();
testSets.forEach(testDat => intersectB(...testDat));
var time = performance.now() - now;
console.log("Execution time : " + time);
解决方案 A
更好的方法，虽然不花哨但效率更高。
function intersectA(firstSet,...sets) {
var count = sets.length;
var result = new Set(firstSet); // Only create one copy of the set
firstSet.forEach(item => {
var i = count;
var allHave = true;
while(i--){
allHave = sets[i].has(item)
if(!allHave) { break } // loop only until item fails test
}
if(!allHave){
result.delete(item); // remove item from set rather than
// create a whole new set
}
})
return result;
}
比较
所以现在让我们比较两者，如果您运气好，尝试猜测性能差异，这是衡量您对 Javascript 执行的理解的好方法。
// Create a set of numbers from 0 and < count
// With a odds for any number occurring to be odds
// return as a new set;
function createLargeSet(count,odds){
var numbers = new Set();
while(count-- > 0){
if(Math.random() < odds){
numbers.add(count);
}
}
return numbers;
}
// create a array of large sets
function bigArrayOfSets(setCount,setMaxSize,odds){
var bigSets = [];
for(var i = 0; i < setCount; i ++){
bigSets.push(createLargeSet(setMaxSize,odds));
}
return bigSets;
}
function intersectA(firstSet,...sets) {
var count = sets.length;
var result = new Set(firstSet); // Only create one copy of the set
firstSet.forEach(item => {
var i = count;
var allHave = true;
while(i--){
allHave = sets[i].has(item)
if(!allHave) { break } // loop only until item fails test
}
if(!allHave){
result.delete(item); // remove item from set rather than
// create a whole new set
}
})
return result;
}
function intersectB(firstSet, ...sets) {
var intersect = (a,b) => {
return new Set([...a].filter(item => b.has(item)))
};
sets.forEach(sItem => firstSet = intersect(firstSet, sItem));
return firstSet;
}
var testSets = [];
for(var i = 0.1; i <= 1; i += 0.1){
testSets.push(bigArrayOfSets(100,10000,i));
}
var now = performance.now();
testSets.forEach(testDat => intersectB(...testDat));
var time = performance.now() - now;
console.log("Execution time 'intersectB' : " + time);
var now = performance.now();
testSets.forEach(testDat => intersectA(...testDat));
var time = performance.now() - now;
console.log("Execution time 'intersectA' : " + time);
如您所见，使用简单的 while 循环可能不如使用过滤器那么酷，但性能优势是巨大的，下次您编写完美的 3 行 ES6 数组操作函数时要记住这一点。不要忘记 for 和 while.
好的，我想执行数组交集的最有效方法是使用 Map 或 Hash 对象。在这里，我测试了 1000 个数组，每个数组在 1..175 中有约 1000 个随机整数项用于交集。不到100毫秒得到结果
function setIntersection(a){
var m = new Map(),
r = new Set(),
l = a.length;
a.forEach(sa => new Set(sa).forEach(n => m.has(n) ? m.set(n,m.get(n)+1)
: m.set(n,1)));
m.forEach((v,k) => v === l && r.add(k));
return r;
}
var testSets = Array(1000).fill().map(_ => Array(1000).fill().map(_ => ~~(Math.random()*175+1)));
console.time("int");
result = setIntersection(testSets);
console.timeEnd("int");
console.log(JSON.stringify([...result]));
求交 n 个数组的最有效算法是 fast_array_intersect 中实现的算法。它在 O(n) 中运行，其中 n 是所有数组中元素的总数。
基本原理很简单：遍历所有数组，存储您在地图中看到每个元素的次数。然后过滤掉最小的数组，到return只有所有数组中都见过的元素。 (source code).
您可以通过简单的方式使用该库：
import intersect from 'fast_array_intersect'
intersect([[1,2,3], [1,2,6]]) // --> [1,2]
使用 ES6 的 Set，给定两个数组，我们可以像这样得到交集：
let a = new Set([1,2,3])
let b = new Set([1,2,4])
let intersect = new Set([...a].filter(i => b.has(i)));
如何得到n个数组的交集？
更新：
对于以下用例，我正在努力解决这个问题。我有一个至少包含一个元素的二维数组。
parts.forEach(part => {
intersection = new Set()
})
如何得到parts中每个元素（数组）的交集？
假设您有一些函数 function intersect(set1, set2) {...} 可以使两个集合相交，您可以使用 reduce:
function intersect(a, b) {
return new Set(a.filter(i => b.has(i)));
}
var sets = [new Set([1,2,3]), ...];
var intersection = sets.reduce(intersect);
您可以使用 Array 方法的组合创建一个 intersect 辅助函数，例如 .filter()、.map() 和 .every()。
此答案的灵感来自 Xufox 的上述评论，他提到在 filter 谓词中使用 Array#every。
function intersect (first = [], ...rest) {
rest = rest.map(array => new Set(array))
return first.filter(e => rest.every(set => set.has(e)))
}
let parts = [
[1, 2, 3],
[1, 2, 4],
[1, 5, 2]
]
console.log(
intersect(...parts)
)
ES6还有一个while
这是一种很容易因处理量过多而导致长时间滞后的函数类型。毫无疑问甚至优先使用 ES6 和数组方法（如 reduce、filter 等）而不是简单的老式循环（如 while 和 for）更是如此。
计算多个集合的交集时，如果发现某个项目不属于交集，则每次迭代完成的工作量应该会减少。因为 forEach 不能中断，所以您仍然被迫迭代所有元素。添加一些代码以避免在发现当前项目不属于时进行搜索可以提高性能，但这是一个真正的问题。
还有一种趋势是创建全新的数据集，只是为了从数组、集合或映射中删除单个项目。这是一个非常糟糕的习惯，随着人们采用 ES5 方式，我看到越来越多。
获取n个集合的交集。
所以对于手头的问题。找到许多集合的交集。
解决方案 B
典型的 ES6 解决方案
function intersectB(firstSet, ...sets) {
// function to intercept two sets
var intersect = (a,b) => {
return new Set([...a].filter(item => b.has(item)))
};
// iterate all sets comparing the first set to each.
sets.forEach(sItem => firstSet = intersect(firstSet, sItem));
// return the result.
return firstSet;
}
var sets = [new Set([1,2,3,4]), new Set([1,2,4,6,8]), new Set([1,3,4,6,8])];
var inter = intersectB(...sets);
console.log([...inter]);
效果很好，简单的测试用例执行时间不到一毫秒。但在我的书中，这是一个效率低下的内存占用结，几乎在每一行创建数组和集合，并在结果已知时迭代整个集合。
让我们再做一些工作。 100 套，最多 10000 个项目，超过 10 个测试，每个测试都有不同数量的匹配项目。大多数拦截将 return 空集。
警告会导致页面挂起整整一秒...:(
// Create a set of numbers from 0 and < count
// With a odds for any number occurring to be odds
// return as a new set;
function createLargeSet(count,odds){
var numbers = new Set();
while(count-- > 0){
if(Math.random() < odds){
numbers.add(count);
}
}
return numbers;
}
// create a array of large sets
function bigArrayOfSets(setCount,setMaxSize,odds){
var bigSets = [];
for(var i = 0; i < setCount; i ++){
bigSets.push(createLargeSet(setMaxSize,odds));
}
return bigSets;
}
function intersectB(firstSet, ...sets) {
var intersect = (a,b) => {
return new Set([...a].filter(item => b.has(item)))
};
sets.forEach(sItem => firstSet = intersect(firstSet, sItem));
return firstSet;
}
var testSets = [];
for(var i = 0.1; i <= 1; i += 0.1){
testSets.push(bigArrayOfSets(100,10000,i));
}
var now = performance.now();
testSets.forEach(testDat => intersectB(...testDat));
var time = performance.now() - now;
console.log("Execution time : " + time);
解决方案 A
更好的方法，虽然不花哨但效率更高。
function intersectA(firstSet,...sets) {
var count = sets.length;
var result = new Set(firstSet); // Only create one copy of the set
firstSet.forEach(item => {
var i = count;
var allHave = true;
while(i--){
allHave = sets[i].has(item)
if(!allHave) { break } // loop only until item fails test
}
if(!allHave){
result.delete(item); // remove item from set rather than
// create a whole new set
}
})
return result;
}
比较
所以现在让我们比较两者，如果您运气好，尝试猜测性能差异，这是衡量您对 Javascript 执行的理解的好方法。
// Create a set of numbers from 0 and < count
// With a odds for any number occurring to be odds
// return as a new set;
function createLargeSet(count,odds){
var numbers = new Set();
while(count-- > 0){
if(Math.random() < odds){
numbers.add(count);
}
}
return numbers;
}
// create a array of large sets
function bigArrayOfSets(setCount,setMaxSize,odds){
var bigSets = [];
for(var i = 0; i < setCount; i ++){
bigSets.push(createLargeSet(setMaxSize,odds));
}
return bigSets;
}
function intersectA(firstSet,...sets) {
var count = sets.length;
var result = new Set(firstSet); // Only create one copy of the set
firstSet.forEach(item => {
var i = count;
var allHave = true;
while(i--){
allHave = sets[i].has(item)
if(!allHave) { break } // loop only until item fails test
}
if(!allHave){
result.delete(item); // remove item from set rather than
// create a whole new set
}
})
return result;
}
function intersectB(firstSet, ...sets) {
var intersect = (a,b) => {
return new Set([...a].filter(item => b.has(item)))
};
sets.forEach(sItem => firstSet = intersect(firstSet, sItem));
return firstSet;
}
var testSets = [];
for(var i = 0.1; i <= 1; i += 0.1){
testSets.push(bigArrayOfSets(100,10000,i));
}
var now = performance.now();
testSets.forEach(testDat => intersectB(...testDat));
var time = performance.now() - now;
console.log("Execution time 'intersectB' : " + time);
var now = performance.now();
testSets.forEach(testDat => intersectA(...testDat));
var time = performance.now() - now;
console.log("Execution time 'intersectA' : " + time);
如您所见，使用简单的 while 循环可能不如使用过滤器那么酷，但性能优势是巨大的，下次您编写完美的 3 行 ES6 数组操作函数时要记住这一点。不要忘记 for 和 while.
好的，我想执行数组交集的最有效方法是使用 Map 或 Hash 对象。在这里，我测试了 1000 个数组，每个数组在 1..175 中有约 1000 个随机整数项用于交集。不到100毫秒得到结果
function setIntersection(a){
var m = new Map(),
r = new Set(),
l = a.length;
a.forEach(sa => new Set(sa).forEach(n => m.has(n) ? m.set(n,m.get(n)+1)
: m.set(n,1)));
m.forEach((v,k) => v === l && r.add(k));
return r;
}
var testSets = Array(1000).fill().map(_ => Array(1000).fill().map(_ => ~~(Math.random()*175+1)));
console.time("int");
result = setIntersection(testSets);
console.timeEnd("int");
console.log(JSON.stringify([...result]));
求交 n 个数组的最有效算法是 fast_array_intersect 中实现的算法。它在 O(n) 中运行，其中 n 是所有数组中元素的总数。
基本原理很简单：遍历所有数组，存储您在地图中看到每个元素的次数。然后过滤掉最小的数组，到return只有所有数组中都见过的元素。 (source code).
您可以通过简单的方式使用该库：
import intersect from 'fast_array_intersect'
intersect([[1,2,3], [1,2,6]]) // --> [1,2]