CODEWITHSUNDEEP
javascriptarrays
Zahand
Zahand

Reputation: 488

More efficient way of searching through a two-dimensional array than nested for-loops?

So I have a function that takes in a two-dimensional array and a string. It then searches through the table and counts how many times the given string is found.

Here is the code: 

function getNumberShifts(table, name) {

  var amount = 0;

  for(i = 0; i < table.length; i++){
    for(j = 0; j < table[i].length; j++){

      var text = table[i][j].toString();

      if(text.indexOf(name)>-1){
        amount += 1;
      }
    }
  }
  return amount;
}

The 2D-array is not that big, about 30 x 60. Most of the cells are empty or contain 1 element (name). Sometimes it can contain two.

Is there a more efficient way than O(n^2)? (This is a Google Sheets Script)

Thanks in advance!

Edit: Example-table:

Time | Monday | Tuesday | Wednesday | Thursday | Friday | Saturday | Monday | ...
12:00| --name1 | ---name2 | ----name3 | ---name2 | name4 | ----name1 | name2 | ...
.
.
.

(Ignore the dashes, they are only for formatting purposes so you guys "see" the table)

This is basically it. Just a table with names. The top row and the left coloumn are not a part of the table that is sent to the function. Just the names. Some of the cells are completeley empty, (So it's easier to read it for me and my coworkers)

Upvotes: 1

Views: 655

Answers (3)

kennebec
kennebec

Reputation: 104780

It may be that converting the array to a string and using string's indexOf,

incrementing the index after each match, would be less laborious than

iterating through the array.

function getNumberShifts(table, name){
    var i= 0, amount= 0, text= table.join(' ');
    while((i= text.indexOf(name,i)+1)){
        ++amount;
    }

    return amount;
}


var A1= [
    [0, "name2"], [1, ""], [2, "name2"], [3, ""], 
    [4, "name3"], [5, ""], [6, "name2"], [7, ""], [8, "name2"], [9, "name3"], 
    [10, "name2"], [11, ""], [12, "name2"], [13, ""], [14, "name3"], [15, ""], 
    [16, "name2"], [17, ""], [18, "name2"], [19, "name3"], [20, "name2"], 
    [21, ""], [22, "name2"], [23, ""], [24, "name3"], [25, ""], 
    [26, "name2"], [27, ""], [28, "name2"], [29, "name3"]
]

getNumberShifts(A1, 'name3');

/* returned value: (Number) 6 */

Upvotes: 0

Michael Lorton
Michael Lorton

Reputation: 44396

You cannot do it faster for one search. As Safari points out, you have to look in every cell once, there are n^2 cells, so...

But if you are searching multiple times, it may make sense to preprocess the 2D array into a single hash-array. So a n^2 set-up time but only a log(n) look-up time for each search.

var getNumberShiftsFinder = function(table) {
  var found = {};

  for(var i = 0; i < table.length; i++){
    for(var j = 0; j < table[i].length; j++) {
      var text = table[i][j].toString();
      found[text] = 1 + ( found[text] || 0 );
    }
  }
  return function(name) {
      return found[name] || 0;
  };
};

Upvotes: 0

Safari
Safari

Reputation: 3382

Sorry, but there is no faster way of doing that. You need to check every single cell at least once.

Upvotes: 2

Related Questions