0

Just wondering, I have seen diverging opinions on this subject.

If you take an array of strings, say 1000 elements and use the sort method. Which one would be faster? An array in which the strings are 100 characters long or one in which the strings are only 3 characters long?

I tried to test but I have a bug with Firebug at the moment and Date() appears too random.

Thank you!

Improve this question
5
  • I don't see how 100-character strings could possibly be faster than 3-character strings. Commented Jul 11, 2012 at 20:28
  • After what appears to be a less random Date get milliseconds... the longest string is faster? This seems a litte counterintuitive. Commented Jul 11, 2012 at 20:30
  • I do agree with you minitech, but still I wonder how big the gain would be to see if it justifies the time that cropping the strings in a copied array would take. Commented Jul 11, 2012 at 20:31
  • They're the same, just in general. And don't bother truncating strings unless you have a ton that are the same as each other. jsperf.com/sorting-strings-length-difference Commented Jul 11, 2012 at 20:33
  • Thank you minitech!! You're right, most of the time 100 seems to be either equal or faster. Commented Jul 11, 2012 at 20:39

2 Answers 2

Reset to default
1

It depends what the strings contain, if they contain different characters, the rest of the string doesn't have to be checked for comparison so it doesn't matter.

For example, "abc" < "bca" Here only the first character had to be checked.

You can read the specs for this: http://ecma-international.org/ecma-262/5.1/#sec-11.8.5

Specifically:

Else, both px and py are Strings

  1. If py is a prefix of px, return false. (A String value p is a prefix of String value q if q can be the result of concatenating p and some other String r. Note that any String is a prefix of itself, because r may be the empty String.)
  2. If px is a prefix of py, return true.
  3. Let k be the smallest nonnegative integer such that the character at position k within px is different from the character at position k within py. (There must be such a k, for neither String is a prefix of the other.)
  4. Let m be the integer that is the code unit value for the character at position k within px.
  5. Let n be the integer that is the code unit value for the character at position k within py.
  6. If m < n, return true. Otherwise, return false.
Improve this answer
Sign up to request clarification or add additional context in comments.

5 Comments

No, the sort() [spec] does not use the abstract compare algorithm - but the rest of the answer is true, so +1
@Bergi the specs say that the custom sort function is implementation defined there. So if you use .sort() without passing a callback function, then the implementation defined function is used?
@Bergi actually it says this If xString < yString, return −1. If xString > yString, return 1. (In a case where compareFn is undefined). But yeah I'm not really sure, I just assume it does this with strings. :P
No, it always uses the "SortCompare abstract operation" - and when no custom function is given, it applies toString on both values and compares them - yes, and that will (I guess) be lexicographically as in 11.8.5 :-)
@Bergi yes I am assuming no custom function is passed to .sort(): P
1

It really depends on how different the strings are, but I guess the differences would be minimal due to the fact that what's called to do the comparison is way slower than actually comparing the strings.

But then again, modern browsers use some special optimizations for sort, so they cut some comparisons to speed things up. And this would happen more often sorting an array of short strings.

And FYI, if you want to make some benchmark, use a reliable tool like jsPerf.

Improve this answer

8 Comments

The difference is significant: jsperf.com/sorting-strings-length-difference/2
Well, you created a very bad case on purpose. When things are more random, the results are much more similar: jsperf.com/sorting-strings-length-difference/4
What do you mean by "cut some comparisons"?
@MaxArt I did indeed create some kind of worst case, since I assumed that was what you were talking about.
@Bergi I mean something like this: github.com/jquery/sizzle/blob/master/sizzle.js#L827
|

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.