Efficient and async way to check if at least one element of an array is also an element of another array

Question

I want to determine if one array has at least one element that is also contained in another array.

For instantce:

arr0 = [0]
arr1 = [1,2,3]
arr2 = [2,3,4]
arr3 = [1,5,3]

arrCompare(arr0, arr1) // false
arrCompare(arr1, arr2) // true
arrCompare(arr1, arr3) // true

So far, I have:

array_has_one_common_element =        (a, b) ->
  breakLoop1 = false

  for num1 in a
    for num2 in b
      if num2 is num1
        breakLoop1 = true; break
    break if breakLoop1

  return breakLoop1

Because this function will be used on the server side with nodejs and may have to deal with big arrays, I was wondering how it could be rewritten to be asynchronous (with the async library). Or is it efficient enough as is ?

Is it possible to convert arrays into HashSets (Maps) and intersect them? If intersection is empty - arrays don't have common items, otherwise intersection is common items. Combined loop is O(n^2) when intersection is O(n) — Dmitry Bychenko, Dec 10 '13 at 08:38

Leonid Beschastny · Accepted Answer · 2013-12-10T10:42:03.720

Arrays intersection is a very slow operation. So, if you work with large arrays then it's best to use hashsets instead.

Here is my intersection implementation using hashsets:

hashset = (elements) ->
  return elements unless Array.isArray elements
  set = {}
  set[e] = true for e in elements
  set

intersect = (a, b) ->
  s1 = hashset a
  s2 = hashset b
  s3 = {}
  for k of s1
    s3[k] = true if s2[k]
  s3

arrCompare = (a, b) ->
  Object.keys(intersect a, b).length isnt 0

I don't think you actually need it to be asynchronous. If you don't want array operations to block main thread - dispatch them to another process (worker).

Update

Here are some benchmarks with benchmark.js:

arr1 = [1..9999];
arr2 = [9999..99999];

{ name: 'My Code',
  mean: 0.004182571958225297 }
{ name: 'Your Code',
  mean: 2.1228081478333336 }
{ name: 'askkirati\'s Synchronous Code',
  mean: 3.569238156 }

Same benchmark for two string arrays:

arr1 = (Math.random().toString(36).slice(2,12) for i in [1..9999])
arr2 = (Math.random().toString(36).slice(2,12) for i in [1..9999])

{ name: 'My Code',
  mean: 0.009257149728395064 }
{ name: 'Your Code',
  mean: 1.5913590743333332 }
{ name: 'askkirati\'s Synchronous Code',
  mean: 1.418200398 }

I also tried two very huge arrays, but I given up on waiting for all methods to complete:

arr1 = [1..999999]
arr2 = [999999..9999999]

{ name: 'My Code',
  mean: 1.6512419735000001 }

As you can see, hashmap intersection works much faster than loops intersection. And it takes only 1.6 seconds on my PC to intersect two 999999 element arrays.

Yalamber · Answer 2 · 2013-12-10T09:24:04.690

Here is one way using async.some

var async = require('async');
var arr0 = [0];
var arr1 = [1,2,3];
var arr2 = [2,3,4];
var arr3 = [1,5,3];

function testExist(arrayToCheck, arrayInCheck, mainCallback){
  async.some(arrayToCheck, function(item, callback){
    if(arrayInCheck.indexOf(item) != -1){
      callback(true);
    }
    else{
      callback(false);
    }
  }, function(result){
    mainCallback(result);
  });
}
testExist(arr0, arr1, function(result){
  console.log(result);
});
testExist(arr1, arr2, function(result){
  console.log(result);
});

testExist(arr2, arr3, function(result){
  console.log(result);
});

Here is example without using async library, Node.js supports array.some

var arr0 = [0];
var arr1 = [1,2,3];
var arr2 = [2,3,4];
var arr3 = [1,5,3];

function testWithoutAsyncLibExist(arrayToCheck, arrayInCheck, callback){
  var check = arrayToCheck.some(function(el, index, array){
    return (arrayInCheck.indexOf(el) != -1);
  });
  callback(check);
}
testWithoutAsyncLibExist(arr0, arr1, function(result){
  console.log(result);
});
testWithoutAsyncLibExist(arr1, arr2, function(result){
  console.log(result);
});
testWithoutAsyncLibExist(arr2, arr3, function(result){
  console.log(result);
});

Efficient and async way to check if at least one element of an array is also an element of another array

2 Answers2

Update