What's the simplest, library-free code for implementing array intersections in javascript? I want to write
intersection([1,2,3], [2,3,4,5])
and get
[2, 3]
This question is related to
javascript
data-structures
intersection
function getIntersection(arr1, arr2){
var result = [];
arr1.forEach(function(elem){
arr2.forEach(function(elem2){
if(elem === elem2){
result.push(elem);
}
});
});
return result;
}
getIntersection([1,2,3], [2,3,4,5]); // [ 2, 3 ]
I extended tarulen's answer to work with any number of arrays. It also should work with non-integer values.
function intersect() {
const last = arguments.length - 1;
var seen={};
var result=[];
for (var i = 0; i < last; i++) {
for (var j = 0; j < arguments[i].length; j++) {
if (seen[arguments[i][j]]) {
seen[arguments[i][j]] += 1;
}
else if (!i) {
seen[arguments[i][j]] = 1;
}
}
}
for (var i = 0; i < arguments[last].length; i++) {
if ( seen[arguments[last][i]] === last)
result.push(arguments[last][i]);
}
return result;
}
"filter" and "indexOf" aren't supported on Array in IE. How about this:
var array1 = [1, 2, 3];
var array2 = [2, 3, 4, 5];
var intersection = [];
for (i in array1) {
for (j in array2) {
if (array1[i] == array2[j]) intersection.push(array1[i]);
}
}
Here's a very naive implementation I'm using. It's non-destructive and also makes sure not to duplicate entires.
Array.prototype.contains = function(elem) {
return(this.indexOf(elem) > -1);
};
Array.prototype.intersect = function( array ) {
// this is naive--could use some optimization
var result = [];
for ( var i = 0; i < this.length; i++ ) {
if ( array.contains(this[i]) && !result.contains(this[i]) )
result.push( this[i] );
}
return result;
}
My contribution in ES6 terms. In general it finds the intersection of an array with indefinite number of arrays provided as arguments.
Array.prototype.intersect = function(...a) {_x000D_
return [this,...a].reduce((p,c) => p.filter(e => c.includes(e)));_x000D_
}_x000D_
var arrs = [[0,2,4,6,8],[4,5,6,7],[4,6]],_x000D_
arr = [0,1,2,3,4,5,6,7,8,9];_x000D_
_x000D_
document.write("<pre>" + JSON.stringify(arr.intersect(...arrs)) + "</pre>");
_x000D_
.reduce
to build a map, and .filter
to find the intersection. delete
within the .filter
allows us to treat the second array as though it's a unique set.
function intersection (a, b) {
var seen = a.reduce(function (h, k) {
h[k] = true;
return h;
}, {});
return b.filter(function (k) {
var exists = seen[k];
delete seen[k];
return exists;
});
}
I find this approach pretty easy to reason about. It performs in constant time.
If your arrays are sorted, this should run in O(n), where n is min( a.length, b.length )
function intersect_1d( a, b ){
var out=[], ai=0, bi=0, acurr, bcurr, last=Number.MIN_SAFE_INTEGER;
while( ( acurr=a[ai] )!==undefined && ( bcurr=b[bi] )!==undefined ){
if( acurr < bcurr){
if( last===acurr ){
out.push( acurr );
}
last=acurr;
ai++;
}
else if( acurr > bcurr){
if( last===bcurr ){
out.push( bcurr );
}
last=bcurr;
bi++;
}
else {
out.push( acurr );
last=acurr;
ai++;
bi++;
}
}
return out;
}
Destructive seems simplest, especially if we can assume the input is sorted:
/* destructively finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
* State of input arrays is undefined when
* the function returns. They should be
* (prolly) be dumped.
*
* Should have O(n) operations, where n is
* n = MIN(a.length, b.length)
*/
function intersection_destructive(a, b)
{
var result = [];
while( a.length > 0 && b.length > 0 )
{
if (a[0] < b[0] ){ a.shift(); }
else if (a[0] > b[0] ){ b.shift(); }
else /* they're equal */
{
result.push(a.shift());
b.shift();
}
}
return result;
}
Non-destructive has to be a hair more complicated, since we’ve got to track indices:
/* finds the intersection of
* two arrays in a simple fashion.
*
* PARAMS
* a - first array, must already be sorted
* b - second array, must already be sorted
*
* NOTES
*
* Should have O(n) operations, where n is
* n = MIN(a.length(), b.length())
*/
function intersect_safe(a, b)
{
var ai=0, bi=0;
var result = [];
while( ai < a.length && bi < b.length )
{
if (a[ai] < b[bi] ){ ai++; }
else if (a[ai] > b[bi] ){ bi++; }
else /* they're equal */
{
result.push(a[ai]);
ai++;
bi++;
}
}
return result;
}
How about just using associative arrays?
function intersect(a, b) {
var d1 = {};
var d2 = {};
var results = [];
for (var i = 0; i < a.length; i++) {
d1[a[i]] = true;
}
for (var j = 0; j < b.length; j++) {
d2[b[j]] = true;
}
for (var k in d1) {
if (d2[k])
results.push(k);
}
return results;
}
edit:
// new version
function intersect(a, b) {
var d = {};
var results = [];
for (var i = 0; i < b.length; i++) {
d[b[i]] = true;
}
for (var j = 0; j < a.length; j++) {
if (d[a[j]])
results.push(a[j]);
}
return results;
}
function intersection(A,B){
var result = new Array();
for (i=0; i<A.length; i++) {
for (j=0; j<B.length; j++) {
if (A[i] == B[j] && $.inArray(A[i],result) == -1) {
result.push(A[i]);
}
}
}
return result;
}
A functional approach must consider using only pure functions without side effects, each of which is only concerned with a single job.
These restrictions enhance the composability and reusability of the functions involved.
// small, reusable auxiliary functions_x000D_
_x000D_
const createSet = xs => new Set(xs);_x000D_
const filter = f => xs => xs.filter(apply(f));_x000D_
const apply = f => x => f(x);_x000D_
_x000D_
_x000D_
// intersection_x000D_
_x000D_
const intersect = xs => ys => {_x000D_
const zs = createSet(ys);_x000D_
return filter(x => zs.has(x)_x000D_
? true_x000D_
: false_x000D_
) (xs);_x000D_
};_x000D_
_x000D_
_x000D_
// mock data_x000D_
_x000D_
const xs = [1,2,2,3,4,5];_x000D_
const ys = [0,1,2,3,3,3,6,7,8,9];_x000D_
_x000D_
_x000D_
// run it_x000D_
_x000D_
console.log( intersect(xs) (ys) );
_x000D_
Please note that the native Set
type is used, which has an advantageous
lookup performance.
Obviously repeatedly occurring items from the first Array
are preserved, while the second Array
is de-duplicated. This may be or may be not the desired behavior. If you need a unique result just apply dedupe
to the first argument:
// auxiliary functions_x000D_
_x000D_
const apply = f => x => f(x);_x000D_
const comp = f => g => x => f(g(x));_x000D_
const afrom = apply(Array.from);_x000D_
const createSet = xs => new Set(xs);_x000D_
const filter = f => xs => xs.filter(apply(f));_x000D_
_x000D_
_x000D_
// intersection_x000D_
_x000D_
const intersect = xs => ys => {_x000D_
const zs = createSet(ys);_x000D_
return filter(x => zs.has(x)_x000D_
? true_x000D_
: false_x000D_
) (xs);_x000D_
};_x000D_
_x000D_
_x000D_
// de-duplication_x000D_
_x000D_
const dedupe = comp(afrom) (createSet);_x000D_
_x000D_
_x000D_
// mock data_x000D_
_x000D_
const xs = [1,2,2,3,4,5];_x000D_
const ys = [0,1,2,3,3,3,6,7,8,9];_x000D_
_x000D_
_x000D_
// unique result_x000D_
_x000D_
console.log( intersect(dedupe(xs)) (ys) );
_x000D_
Array
sIf you want to compute the intersection of an arbitrarily number of Array
s just compose intersect
with foldl
. Here is a convenience function:
// auxiliary functions_x000D_
_x000D_
const apply = f => x => f(x);_x000D_
const uncurry = f => (x, y) => f(x) (y);_x000D_
const createSet = xs => new Set(xs);_x000D_
const filter = f => xs => xs.filter(apply(f));_x000D_
const foldl = f => acc => xs => xs.reduce(uncurry(f), acc);_x000D_
_x000D_
_x000D_
// intersection_x000D_
_x000D_
const intersect = xs => ys => {_x000D_
const zs = createSet(ys);_x000D_
return filter(x => zs.has(x)_x000D_
? true_x000D_
: false_x000D_
) (xs);_x000D_
};_x000D_
_x000D_
_x000D_
// intersection of an arbitrarily number of Arrays_x000D_
_x000D_
const intersectn = (head, ...tail) => foldl(intersect) (head) (tail);_x000D_
_x000D_
_x000D_
// mock data_x000D_
_x000D_
const xs = [1,2,2,3,4,5];_x000D_
const ys = [0,1,2,3,3,3,6,7,8,9];_x000D_
const zs = [0,1,2,3,4,5,6];_x000D_
_x000D_
_x000D_
// run_x000D_
_x000D_
console.log( intersectn(xs, ys, zs) );
_x000D_
For simplicity:
// Usage
const intersection = allLists
.reduce(intersect, allValues)
.reduce(removeDuplicates, []);
// Implementation
const intersect = (intersection, list) =>
intersection.filter(item =>
list.some(x => x === item));
const removeDuplicates = (uniques, item) =>
uniques.includes(item) ? uniques : uniques.concat(item);
// Example Data
const somePeople = [bob, doug, jill];
const otherPeople = [sarah, bob, jill];
const morePeople = [jack, jill];
const allPeople = [...somePeople, ...otherPeople, ...morePeople];
const allGroups = [somePeople, otherPeople, morePeople];
// Example Usage
const intersection = allGroups
.reduce(intersect, allPeople)
.reduce(removeDuplicates, []);
intersection; // [jill]
Benefits:
Drawbacks:
You wouldn't want to use this for 3D engine or kernel work, but if you have problems getting this to run in an event-based app, your design has bigger problems.
With some restrictions on your data, you can do it in linear time!
For positive integers: use an array mapping the values to a "seen/not seen" boolean.
function intersectIntegers(array1,array2) {
var seen=[],
result=[];
for (var i = 0; i < array1.length; i++) {
seen[array1[i]] = true;
}
for (var i = 0; i < array2.length; i++) {
if ( seen[array2[i]])
result.push(array2[i]);
}
return result;
}
There is a similar technique for objects: take a dummy key, set it to "true" for each element in array1, then look for this key in elements of array2. Clean up when you're done.
function intersectObjects(array1,array2) {
var result=[];
var key="tmpKey_intersect"
for (var i = 0; i < array1.length; i++) {
array1[i][key] = true;
}
for (var i = 0; i < array2.length; i++) {
if (array2[i][key])
result.push(array2[i]);
}
for (var i = 0; i < array1.length; i++) {
delete array1[i][key];
}
return result;
}
Of course you need to be sure the key didn't appear before, otherwise you'll be destroying your data...
Something like this, Not tested well though.
function intersection(x,y){
x.sort();y.sort();
var i=j=0;ret=[];
while(i<x.length && j<y.length){
if(x[i]<y[j])i++;
else if(y[j]<x[i])j++;
else {
ret.push(x[i]);
i++,j++;
}
}
return ret;
}
alert(intersection([1,2,3], [2,3,4,5]));
PS:The algorithm only intended for Numbers and Normal Strings, intersection of arbitary object arrays may not work.
Building on Anon's excellent answer, this one returns the intersection of two or more arrays.
function arrayIntersect(arrayOfArrays)
{
var arrayCopy = arrayOfArrays.slice(),
baseArray = arrayCopy.pop();
return baseArray.filter(function(item) {
return arrayCopy.every(function(itemList) {
return itemList.indexOf(item) !== -1;
});
});
}
This is probably the simplest one, besides list1.filter(n => list2.includes(n))
var list1 = ['bread', 'ice cream', 'cereals', 'strawberry', 'chocolate']_x000D_
var list2 = ['bread', 'cherry', 'ice cream', 'oats']_x000D_
_x000D_
function check_common(list1, list2){_x000D_
_x000D_
list3 = []_x000D_
for (let i=0; i<list1.length; i++){_x000D_
_x000D_
for (let j=0; j<list2.length; j++){ _x000D_
if (list1[i] === list2[j]){_x000D_
list3.push(list1[i]); _x000D_
} _x000D_
}_x000D_
_x000D_
}_x000D_
return list3_x000D_
_x000D_
}_x000D_
_x000D_
check_common(list1, list2) // ["bread", "ice cream"]
_x000D_
intersection of N arrays in coffeescript
getIntersection: (arrays) ->
if not arrays.length
return []
a1 = arrays[0]
for a2 in arrays.slice(1)
a = (val for val in a1 when val in a2)
a1 = a
return a1.unique()
Using jQuery:
var a = [1,2,3];
var b = [2,3,4,5];
var c = $(b).not($(b).not(a));
alert(c);
not about efficiency, but easy to follow, here is an example of unions and intersections of sets, it handles arrays of sets and sets of sets.
http://jsfiddle.net/zhulien/NF68T/
// process array [element, element...], if allow abort ignore the result
function processArray(arr_a, cb_a, blnAllowAbort_a)
{
var arrResult = [];
var blnAborted = false;
var intI = 0;
while ((intI < arr_a.length) && (blnAborted === false))
{
if (blnAllowAbort_a)
{
blnAborted = cb_a(arr_a[intI]);
}
else
{
arrResult[intI] = cb_a(arr_a[intI]);
}
intI++;
}
return arrResult;
}
// process array of operations [operation,arguments...]
function processOperations(arrOperations_a)
{
var arrResult = [];
var fnOperationE;
for(var intI = 0, intR = 0; intI < arrOperations_a.length; intI+=2, intR++)
{
var fnOperation = arrOperations_a[intI+0];
var fnArgs = arrOperations_a[intI+1];
if (fnArgs === undefined)
{
arrResult[intR] = fnOperation();
}
else
{
arrResult[intR] = fnOperation(fnArgs);
}
}
return arrResult;
}
// return whether an element exists in an array
function find(arr_a, varElement_a)
{
var blnResult = false;
processArray(arr_a, function(varToMatch_a)
{
var blnAbort = false;
if (varToMatch_a === varElement_a)
{
blnResult = true;
blnAbort = true;
}
return blnAbort;
}, true);
return blnResult;
}
// return the union of all sets
function union(arr_a)
{
var arrResult = [];
var intI = 0;
processArray(arr_a, function(arrSet_a)
{
processArray(arrSet_a, function(varElement_a)
{
// if the element doesn't exist in our result
if (find(arrResult, varElement_a) === false)
{
// add it
arrResult[intI] = varElement_a;
intI++;
}
});
});
return arrResult;
}
// return the intersection of all sets
function intersection(arr_a)
{
var arrResult = [];
var intI = 0;
// for each set
processArray(arr_a, function(arrSet_a)
{
// every number is a candidate
processArray(arrSet_a, function(varCandidate_a)
{
var blnCandidate = true;
// for each set
processArray(arr_a, function(arrSet_a)
{
// check that the candidate exists
var blnFoundPart = find(arrSet_a, varCandidate_a);
// if the candidate does not exist
if (blnFoundPart === false)
{
// no longer a candidate
blnCandidate = false;
}
});
if (blnCandidate)
{
// if the candidate doesn't exist in our result
if (find(arrResult, varCandidate_a) === false)
{
// add it
arrResult[intI] = varCandidate_a;
intI++;
}
}
});
});
return arrResult;
}
var strOutput = ''
var arrSet1 = [1,2,3];
var arrSet2 = [2,5,6];
var arrSet3 = [7,8,9,2];
// return the union of the sets
strOutput = union([arrSet1, arrSet2, arrSet3]);
alert(strOutput);
// return the intersection of 3 sets
strOutput = intersection([arrSet1, arrSet2, arrSet3]);
alert(strOutput);
// of 3 sets of sets, which set is the intersecting set
strOutput = processOperations([intersection,[[arrSet1, arrSet2], [arrSet2], [arrSet2, arrSet3]]]);
alert(strOutput);
If you need to have it handle intersecting multiple arrays:
const intersect = (a1, a2, ...rest) => {
const a12 = a1.filter(value => a2.includes(value))
if (rest.length === 0) { return a12; }
return intersect(a12, ...rest);
};
console.log(intersect([1,2,3,4,5], [1,2], [1, 2, 3,4,5], [2, 10, 1]))
_x000D_
I have written an intesection function which can even detect intersection of array of objects based on particular property of those objects.
For instance,
if arr1 = [{id: 10}, {id: 20}]
and arr2 = [{id: 20}, {id: 25}]
and we want intersection based on the id
property, then the output should be :
[{id: 20}]
As such, the function for the same (note: ES6 code) is :
const intersect = (arr1, arr2, accessors = [v => v, v => v]) => {
const [fn1, fn2] = accessors;
const set = new Set(arr2.map(v => fn2(v)));
return arr1.filter(value => set.has(fn1(value)));
};
and you can call the function as:
intersect(arr1, arr2, [elem => elem.id, elem => elem.id])
Also note: this function finds intersection considering the first array is the primary array and thus the intersection result will be that of the primary array.
Create an Object using one array and loop through the second array to check if the value exists as key.
function intersection(arr1, arr2) {
var myObj = {};
var myArr = [];
for (var i = 0, len = arr1.length; i < len; i += 1) {
if(myObj[arr1[i]]) {
myObj[arr1[i]] += 1;
} else {
myObj[arr1[i]] = 1;
}
}
for (var j = 0, len = arr2.length; j < len; j += 1) {
if(myObj[arr2[j]] && myArr.indexOf(arr2[j]) === -1) {
myArr.push(arr2[j]);
}
}
return myArr;
}
If your environment supports ECMAScript 6 Set, one simple and supposedly efficient (see specification link) way:
function intersect(a, b) {
var setA = new Set(a);
var setB = new Set(b);
var intersection = new Set([...setA].filter(x => setB.has(x)));
return Array.from(intersection);
}
Shorter, but less readable (also without creating the additional intersection Set
):
function intersect(a, b) {
var setB = new Set(b);
return [...new Set(a)].filter(x => setB.has(x));
}
Note that when using sets you will only get distinct values, thus new Set([1, 2, 3, 3]).size
evaluates to 3
.
This is a modern and simple ES6 way to do it that is also very flexible. It lets you specify multiple arrays as the arrays to compare the subject array to, and can work in both inclusive and exclusive mode.
// =======================================
// The function
// =======================================
function assoc(subjectArray, otherArrays, { mustBeInAll = true } = {}) {
return subjectArray.filter((subjectItem) => {
if (mustBeInAll) {
return otherArrays.every((otherArray) =>
otherArray.includes(subjectItem)
);
} else {
return otherArrays.some((otherArray) => otherArray.includes(subjectItem));
}
});
}
// =======================================
// The usage
// =======================================
const cheeseList = ["stilton", "edam", "cheddar", "brie"];
const foodListCollection = [
["cakes", "ham", "stilton"],
["juice", "wine", "brie", "bread", "stilton"]
];
// Output will be: ['stilton', 'brie']
const inclusive = assoc(cheeseList, foodListCollection, { mustBeInAll: false }),
// Output will be: ['stilton']
const exclusive = assoc(cheeseList, foodListCollection, { mustBeInAll: true })
Live example: https://codesandbox.io/s/zealous-butterfly-h7dgf?fontsize=14&hidenavigation=1&theme=dark
Another indexed approach able to process any number of arrays at once:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = 0;
index[v]++;
};
};
var retv = [];
for (var i in index) {
if (index[i] == arrLength) retv.push(i);
};
return retv;
};
It works only for values that can be evaluated as strings and you should pass them as an array like:
intersect ([arr1, arr2, arr3...]);
...but it transparently accepts objects as parameter or as any of the elements to be intersected (always returning array of common values). Examples:
intersect ({foo: [1, 2, 3, 4], bar: {a: 2, j:4}}); // [2, 4]
intersect ([{x: "hello", y: "world"}, ["hello", "user"]]); // ["hello"]
EDIT: I just noticed that this is, in a way, slightly buggy.
That is: I coded it thinking that input arrays cannot itself contain repetitions (as provided example doesn't).
But if input arrays happen to contain repetitions, that would produce wrong results. Example (using below implementation):
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]);
// Expected: [ '1' ]
// Actual: [ '1', '3' ]
Fortunately this is easy to fix by simply adding second level indexing. That is:
Change:
if (index[v] === undefined) index[v] = 0;
index[v]++;
by:
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
...and:
if (index[i] == arrLength) retv.push(i);
by:
if (Object.keys(index[i]).length == arrLength) retv.push(i);
Complete example:
// Calculate intersection of multiple array or object values.
function intersect (arrList) {
var arrLength = Object.keys(arrList).length;
// (Also accepts regular objects as input)
var index = {};
for (var i in arrList) {
for (var j in arrList[i]) {
var v = arrList[i][j];
if (index[v] === undefined) index[v] = {};
index[v][i] = true; // Mark as present in i input.
};
};
var retv = [];
for (var i in index) {
if (Object.keys(index[i]).length == arrLength) retv.push(i);
};
return retv;
};
intersect ([[1, 3, 4, 6, 3], [1, 8, 99]]); // [ '1' ]
Hope this Helps for all versions.
function diffArray(arr1, arr2) {
var newArr = [];
var large = arr1.length>=arr2.length?arr1:arr2;
var small = JSON.stringify(large) == JSON.stringify(arr1)?arr2:arr1;
for(var i=0;i<large.length;i++){
var copyExists = false;
for(var j =0;j<small.length;j++){
if(large[i]==small[j]){
copyExists= true;
break;
}
}
if(!copyExists)
{
newArr.push(large[i]);
}
}
for(var i=0;i<small.length;i++){
var copyExists = false;
for(var j =0;j<large.length;j++){
if(large[j]==small[i]){
copyExists= true;
break;
}
}
if(!copyExists)
{
newArr.push(small[i]);
}
}
return newArr;
}
Using Underscore.js or lodash.js
_.intersection( [0,345,324] , [1,0,324] ) // gives [0,324]
For arrays containing only strings or numbers you can do something with sorting, as per some of the other answers. For the general case of arrays of arbitrary objects I don't think you can avoid doing it the long way. The following will give you the intersection of any number of arrays provided as parameters to arrayIntersection
:
var arrayContains = Array.prototype.indexOf ?
function(arr, val) {
return arr.indexOf(val) > -1;
} :
function(arr, val) {
var i = arr.length;
while (i--) {
if (arr[i] === val) {
return true;
}
}
return false;
};
function arrayIntersection() {
var val, arrayCount, firstArray, i, j, intersection = [], missing;
var arrays = Array.prototype.slice.call(arguments); // Convert arguments into a real array
// Search for common values
firstArray = arrays.pop();
if (firstArray) {
j = firstArray.length;
arrayCount = arrays.length;
while (j--) {
val = firstArray[j];
missing = false;
// Check val is present in each remaining array
i = arrayCount;
while (!missing && i--) {
if ( !arrayContains(arrays[i], val) ) {
missing = true;
}
}
if (!missing) {
intersection.push(val);
}
}
}
return intersection;
}
arrayIntersection( [1, 2, 3, "a"], [1, "a", 2], ["a", 1] ); // Gives [1, "a"];
I'll contribute with what has been working out best for me:
if (!Array.prototype.intersect){
Array.prototype.intersect = function (arr1) {
var r = [], o = {}, l = this.length, i, v;
for (i = 0; i < l; i++) {
o[this[i]] = true;
}
l = arr1.length;
for (i = 0; i < l; i++) {
v = arr1[i];
if (v in o) {
r.push(v);
}
}
return r;
};
}
Here is underscore.js implementation:
_.intersection = function(array) {
if (array == null) return [];
var result = [];
var argsLength = arguments.length;
for (var i = 0, length = array.length; i < length; i++) {
var item = array[i];
if (_.contains(result, item)) continue;
for (var j = 1; j < argsLength; j++) {
if (!_.contains(arguments[j], item)) break;
}
if (j === argsLength) result.push(item);
}
return result;
};
Source: http://underscorejs.org/docs/underscore.html#section-62
var arrays = [_x000D_
[1, 2, 3],_x000D_
[2, 3, 4, 5]_x000D_
]_x000D_
function commonValue (...arr) {_x000D_
let res = arr[0].filter(function (x) {_x000D_
return arr.every((y) => y.includes(x))_x000D_
})_x000D_
return res;_x000D_
}_x000D_
commonValue(...arrays);
_x000D_
A tiny tweak to the smallest one here (the filter/indexOf solution), namely creating an index of the values in one of the arrays using a JavaScript object, will reduce it from O(N*M) to "probably" linear time. source1 source2
function intersect(a, b) {
var aa = {};
a.forEach(function(v) { aa[v]=1; });
return b.filter(function(v) { return v in aa; });
}
This isn't the very simplest solution (it's more code than filter+indexOf), nor is it the very fastest (probably slower by a constant factor than intersect_safe()), but seems like a pretty good balance. It is on the very simple side, while providing good performance, and it doesn't require pre-sorted inputs.
The performance of @atk's implementation for sorted arrays of primitives can be improved by using .pop rather than .shift.
function intersect(array1, array2) {
var result = [];
// Don't destroy the original arrays
var a = array1.slice(0);
var b = array2.slice(0);
var aLast = a.length - 1;
var bLast = b.length - 1;
while (aLast >= 0 && bLast >= 0) {
if (a[aLast] > b[bLast] ) {
a.pop();
aLast--;
} else if (a[aLast] < b[bLast] ){
b.pop();
bLast--;
} else /* they're equal */ {
result.push(a.pop());
b.pop();
aLast--;
bLast--;
}
}
return result;
}
I created a benchmark using jsPerf: http://bit.ly/P9FrZK. It's about three times faster to use .pop.
function intersectionOfArrays(arr1, arr2) {
return arr1.filter((element) => arr2.indexOf(element) !== -1).filter((element, pos, self) => self.indexOf(element) == pos);
}
// Return elements of array a that are also in b in linear time:_x000D_
function intersect(a, b) {_x000D_
return a.filter(Set.prototype.has, new Set(b));_x000D_
}_x000D_
_x000D_
// Example:_x000D_
console.log(intersect([1,2,3], [2,3,4,5]));
_x000D_
I recommend above succinct solution which outperforms other implementations on large inputs. If performance on small inputs matters, check the alternatives below.
Alternatives and performance comparison:
See the following snippet for alternative implementations and check https://jsperf.com/array-intersection-comparison for performance comparisons.
function intersect_for(a, b) {_x000D_
const result = [];_x000D_
const alen = a.length;_x000D_
const blen = b.length;_x000D_
for (let i = 0; i < alen; ++i) {_x000D_
const ai = a[i];_x000D_
for (let j = 0; j < blen; ++j) {_x000D_
if (ai === b[j]) {_x000D_
result.push(ai);_x000D_
break;_x000D_
}_x000D_
}_x000D_
} _x000D_
return result;_x000D_
}_x000D_
_x000D_
function intersect_filter_indexOf(a, b) {_x000D_
return a.filter(el => b.indexOf(el) !== -1);_x000D_
}_x000D_
_x000D_
function intersect_filter_in(a, b) {_x000D_
const map = b.reduce((map, el) => {map[el] = true; return map}, {});_x000D_
return a.filter(el => el in map);_x000D_
}_x000D_
_x000D_
function intersect_for_in(a, b) {_x000D_
const result = [];_x000D_
const map = {};_x000D_
for (let i = 0, length = b.length; i < length; ++i) {_x000D_
map[b[i]] = true;_x000D_
}_x000D_
for (let i = 0, length = a.length; i < length; ++i) {_x000D_
if (a[i] in map) result.push(a[i]);_x000D_
}_x000D_
return result;_x000D_
}_x000D_
_x000D_
function intersect_filter_includes(a, b) {_x000D_
return a.filter(el => b.includes(el));_x000D_
}_x000D_
_x000D_
function intersect_filter_has_this(a, b) {_x000D_
return a.filter(Set.prototype.has, new Set(b));_x000D_
}_x000D_
_x000D_
function intersect_filter_has_arrow(a, b) {_x000D_
const set = new Set(b);_x000D_
return a.filter(el => set.has(el));_x000D_
}_x000D_
_x000D_
function intersect_for_has(a, b) {_x000D_
const result = [];_x000D_
const set = new Set(b);_x000D_
for (let i = 0, length = a.length; i < length; ++i) {_x000D_
if (set.has(a[i])) result.push(a[i]);_x000D_
}_x000D_
return result;_x000D_
}
_x000D_
Results in Firefox 53:
Ops/sec on large arrays (10,000 elements):
filter + has (this) 523 (this answer)
for + has 482
for-loop + in 279
filter + in 242
for-loops 24
filter + includes 14
filter + indexOf 10
Ops/sec on small arrays (100 elements):
for-loop + in 384,426
filter + in 192,066
for-loops 159,137
filter + includes 104,068
filter + indexOf 71,598
filter + has (this) 43,531 (this answer)
filter + has (arrow function) 35,588
Source: Stackoverflow.com