CODEWITHSUNDEEP
javascriptarraysperformance
the-nick-wilson
the-nick-wilson

Reputation: 616

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

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;
}

Upvotes: 3

Views: 103

Answers (3)

Alex Kudryashev
Alex Kudryashev

Reputation: 9460

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');

Upvotes: 0

Rajesh
Rajesh

Reputation: 24915

Few pointers:

  1. Save length in a variable and use it. Using Array.length will check for every iteration.
  2. 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]]

  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.
  2. You can get rid of 1 iteration(first iteration). Just set lastKey = char_arr[0] or lastKey=keys.charAt(0)
  3. Else part for if (thisKey != lastKey) is not required. If both values are same, you do not need to set lastKey = thisKey;

Upvotes: 1

StriplingWarrior
StriplingWarrior

Reputation: 156459

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];
}

Upvotes: 2

Related Questions