Optimum way to compare strings in JavaScript?

Question

I am trying to optimize a function which does binary search of strings in JavaScript.

Binary search requires you to know whether the key is == the pivot or < the pivot.

But this requires two string comparisons in JavaScript, unlike in C like languages which have the strcmp() function that returns three values (-1, 0, +1) for (less than, equal, greater than).

Is there such a native function in JavaScript, that can return a ternary value so that just one comparison is required in each iteration of the binary search?

Solution 1

You can use the localeCompare() method.

string_a.localeCompare(string_b);

/* Expected Returns:

 0:  exact match

-1:  string_a < string_b

 1:  string_a > string_b

 */

Further Reading:

• MDN: String.prototype.localeCompare
• Stack Overflow - Is there a JavaScript strcmp()?
• Tutorials Point: JavaScript String - localeCompare() Method

Solution 2

Well in JavaScript you can check two strings for values same as integers so yo can do this:

• "A" < "B"
• "A" == "B"
• "A" > "B"

And therefore you can make your own function that checks strings the same way as the strcmp().

So this would be the function that does the same:

function strcmp(a, b)
{   
    return (a<b?-1:(a>b?1:0));  
}

Solution 3

You can use the comparison operators to compare strings. A strcmp function could be defined like this:

function strcmp(a, b) {
    if (a.toString() < b.toString()) return -1;
    if (a.toString() > b.toString()) return 1;
    return 0;
}

---

Edit    Here’s a string comparison function that takes at most min { length(a), length(b) } comparisons to tell how two strings relate to each other:

function strcmp(a, b) {
    a = a.toString(), b = b.toString();
    for (var i=0,n=Math.max(a.length, b.length); i<n && a.charAt(i) === b.charAt(i); ++i);
    if (i === n) return 0;
    return a.charAt(i) > b.charAt(i) ? -1 : 1;
}

Comments

[Pointy]

But this routine does exactly what the OP doesn't want to do: there are two string comparisons (let alone those function calls to "toString").

[Pointy]

Again, read the original question!! The point is to avoid doing more than one string comparison.

[Gumbo]

@Pointy: It’s not possible with just one comparison. You need at least min {a.length, b.length} steps (compare two characters at a time) to determine if the strings are equal or not. (Even localeCompare will do that internally.)

[Pointy]

No, localeCompare will not do that internally. Comparing the characters is implemented as a subtraction, so as soon as there's a non-zero result of that operation you know the answer. Your answer can re-compare possibly all the characters of each string.

[Gumbo]

@Pointy: But the substraction is done character by character. And that’s the point. That takes at most (and not at least as I wrote) min {a.length, b.length} steps (in the case where both strings are equal). But you’re right. It’s better to test for equality first as that takes the most steps.

[Cipi]

Oh sorry. Didn't see that... At least this works for someone. =|

[kennebec]

Unfortunately, stringCompare is not reliable. Opera, IE, Firefox, Chrome and Safari all return 1 for 'dog'.localeCompare('cat'), which is to be expected, and -1 when you reverse the caller and the argument. BUt capital letters behave oddly- 'dog'.localeCompare('Dog') Of the browsers I tested, only Safar 4 returned 1. It returns -1 in IE8 and firefox 3, and Opera 9 and Chrome both return +32.

[HRJ]

@Gumbo localeCompare doesn't have to be in Javascript right? It could be natively implemented. Or I have missed something...

[Pointy]

Maybe I'm missing something. When you code up two completely separate Javascript string comparisons, what happens? Well, the first comparison gets started and (let's say) it notices a mismatch at character position 5. That is, characters 1 through 4 match, but character 5 mismatches. If the first Javascript comparison is a "!=" comparison (or "=="; whatever), then we know that the strings are not equal. However, in the low-level comparison code, we also know the answer to "<" and ">". But we throw away that knowledge when we start the next (Javascript) comparison, and re-compare chars 1-4.

[Gumbo]

@Pointy: You probably meant something like the algorithm in my update, right?

[Pointy]

@Gumbo yes, exactly. Of course, "localeCompare" is part of the runtime and therefore a C/C++ (or whatever) implementation. I wonder how good a job V8 would do at optimizing out the "charAt" calls?

[Ghost]

You can use toLowerCase or toLocaleLowerCase when you want case insensitive comparisons.

[JoshVarty]

I think it's important to note that V8 (Chrome) seems to interpret ECMA-262 differently than IE/Firefox on localeCompare. For example: "a".localeCompare("Z") should return -1 but instead returns 7 which is the charcode of "a" - charcode of "Z". Unfortunately, the language in the specification is loose, specifying that localeCompare() returns negative number, a positive number or 0. (Not specifically -1, 1, 0). I filed a bug report in the hope this might change, but it's been an issue since August 2010, so I doubt it will.

[Ilya Kharlamov]

''.localeCompare.call(string_a, string_b);

[PositiveGuy]

I don't understand the > and < when comparing strings...

[Gerben Jacobs]

Apparently you're better off comparing it yourself; jsperf.com/localecompare

[HRJ]

@GerbenJacobs Thanks for that. I also derived a bigger benchmark (binary search) out of that: jsperf.com/localecompare/2

[vf.]

jsperf.com/localecompare is wrong, there is invalid expression: s1 < s1 ? -1 : s1 > s2 ? 1 : 0;

[Alex McMillan]

What if the values being sorted could be strings OR numbers, and you don't know at design time? String.prototype.localeCompare.call(a, b) ?

[kayakyakr]

Should favor using === as the first comparison. It's faster than < or >. Wrote a new jsperf revision to demonstrate: jsperf.com/localecompare/33

[Yura]

I see that in 2021 localeCompare works good and old comments about result deviation in a different browsers are no longer actual