How to check if an array contains a specific array efficiently

Question

I need to sort and remove vertex and I used this thing. But recently I realized that this method is terrible slow.

function Face(v1, v2, v3) {
  var df = Math.hypot(v2[0] * 1 - v3[0] * 1, v2[1] * 1 - v3[1] * 1, v2[2] * 1 - v3[2] * 1);
  if (df != 0) {
    for (var dp = 0; dp < df; dp += gap) {
      x = v3[0] * 1 + (v2[0] * 1 - v3[0] * 1) / df * dp;
      y = v3[1] * 1 + (v2[1] * 1 - v3[1] * 1) / df * dp;
      z = v3[2] * 1 + (v2[2] * 1 - v3[2] * 1) / df * dp;
      var ds = Math.hypot(x - v1[0] * 1, y - v1[1] * 1, z - v1[2] * 1);
      if (ds != 0) {
        for (var dps = 0; dps < ds; dps += gap) {
          fx = v1[0] * 1 + (x - v1[0] * 1) / ds * dps;
          fy = v1[1] * 1 + (y - v1[1] * 1) / ds * dps;
          fz = v1[2] * 1 + (z - v1[2] * 1) / ds * dps;
          var ffx = Math.round(fx / gap) * gap;
          var ffy = Math.round(fy / gap) * gap;
          var ffz = Math.round(fz / gap) * gap;

          if (check) {
            if (!(findOne(output, [ffx, ffy, ffz]))) {
              output.push([ffx, ffy, ffz]);
            }
          } else {
            output.push([ffx, ffy, ffz]);
          }
        }
      }
    }
  }
}

Face(vertex1,vertex2,vertex3); without checking, Much more faster. (This method is call almost 1000~10000 times)

findOne(arr,[1,2]);//returns true. (I NEED THIS)
arr.includes([1,2]);//returns false.
arr[0]==[1,2];// returns false.


function findOne(arr, arr2) { 
    for(var l=0;l<arr.length;l++){
        if(arr[l][0]==arr2[0]&&arr[l][1]==arr2[1]&&arr[l][2]==arr2[2]){
           return true;
        }
    }
    return false;
}

I tried with arr0.include(arr1), but this doesnt work if param is array. if(arr0 == arr1) also didnt worked.

Does anyone know the solution?

The method you posted has linear time complexity so I doubt that's what making your program slow. Sure it can be optimized, depending on how often the contents of those arrays change. I also don't get what this has to do with sorting and removing vertex, maybe your bottleneck is somewhere else. — FINDarkside, May 30 '18 at 13:08
Possible duplicate of [Check whether an array exists in an array of arrays?](https://stackoverflow.com/questions/19543514/check-whether-an-array-exists-in-an-array-of-arrays) — Durga, May 30 '18 at 13:08
#FINDDarkside I made a switch to turn that thing on and off. That surely is a trouble. it takes at least 2x secs more. — user9735269, May 30 '18 at 13:15
#Durga Thanks for replying, but that post didnt helped me. thanks thanks.. — user9735269, May 30 '18 at 13:16
@user9735269 You're talking about just one call to the findOne? If you're doing it like thousands time in a row that's pretty relevant. — FINDarkside, May 30 '18 at 13:17
#FINDDarkside Yes maybe. X, Y and Z. I will add color some day. — user9735269, May 30 '18 at 13:18
@FINDDarkside More than thousand times. You 'll may be impressed — user9735269, May 30 '18 at 13:19
You're checking for three elements (0, 1, 2), but your sub-arrays only contain two elements, am I missing something? — ChatterOne, May 30 '18 at 13:22
@user9735269 What I'm saying is that if you're calling it thousands time in a row, include the code doing so to your question, as it's very likely that's the code we should be optimizing instead of findOne. — FINDarkside, May 30 '18 at 13:22
@ChatterOneMy mistake, this is not a real code. I'll get it. — user9735269, May 30 '18 at 13:29

FINDarkside · Answer 1 · 2018-05-30T14:00:17.697

0

Your solution shouln't be "terrible slow", it has linear time complexity. You could make the check O(1) like this:

var lookup = {
  '1#2': true,
  '3#4': true
};
var arr = [[1, 2], [3, 4]];

function findOne(arr2) {
  return lookup[arr2.join('#')];
}

function addArray(arrayToAdd) {
  const s = arrayToAdd.join('#');
  lookup[s] = true;
  arr.push(arrayToAdd);
}

function removeAtIndex(index) {
  const s = arr[index].join('#');
  delete lookup[s];
  arr.splice(index, 1);
}

Idea is to keep lookup table of what arrays arr contains. Obviously this requires you to update the lookup table every time you add or remove items, I have provided the example. This will obviously use more memory, I'm not sure how big your array is so not sure if that's a problem though.

The lookup table is also assuming that the array items are numbers, if they are strings for example, ['a.', 'ab'].join('.') and ['a', '.ab'].join('.') would result in the same string which isn't desired, take that into account.

Since you said that you're calling it multiple times, so that's probably the code we should be optimizing though. If you want to check if 10k items are in arr, you're currently iterating 10000*arraySize times over the whole array, while just once would be enough.

edited May 30 '18 at 14:00

answered May 30 '18 at 13:25

FINDarkside

2,102
1
18
26

Do you think mixing it with my Face(); function will be good? – user9735269 May 30 '18 at 13:37
What Face function? This will make findOne almost as fast as it can possibly be, array size should have little to none effect on the speed. – FINDarkside May 30 '18 at 13:40
I re-uploaded the code. in my post. It has Face() function – user9735269 May 30 '18 at 13:41
Yeah this should work. Just try it out, it should be super fast. Instead of pushing to array from Face method, call addArray([ffx,ffy,ffz]). You probably won't need the removeAtIndex at all, and it can be simplified a bit if the array will never contain duplicate arrays. – FINDarkside May 30 '18 at 13:49
@user9735269 I simplified the code a bit, assuming you never need to remove arrays and that you never want to add duplicate arrays. – FINDarkside May 30 '18 at 13:52

score 0 · Answer 2 · answered May 30 '18 at 13:38

There are three possible use cases here, but you haven't specified which one you're in, so I'll mention both.

Case 1: Array1 is always the same and Array2 changes. In this case what you can do is build a map out of the array and use that to check if the value exists. This will take a while the first time (because you have to build it), but if Array1 is always the same, all the following checks will be a lot faster.

An example:

var arr = [[1,2,3],[3,4,5]];
var arr2 = [3, 4, 5];

function buildMap(arr) {
    var retObj = {};
    for (var l=0;l<arr.length;l++) {
    retObj[arr[l][0]] = {};
    retObj[arr[l][0]][arr[l][1]] = {};
    retObj[arr[l][0]][arr[l][1]][arr[l][2]] = true;
  }

  return retObj;
}

function findOne(mapArr, arr2) { 
    return mapArr[arr2[0]][arr2[1]][arr2[2]];
}

var mapArr = buildMap(arr);

console.log(findOne(mapArr, arr2));

Case 2: Array1 changes and Array2 is always the same. You can do pretty much the same thing, switching the two arrays.
Case 3: Both arrays change. You can't do much in this case, you'll have to go through the main array at least once, so you can't go lower than O(n). Unless you have some other constraint that you haven't mentioned (I'm specifically thinking of the data being sorted or not).

I think this would be slower. Making another array for checking... Isnt it? — user9735269, May 30 '18 at 13:47
No, making an object for checking, which means a hash map, because the lookup time would be O(1) instead of O(n) (on average) — ChatterOne, May 30 '18 at 13:53

score -2 · Answer 3 · answered May 30 '18 at 13:18

-2

You can use array#some with array#every. First iterate through each array and then compare the length of both the arrays, only if it is equal compare each value.

var arr = [[1,2],[3,4]];
var findOne = (matrix, arr) => {
  return matrix.some(a => a.length === arr.length && a.every((v,i) => v === arr[i]));
} 
console.log(findOne(arr,[1,2]))

answered May 30 '18 at 13:18

Hassan Imam

21,956
5
41
51

Thanks for replying. I'll try that and comment you. – user9735269 May 30 '18 at 13:20

How to check if an array contains a specific array efficiently

3 Answers3