Fastest way to find a value inside a multi-dimensional array?

Question

I am creating a function that finds a value inside multiple arrays, but I'm having some performance issues since the arrays can be really long. The best performance I have found so far is with something like this:

function isValInArray(arr, value) {
    var bool = false;
    var myArr = arr;
    var myVal = value;
    var i = 0;
    var j = 0;

    for (i = 0; i < myArr.length; i++) {
        for (j = 0; j < myArr[i].length; j++){
            if (myArr[i][j] === myVal ) {
               bool = true;
            }
        }
    }
    return bool;
}

I have tried some different approaches but the performance of the previous function has been the best one so far.

Any ideas on how to make it a little faster?

Answer 1

Since you're only concerned about whether a value is IN the arrays, you can flatten them first, then use native functions to perform the search just once.

function isValInArray(arr, value) {
  var myArr = [].concat.apply([], arr);  // from stackoverflow.com/a/10865042/1677912
  return ( myArr.indexOf(value) >= 0 );
}

I revised the jsPerf test proposed by @torazaburo, see revision 2. The original test was fatally biased, as it searched a small array for only for a single value, and that value was the second-to-last item in the last row. (The second item a decrementing loop would find - hence the bias.) To reflect a more real-world scenario, now:

• The sample data is larger; a configurable 10 x 100 square array. (OP indicated the arrays can be really long.)
• Three data points are searched in each test; the first, last and middle. (This could be further expanded, but this selection covers best, worst, and average for loop-based solutions.)
• Values are Strings instead of Numbers; while this will neutralize the effect of the search algorithms somewhat because string comparisons are slower than numeric comparisons, but as the OP did not indicate the nature of the values, it's a more realistic assumption.

This test shows that all the suggested solutions perform similarly, which reinforces @torazaburo's opinion, it is questionable whether these types of micro-optimizations are worth worrying about at all.

I recommend using the solution that is easiest for you to maintain. If performance is an actual problem for you, test your options with data that realistically reflects your situation.

In case you're wondering, this solution appears as concat in the tests.

Answer 2

You can return true immediately when you find a match:

function isValInArray(arr, value) {
  for (var i = 0; i < arr.length; ++i)
    for (var j = 0; j < arr[i].length; ++j)
      if (arr[i][j] === value)
        return true;
  return false;
}

In ECMAScript5 it can be rewritten to the more semantic (but probably slower)

function isValInArray(arr, value) {
  return arr.some(function(sub) {
    return sub.indexOf(value) > -1;
  });
}

However, asymptotically, both will still have the same average and worst-case costs as the code in your question, because searches in an array are linear. Then if the array contains n subarrays, each of which has m items, the cost will be n m.

If you want to speed it up, you can use ECMAScript 6 sets. The searches are required to be sublinear on average. For example, if the implementation uses a hash, they will be constant, so the total cost will be n.

Then the function would be one of the following

function isValInArray(arrSets, value) {
  return arrSets.some(set => set.has(value));
}
function isValInArray(arrSets, value) {
  for (var i = 0; i < arrSets.length; ++i)
    if (arrSets[i].has(value)) return true;
  return false;
}

Example:

var arrSets = [new Set([1,2,3]), new Set([3,5,6])];
isValInArray(arrSets, 0); // false
isValInArray(arrSets, 1); // true

In case you must use arrays because you want to keep indices, you can do a conversion before the search. But that will cost n m, so it will only be useful if you can reuse the sets because you want to do lots of searches.

var arrSets = arr.map(sub => new Set(sub));

But in that case, you don't need to keep the sets separated. Similarly to what @Mogsdad proposed, you can insert the elements of all the arrays in a single set, which will cost n m too. The advantage is that searches will be constant. Example:

var arr = [[1,2,3], [3,5,6]],
    set = new Set([].concat.apply([], arr));
set.has(0); // false
set.has(1); // true