Ad

Fastest Way To Find A Value Inside A Multi-dimensional Array?

- 1 answer

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?

Ad

Answer

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 @Mogsdadproposed, 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
Ad
source: stackoverflow.com
Ad