Improve performance of a JavaScript function (with an array lookup)

Question

I'm trying to complete a code challenge where I have to decode the keystrokes of a cell phone t9 input into characters to create a text message. The main function (reverse_t9) takes a string of keys such as "44 444" or "999337777" and I need to translate them to their corresponding texts ("hi", or "yes" respectively).

I have all the logic down and can generate the correct outputs, but the challenge is telling me that I'm exceeding the time limit which is 4000ms. I've found a couple spots to improve performance, but still can't get it under that mark. I think the biggest time-waster is my "getLetterFromDigits" function which has to iterate through my array to find the corresponding mapping for a set of keystrokes.

Am I missing some other obvious performance problems? Please let me know if you need more info.

function reverse_t9(keys) {
    var retVal = "";
    var maxKeystrokes = 3;
    var splitKeystrokes = splitKeystrokesBySpacesAndKeys(keys);

    for (i = 0, numSplits = splitKeystrokes.length; i < numSplits; i++){
        //console.log("THIS SPLIT:");
        //console.log(splitKeystrokes[i]);
        //console.log("THIS LETTER:");
        //console.log(getLetterFromDigits(splitKeystrokes[i]));
        retVal = retVal + getLetterFromDigits(splitKeystrokes[i]);
    }

    return retVal;
}

function splitKeystrokesBySpacesAndKeys(keys) {
    var retVal = [];
    var lastKey = "";
    var thisKey = "";
    var lastSplit = 0;
    var isSpace = 0;

    for (i = 0, numKeys = keys.length; i <= numKeys; i++) {

        thisKey = keys.substring(i, i + 1);

        if (i == 0) {
            // FIRST TIME AROUND, DO NOTHING ELSE, JUST ASSIGN LAST KEY
            lastKey = thisKey;
        } else {
            if (thisKey != lastKey) {
                if (thisKey != " ") {
                    if (lastKey != " ") {
                        retVal.push(keys.substring(lastSplit, i));
                    } else {
                        retVal.push(keys.substring(lastSplit, i - 1));
                    }

                    lastSplit = i;
                }

                lastKey = thisKey;

            } else {
                // KEY DID NOT CHANGE, ASSIGN LAST KEY AND CONTINUE ON
                lastKey = thisKey;
            }
        }
    }

    return retVal;
}

function getLetterFromDigits(digits){
    var retVal;

    var digitMapping = [
    {
        digit: "1",
        mapping: []
    },
    {
        digit: "2",
        mapping: ["a", "b", "c"]
    },
    {
        digit: "3",
        mapping: ["d", "e", "f"]
    },
    {
        digit: "4",
        mapping: ["g", "h", "i"]
    },
    {
        digit: "5",
        mapping: ["j", "k", "l"]
    },
    {
        digit: "6",
        mapping: ["m", "n", "o"]
    },
    {
        digit: "7",
        mapping: ["p", "q", "r", "s"]
    },
    {
        digit: "8",
        mapping: ["t", "u", "v"]
    },
    {
        digit: "9",
        mapping: ["w", "x", "y", "z"]
    },
    {
        digit: "0",
        mapping: ["*"]
    }

    ];

    var digit = digits.substring(0, 1);


    for (i = 0, numMappings = digitMapping.length; i < numMappings; i++){
        if (digitMapping[i].digit == digit){
            retVal = digitMapping[i].mapping[digits.length - 1];
            break;
        }
    }

    return retVal;
}

For one thing, instead of setting up that key to mapping list like that, you could make a simple array. You're mapping strings "0" through "9" - that's a simple array lookup. Just make an array of arrays. — Pointy
– Pointy, Commented Jun 9, 2016 at 15:21
Also, instead of keys.substring(i, i+1) you can see if keys.charAt(i) or simply keys[i] is faster. — Pointy
– Pointy, Commented Jun 9, 2016 at 15:22
Whoops... Didn't know about codereview. And @Pointy you mean like: var digitMapping = [['a','b','c'],['d','e','f']...]; ? — the-nick-wilson
– the-nick-wilson, Commented Jun 9, 2016 at 15:23
The biggest problem I can spot is that you've forgotten to declare the i variable as local with var in all of your three loops. This is likely the reason for the abysimal runtime, though you must have been lucky to still see it a) terminate and b) get the correct results. — Bergi
– Bergi, Commented Jun 9, 2016 at 16:29

StriplingWarrior · Accepted Answer · 2016-06-09 15:29:03Z

2

First, declare your digit mapping outside of the function, so you're reusing the results of that work rather than performing that work every time the function is called.

Secondly, make digitMapping use key/value pairs so you can do a quick lookup based on a given property name rather than having to loop through it.

var digitMapping = 
{
    "1": [],
    "2": ["a", "b", "c"],
    ...
};

function getLetterFromDigits(digits){
    var digit = digits.substring(0, 1);
    return digitMapping[digit][digits.length - 1];
}

edited Jun 9, 2016 at 15:29

answered Jun 9, 2016 at 15:27

StriplingWarrior

158k29 gold badges261 silver badges326 bronze badges

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

4 Comments

the-nick-wilson Over a year ago

This seems like a good solution - Let me try it and get back to you.

StriplingWarrior Over a year ago

@xboxremote: It wasn't correct at first (still might not be) but hopefully it'll give you the right idea.

the-nick-wilson Over a year ago

I think it does... Still working through it, but I gotcha.

the-nick-wilson Over a year ago

This did the trick. I had to add the "space bar" character mapped for 0 in order to get it to work, and I ended up doing away with the key/value pairs, and just did an array of arrays:

var digitMapping = [     [" "],     [],     ["a", "b", "c"],     ["d", "e", "f"],     ["g", "h", "i"],     ["j", "k", "l"],     ["m", "n", "o"],     ["p", "q", "r", "s"],     ["t", "u", "v"],     ["w", "x", "y", "z"] ];

Rajesh Dixit · Accepted Answer · 2016-06-09 15:40:23Z

Few pointers:

Save length in a variable and use it. Using Array.length will check for every iteration.
Instead of having array of objects, create 1 mapping object like:

{
  "1": [],
  "2": ["a", "b", "c"]
},

and fetch it as digitMapping[mapping[digits.length - 1]]

Instead of thisKey = keys.substring(i, i + 1);, you can save characters in a variable like char_arr = keys.split("") and loop over it.
You can get rid of 1 iteration(first iteration). Just set lastKey = char_arr[0] or lastKey=keys.charAt(0)
Else part for if (thisKey != lastKey) is not required. If both values are same, you do not need to set lastKey = thisKey;

Alex Kudryashev · Accepted Answer · 2016-06-09 17:18:15Z

Try my version.

function getMsg(val){
  //split digits to array
  val = val.split('');
  //some internal vars
  var letter = [];
  var last = val[0];
  var msg='';
  for(var i=0,n=val.length;i<n;i++){
    if(val[i]==last)
      //collect sequential digits
      letter.push(val[i]);
    else{
      //new digit 
      msg += digMap[letter[0]][letter.length-1];
      //reinit letter array
      letter=[val[i]];
      last = val[i];
    }
  }
  msg += digMap[letter[0]][letter.length-1];
  return msg; //return decoded
}
//map digits as @Rajesh recommended
var digMap={
  "1":[" "],
  "2":'abc'.split(''),
  "3":'def'.split(''),
  "4":'ghi'.split(''),
  "5":'jkl'.split(''),
  "6":'mno'.split(''),
  "7":'pqrs'.split(''),
  "8":'tuv'.split(''),
  "9":'wxyz'.split(''),
  "0":["*"],
  " ":['']
}
//test functionality
console.time('txt');
console.log(getMsg('999337777'));
//yes
console.timeEnd('txt');

Collectives™ on Stack Overflow

Improve performance of a JavaScript function (with an array lookup)

3 Answers 3

4 Comments

Comments

Comments

Hot Network Questions

Collectives™ on Stack Overflow

3 Answers 3

4 Comments

Comments

Comments

Related