more efficient way of searching 2D array - break after match?

Question

I have a 2D array of units students are studying. For each unit there are different numbers of functions (aka objectives) they are studying and for each function, different numbers of prompts they could be asked in an assessment. My data is a 2D array thus:

functions = [
  ["Unit 1",
    [ // function 1
      "prompt 1",
      "prompt 2",
      ...,
      "prompt n"],
    [ // function 2
  etc...

My code creates assessments based on which units have been studied by pulling random prompts and then shuffling these into the array (sm1).

Some of these prompts have image files associated with them and all have audio files. The file names for these media files are based on where they occur in our material, e.g. u1f1p1.mp3

So my solution was to match this regularity by creating file names based on their position in the array. Here's my code to do that:

for (var a = 0; a < sm1.length; a++) {// for each of sm1's prompts
    for (var b = 0; b <= functions.length-6; b++) { // limit it to units 1-3 of 8 for this specific assessment
       for(var c = 1; c < functions[b].length; c++) { // for each unit's function but starting at 1 to skip "Unit x" label at this point in the array
           for (var d = 0; d < functions[b][c].length; d++) { // for each prompt for each function for each unit
               if(functions[b][c][d] === sm1[a]) { // see if it matches
                    fileNames.push('u'+(b+1)+'f'+c+'p'+(d+1)); // create file name from index and add to fileNames[]
                }
            }
        }
    }
}

This code works fine and, because speed is effectively irrelevant for our purposes, I could say job done. However, I know that this has to be hopelessly inefficient because not only is this a long loop, but it continues to run even after a match is found.

So, two questions:

What would be the most efficient way of finding a match?
How can I break once sm1[n] is found and go on to look for sm1[n+1]?

score 1 · Accepted Answer · answered Jul 06 '17 at 08:24

As for efficiency well I'm unsure but as for breaking on a match it's actually quite simple.

One way (and probably the best way) you can do it is to put it in a function and return fileNames when you have found your match -

function findFileName(sm1, functions, fileNames) {
  for (var a = 0; a < sm1.length; a++) { // for each of sm1's prompts
    for (var b = 0; b <= functions.length - 6; b++) { // limit it to units 1-3 of 8 for this specific assessment
      for (var c = 1; c < functions[b].length; c++) { // for each unit's function but starting at 1 to skip "Unit x" label at this point in the array
        for (var d = 0; d < functions[b][c].length; d++) { // for each prompt for each function for each unit
          if (functions[b][c][d] === sm1[a]) { // see if it matches
            fileNames.push('u' + (b + 1) + 'f' + c + 'p' + (d + 1)); // create file name from index and add to fileNames[]
            return fileNames;
          }
        }
      }
    }
  }
}

If using a function isn't for you it can be done inline (hacky code follows; you have been warned).

Although the second clause of a for statement usually relies on the first clause (a < sm1.length) there's actually nothing stopping you from putting extra constraints in there that have nothing to do with the first clause. So you could add a boolean variable before the first for check that on each iteration and set it to true when you find a match -

var matchFound = false;
for (var a = 0; a < sm1.length && !matchFound; a++) { // for each of sm1's prompts
  for (var b = 0; b <= functions.length - 6 && !matchFound; b++) { // limit it to units 1-3 of 8 for this specific assessment
    for (var c = 1; c < functions[b].length && !matchFound; c++) { // for each unit's function but starting at 1 to skip "Unit x" label at this point in the array
      for (var d = 0; d < functions[b][c].length && !matchFound; d++) { // for each prompt for each function for each unit
        if (functions[b][c][d] === sm1[a]) { // see if it matches
          fileNames.push('u' + (b + 1) + 'f' + c + 'p' + (d + 1)); // create file name from index and add to fileNames[]
          matchFound = true;
        }
      }
    }
  }
}

the code at the top does the trick. Thanks for the warning ;-) — Mikawa Ben, Jul 09 '17 at 11:35

score 0 · Answer 2 · answered Jul 06 '17 at 08:40

In general, the most efficient way to loop over an array is to use array.forEach, unfortunately, it is not possible to short circuit Array.forEach calling break. How to short circuit Array.forEach like calling break?. But in this case, you can use another method, such as array.some() instead.

If I had to implement your project, I would not use 2D arrays, because it is less efficient than 1D arrays. And I would use arrays as follows :

let a = [];

a["prompt 1"] = {name: "tom", age: 15, unit: 1} // You can put all your infos in your objects
a["prompt 2"] = {name: "bob", age: 42, unit: 2}
a["prompt 3"] = {name: "alex", age: 55, unit: 3}
a["prompt 4"] = {name: "homer", age: 50, unit: 3}

let b = ["prompt 2", "prompt 4"]

b.forEach((key)=>{ // for each element of array b

    if(a[key] !== undefined) // one match found
    {
        // fileNames.push('u'+(b+1)+'f'+c+'p'+(d+1));
        console.log(a[key])
    }
})

more efficient way of searching 2D array - break after match?

2 Answers2