2
\$\begingroup\$

I built a small JavaScript function to see if a series of characters are a palindrome or not. The functions works well and does everything it has to do, but I'm wondering if something can be tweaked to make it faster.

This is the actual code:

var words = ['anita lava la tina',' a ', 'civvic', 'ddaa', 'aa', 'dca', '332', null,     'toyota','racecar'];
function getPalindrome(word){
    if(!word || (word = word.replace(/ /g,'')).length<2)
        return "-1";

    var charsCount = {};
    word = word.toLowerCase();
    var chars = word.split("");

    //ahorra un poco de tiempo cuando las palabras son grandes
    if(chars.reverse().join('')===word)
        return word;


    for(var i=0;i<chars.length;i++){
        if(charsCount[chars[i]])
            charsCount[chars[i]] += 1;
        else 
            charsCount[chars[i]] = 1;
    }

    //si hay mas de un impar, ya no puede ser palindromo
    var oddCounter = 0;
    var palindromo = [];
    var oddChar = '';
    for(var letter in charsCount){
        if(charsCount[letter] % 2 !== 0)
            oddCounter++;

        if(oddCounter>1)
            return "-1";

        var times = charsCount[letter];
        if(times===1){
            oddChar = letter;
        }
        else{
            for(var i=0;i<times;i++){
                if(i%2==0)
                    palindromo.push(letter);
                else
                    palindromo.unshift(letter);
            }
        }
    }
    //agrego el impar a la mitad, si es que hay
    palindromo.splice(palindromo.length/2,0,oddChar);   

    return palindromo.join('');
}

for(var i in words){    
    console.log(words[i],":",getPalindrome(words[i]));  
}

What I do here is this:

  1. If word is null or the length of word after eliminating spaces is lower than 2, then it's not a palindrome, so return -1.
  2. If the reverse of word equals word, then it is a palindrome, so return the word.
  3. Make a map with all the chars, adding the occurrence of each char.
  4. Loop the map of the chars: if the count of more than one char is an odd number, then it's not a palindrome, so return -1.
  5. Simply put one char at the beginning of an array and one at the end and loop n times if the char was found.
  6. Store the odd char in a variable for later use.
  7. When loop (4) ends, insert the odd char in the middle of the array.
  8. Return the built palindrome.

The function works, but how can I make it faster?

\$\endgroup\$

migrated from stackoverflow.com Aug 17 '14 at 3:42

This question came from our site for professional and enthusiast programmers.

  • 1
    \$\begingroup\$ Surely the easiest way to check for a palindrome is to remove all spaces / punctuation and then check word.split("").reverse().join("")===word or am I missing something here. Your other checks seem pointless? \$\endgroup\$ – MarshallOfSound Aug 17 '14 at 3:46
2
\$\begingroup\$

Make a local instance of word and work with that variable through all your function code, every reference to word it's been fetched through the scope chain.

During code execution, identifiers such as variable and function names are resolved by searching the scope chain of the execution context. Identifier resolution begins at the front of the scope chain and proceeds toward the back. Consider the following code:

function add(num1, num2){
    return num1 + num2;
}

var result = add(5, 10);

When this code is executed, the add function has a [[Scope]] property that contains only the global variable object. As execution flows into the add function, a new execution context is created, and an activation object containing this, arguments, num1, and num2 is placed into the scope chain.

enter image description here

This resolution is performed by inspecting each object in the scope chain until the specific identifier is found. The search begins at the first object in the scope chain, which is the activation object containing the local variables for the function. If the identifier isn’t found there, the next object in the scope chain is inspected for the identifier. When the identifier is found, the search stops. In the case of this example, the identifiers num1 and num2 exist in the local activation object and so the search never goes on to the global object.

Understanding scopes and scope chain management in JavaScript is important because identifier resolution performance is directly related to the number of objects to search in the scope chain. The farther up the scope chain an identifier exists, the longer the search goes on and the longer it takes to access that variable; if scopes aren’t managed properly, they can negatively affect the execution time of your script.

Use Local Variables

Local variables are, by far, the fastest identifiers both to read from and write to in JavaScript. Because they exist in the activation object of the executing function, identifier resolution involves inspecting a single object in the scope chain. The amount of time necessary to read the value of a variable increases with each step along the scope chain, so the greater the identifier depth, the slower the access is going to be.

\$\endgroup\$
0
\$\begingroup\$

I might suggest doing as follows. Keep in mind that the Array.prototype.reverse() should be implemented by utilizing the Object.defineProperty() tool for the production code.

var isPalindrome = s => { var t = s.toLowerCase()
                                   .replace(/\s+/g,"");
                          return [].slice.call(t)
                                   .reverse()
                                   .map((c,i) => c === t[i])
                                   .every(b => b);
                        };
console.log(isPalindrome("Was it a car or a cat I saw"));
console.log(isPalindrome("This is not a palindrome"));

\$\endgroup\$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy