2

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?

Improve this question
15
  • 1
    Please provide sample input as well Commented May 30, 2018 at 13:05
  • Provide sample input and desired successful output. Commented May 30, 2018 at 13:08
  • 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. Commented May 30, 2018 at 13:08
  • Possible duplicate of Check whether an array exists in an array of arrays? Commented May 30, 2018 at 13:08
  • Im sure array is very big. from 300arrays to infinite. Commented May 30, 2018 at 13:09

3 Answers 3

Reset to default
0

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).

Improve this answer
Sign up to request clarification or add additional context in comments.

2 Comments

I think this would be slower. Making another array for checking... Isnt it?
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)
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.

Improve this answer

5 Comments

Do you think mixing it with my Face(); function will be good?
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.
I re-uploaded the code. in my post. It has Face() function
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.
@user9735269 I simplified the code a bit, assuming you never need to remove arrays and that you never want to add duplicate arrays.
-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]))

Improve this answer

1 Comment

Thanks for replying. I'll try that and comment you.

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.