CODEWITHSUNDEEP
node.jsarrays
user4657635
user4657635

Reputation:

In nodejs, Find sub array in array


Is there a quickest way to find a sub array in an array ? For exemple with anonymous methods ?
In my case, the master array is a frame of bytes received from a device, the sub-array is the characteristic sequence of the beginning of the waited answer. The device is a Lidar, so the best is the quickest possible processing. 

function findSubArray( master, sub, fromPos) {
    let pos = null;
    if ( ! fromPos) fromPos = 0;
    
    do {
        if (master.length < sub.length) break;
        if (fromPos > (master.length - sub.length)) break;
        
        for( m=fromPos; m < (master.length - sub.length - fromPos+1); m++) {
            
            let masterPos = m;
            for( s=0; s < sub.length; s++) {
                if (sub[s] != master[m + s]) {
                    masterPos = -1;
                    break;
                }
            }
            if (masterPos != -1) {
                pos = masterPos;
                break;
            }
        }
    } while( false);
    return pos;
}

Best regards.

Upvotes: 0

Views: 265

Answers (2)

The Bomb Squad
The Bomb Squad

Reputation: 4337

Ok, assuming that you want to see a sub array's sequence in another array, here's an example(which really is JavaScript of the C answer given by Breno Alves)

EDIT: I cut down the first loop based on the sub array's length to optimise since it was slower.. you can run the tests a few times.. sometimes it says my code is faster, other times it says your code is faster, but your code is pretty fast either way ;-;

my code when faster

your code when faster

function isSubArray(possibleParent,possibleChild){
  var toReturn=false //will remain false if possibleChild is NOT subArray
  var [arr,sub]=[possibleParent,possibleChild]
  if(arr.length<sub.length){return false} //the sub has to be smaller
  for(let i=0;i<arr.length-(sub.length-1);i++){
    var isSub=true //remains true if entire sub pattern matches
    for(let j=0;j<sub.length;j++){
      if(arr[j+i]!=sub[j]){isSub=false}
    }
    if(isSub){return true} //this means a sub pattern matched
  }
  return false //this means no sub pattern mashed
}

//examples
console.log( isSubArray([1,2,3,4,5,6,7],[4,5]) ) //true
console.log( isSubArray([1,2,3,4,5,6,7],[1,3]) ) //false
console.log( isSubArray([1,2,3],[1,2,3,4,5,6,7]) ) //false
console.log( isSubArray([1,2,3,4,5,6,7],[1,2,3,4,5,6,7]) ) //true

//speed testing
function test(fn){
  var [arr1,arr2]=[[1,2,3,4,5,6,7],[1,3]]
  var startTime=new Date()-0
  for(let i=0;i<1e6;i++){
    fn(arr1,arr2) //test to do 1 million times
  }
  return new Date()-startTime
}

var myCodeTime=test(isSubArray)
var yourCodeTime=test(findSubArray)

console.log("my code speed is",myCodeTime)
console.log("your code speed is",yourCodeTime)
<script>
//your function is here :D
function findSubArray( master, sub, fromPos) {
    let pos = null;
    if ( ! fromPos) fromPos = 0;
    
    do {
        if (master.length < sub.length) break;
        if (fromPos > (master.length - sub.length)) break;
        
        for( m=fromPos; m < (master.length - sub.length - fromPos+1); m++) {
            
            let masterPos = m;
            for( s=0; s < sub.length; s++) {
                if (sub[s] != master[m + s]) {
                    masterPos = -1;
                    break;
                }
            }
            if (masterPos != -1) {
                pos = masterPos;
                break;
            }
        }
    } while( false);
    return pos;
}
</script>

Upvotes: 0

Breno Alves
Breno Alves

Reputation: 11

You could look at geeksforgeeks for those type of problems.

I found this O(N) solution that could be applied for your problem.

https://www.geeksforgeeks.org/check-whether-an-array-is-subarray-of-another-array/

just store the first index when starting a new sub-sequence and you have the position.

Upvotes: 0

Related Questions