The Curious Case of JavaScript’s `sort`(influxdata.com)
influxdata.com
The Curious Case of JavaScript’s `sort`
https://influxdata.com/blog/the-chronograf-files-the-curious-case-of-javascripts-sort/
15 comments
Certainly it's an easy mistake to make, but most JS devs tend to encounter it the very first time they call sort() on anything that isn't epoch dates. The fact that the author's code worked for years is a pretty exotic edge case!
[deleted]
This behavior has been documented forever, and the broken code written in ignorance of this behavior passed into production because of inadequate testing. Nothing you've said countered these facts.
Sounds like your solution would have been to properly read documentation of critical sectors of your code. Assuming that just calling `.sort()` on your arbitrary data would give you exactly what you want was a mistake. Not testing this code was also a mistake, because any combination of different length integers would have shown you this problem very early on, saving you some embarrassment and loss of user trust.
Really, their testing was inadequate. If your product is a timeline graph, you should test it with data covering a large range across the possible time values. A single date from before roughly 2000 would have uncovered the problem.
(Not that I always test adequately, mind you.)
(Not that I always test adequately, mind you.)
MySQL exhibits similar behavior if you're comparing numbers stored in a field with string-ish type (eg, varchar):
mysql> select cast(123 as char(255)) > "2";
+------------------------------+
| cast(123 as char(255)) > "2" |
+------------------------------+
| 0 |
+------------------------------+
1 row in set (0.00 sec)
Stop hijacking my scrollwheel.
So if I'm understanding correctly, JS sort sorts numbers by their string value? That's crazy. And it seems you have to add a compare function just to do a basic operation to sort numbers.
> So if I'm understanding correctly, JS sort sorts numbers by their string value? That's crazy.
It's JavaScript … it doesn't have to be sane; we'll use it anyway.
I think that Erlang had the most elegant solution: it defines a total order over all objects (number < atom < reference < fun < port < pid < tuple < list < bit string). Of course, Erlang's 'strings' are pretty inelegant (they're just lists of integers, which are printed as strings if they happen to incidentally be valid characters), so I guess there's some Law of Conservation of Bogosity at play here.
It's JavaScript … it doesn't have to be sane; we'll use it anyway.
I think that Erlang had the most elegant solution: it defines a total order over all objects (number < atom < reference < fun < port < pid < tuple < list < bit string). Of course, Erlang's 'strings' are pretty inelegant (they're just lists of integers, which are printed as strings if they happen to incidentally be valid characters), so I guess there's some Law of Conservation of Bogosity at play here.
This is what happens when people try do to arithmetic in a typeless language. Javascript does not really have a number type; it just has values. Sometimes it infers that you want to do arithmetic on them.
What is the correct order of the items ["2", 10, "banana", [[]], "", 1]?
See also https://www.destroyallsoftware.com/talks/wat
Bonus: sometimes you can get the same kind of behaviour in Excel when importing CSV.
What is the correct order of the items ["2", 10, "banana", [[]], "", 1]?
See also https://www.destroyallsoftware.com/talks/wat
Bonus: sometimes you can get the same kind of behaviour in Excel when importing CSV.
The language isn't typeless. Other language (python and ruby, among many others) manage to integer and string comparision correct.
It is trickier when someone compares "2" and 3, should we say it's invalid (my preference) or turn 2 into an integer, or 3 into a string? However, there is NO reason for there to be an issue comparing 1 and 11. This is just an unfortunately mistake that is too deeply baked into the language to fix at this point.
It is trickier when someone compares "2" and 3, should we say it's invalid (my preference) or turn 2 into an integer, or 3 into a string? However, there is NO reason for there to be an issue comparing 1 and 11. This is just an unfortunately mistake that is too deeply baked into the language to fix at this point.
Where is the issue comparing 1 and 11? 1 < 11 still returns true. [11,1].sort((a,b) => a -b) still returns [1, 11].
Sorry, 1 and 11 isn't a problem in javascript. Insert two troublesome numbers :)
Seems like it should be up to you to come up with the troublesome numbers, since you're the one making claims.
Oh sorry, here we go.
> [2] < [11]
false
Then your knowledge of Javascript is sorely lacking. To make arrays work like that in Javascript would be very complicated, and counterintuitive to those who know how Javascript arrays work.
I agree my knowledge of JavaScript is lacking, I just (wrongly) assumed arrays would act similarly to other languages.
Obviously it's too late to change JavaScript now, but Iwould be interested to know why it would have been complicated to do this differently originally, and why it would be countintuitive? Is there anything I can read about this kind of thing?
Obviously it's too late to change JavaScript now, but Iwould be interested to know why it would have been complicated to do this differently originally, and why it would be countintuitive? Is there anything I can read about this kind of thing?
Yeah, that's more or less what you get when you hack a language together in 10 days... Arrays in JS are just a special case of objects, which are just name-value hashmaps. Although they usually have some optimizations in their internal implementation.
I guess "Javascript: the Good Parts" is as good a place to start as any. It doesn't really go into the design decisions though.
I guess "Javascript: the Good Parts" is as good a place to start as any. It doesn't really go into the design decisions though.
It's not that it sometimes infers what you want to do. It's that it has defaults and if you want to do something besides the default, you need to specify what it is you want to do.
No, this has nothing to do with how "JS sorts numbers". JavaScript sorts arrays by using a default comparator that runs .toString and compares unicode code point values (with safe handling around null/undefined).
There is no concept of a typed number array in JS. There is just "Array", and an array's contents can be heterogenous.
Imagine the following:
For a more detailed read, see: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
There is no concept of a typed number array in JS. There is just "Array", and an array's contents can be heterogenous.
Imagine the following:
['a', 'c', 'b'].sort() // ['a','b','c']
['a', 1].sort() // [1, 'a']
[1, ['foo'], {bar: 'baz'}, 'a', '2', null, undefined].sort() // [1, '2', {bar:'baz'}, 'a', ['foo'], null, undefined]
For a more detailed read, see: https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
> JavaScript sorts arrays by using a default comparator that runs .toString and compares unicode code point values (with safe handling around null/undefined).
Is there an explanation somewhere of how they decided on that as the default comparator? My first inclination would have been to use "<" as the default comparator. That would sort purely numeric arrays numerically, and purely string arrays lexically, leaving only the case of arrays that mix numerical and non-numerical elements needing the programmer to step in and give an explicit comparator.
Is there an explanation somewhere of how they decided on that as the default comparator? My first inclination would have been to use "<" as the default comparator. That would sort purely numeric arrays numerically, and purely string arrays lexically, leaving only the case of arrays that mix numerical and non-numerical elements needing the programmer to step in and give an explicit comparator.
> There is no concept of a typed number array in JS
Note that nowadays there are indeed Int16Array, Float32Array, and so forth, and their sort methods work numerically like you'd expect.
Note that nowadays there are indeed Int16Array, Float32Array, and so forth, and their sort methods work numerically like you'd expect.
One of the many reasons why I keep away from JS - it deviates from the norm without good reason, in arbitrary places.
Array#sort sorts all elements by their converted string value.
It may seem like a strange way to spec the language, but I'm not sure what would have been better. It wouldn't make sense for sort to have to run through the array checking types before it starts, or for it to dynamically change what kind of comparison it does depending on the types of each pair of elements being compared.
It may seem like a strange way to spec the language, but I'm not sure what would have been better. It wouldn't make sense for sort to have to run through the array checking types before it starts, or for it to dynamically change what kind of comparison it does depending on the types of each pair of elements being compared.
It might have made more sense to not have default behavior and force the user to specify how they want to sort. They could also have done what PHP did and provided several different .sort functions depending on how you want to sort.
I think ECMA4 proposed behavior flags, so you could do:
arr1.sort( Array.NUMERICAL | Array.DESCENDING )
arr2.sort( Array.CASE_INSENSITIVE )
What would make sense (and what most other languages seem to do) is compare elementwise, using whatever ordering javascript would usually use. Therefore [X] < [Y] would be true whenever X<Y is true (for example)
That would have undesirable side effects - e.g. it would mean the results of the sort are not necessarily specified. If the array contains NaN, for example, calling a sort like that would have different results depending on the order in which the elements are compared, which would likely vary by JS engine.
I don't really understand your problem -- this is how array comparison is implemented in C++, Python, Ruby, Java (when using the default isComparable on most array-list types) and Haskell (from the languages I use frequently). Javascript is the only weird outlier.
I don't know what you're taking issue with. The results of sorting in JS with a simple (a<b) comparison will necessarily vary by JS implementation, and I'm suggesting that would be a drawback for a default specified behavior.
E.g.:
E.g.:
[1,3,NaN,2,5].sort( (a,b) => a<b ? -1 : 1 )
// Chrome: [ NaN, 1, 2, 3, 5 ]
// Firefox: [ 2, 5, NaN, 1, 3 ]I am refering to this:
In (almost) every other language ever the following is true. In Javascript it is false.
[[2], [11]].sort() // Javascript: [ [11], [2] ]
In (almost) every other language ever the following is true. In Javascript it is false.
[2] < [11]
[[2], [11]].sort() // Javascript: [ [11], [2] ]
You're overlapping a couple of separate things. The article and my initial comment were about sorting arrays of numbers. If you're sorting arrays of arrays, the behavior of ([2] < [11]) is slightly beside the point, since Array.sort() doesn't compare the arrays, it converts all elements to strings first.
As for the actual behavior of ([2] < [11]), the issue there is that "Array" is not a type in JS, arrays are just objects that happen to have properties called "0" and "1" and so on. Hence operators don't have any special cases for arrays, so getting comparisons to work like you had hoped would mean the comparison operator would need weird special rules where, whenever it's passed two objects it checks if they both have properties called "0", and if so do one thing, if not do something else, etc.
As for the actual behavior of ([2] < [11]), the issue there is that "Array" is not a type in JS, arrays are just objects that happen to have properties called "0" and "1" and so on. Hence operators don't have any special cases for arrays, so getting comparisons to work like you had hoped would mean the comparison operator would need weird special rules where, whenever it's passed two objects it checks if they both have properties called "0", and if so do one thing, if not do something else, etc.
That still wouldn't specify how to sort [ 1, [ 5 ], "hi", { a: 5 }, new Date(), /test/ ] , and which way to sort that would "make sense" anyway? Better to specify something simple but incomplete than something complicated that will still necessarily be either incomplete or useless or both.
You should have read W3Schools:
> However, if numbers are sorted as strings, "25" is bigger than "100", because "2" is bigger than "1".
> However, if numbers are sorted as strings, "25" is bigger than "100", because "2" is bigger than "1".
Ah ah nope!
You should read MDN
The default sort order is according to string Unicode code points.
If compareFunction is not supplied, elements are sorted by converting them to strings and comparing strings in Unicode code point order. For example, "Banana" comes before "cherry". In a numeric sort, 9 comes before 80, but because numbers are converted to strings, "80" comes before "9" in Unicode order.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
You should read MDN
The default sort order is according to string Unicode code points.
If compareFunction is not supplied, elements are sorted by converting them to strings and comparing strings in Unicode code point order. For example, "Banana" comes before "cherry". In a numeric sort, 9 comes before 80, but because numbers are converted to strings, "80" comes before "9" in Unicode order.
https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
And just to throw another wrench in there, because it sorts by Unicode code points, capitals come before lowercase.
So this:
['Banana', 'cherry', 'bagel', 'apple'].sort()
Will produce this order:
["Banana", "apple", "bagel", "cherry"]
So this:
['Banana', 'cherry', 'bagel', 'apple'].sort()
Will produce this order:
["Banana", "apple", "bagel", "cherry"]
Yet another reason why you shouldn't have read W3 schools.
Exactly. If even W3Schools describes the default behavior, it's not exactly a secret.
have seen people raising big uffs-oohs-aahs because of stackoverflow-driven-development :)
developer mozilla helps https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
unit tests help !
developer mozilla helps https://developer.mozilla.org/en-US/docs/Web/JavaScript/Refe...
unit tests help !
The suggestion:
function compareNumbers(a, b) {
return a - b;
}
All numbers in JS are floats. Overflow and underflow are represented as positive and negative infinity while the check itself looks for 0, greater than zero, less than zero. Both infinities qualify as greater or less than zero (respectively), so I don't believe this problem exists.
Javascript numbers are reals, not integers. If they become too large (positively or negatively), they become +Infinity or -Infinity.
ITT: people who expect a language to work just like they want it to instead of reading the docs for the language.
I had some javascript where I wanted to sort a list of list of integers as follows:
EDIT: I replaced the word 'lexicographic' with 'element-wise', as I think it might be causing confusion.
* Sort each inner list smallest to largest
* Sort the list of lists lexicographically
EDIT: I replaced the word 'lexicographic' with 'element-wise', as I think it might be causing confusion.
What would "lexicographic" comparison of two arrays mean? As in, what's the canonical string conversion, and how should commas be treated in the ordering? (eg, does `[1,2]` come before or after `[12]` ?)
Admittedly, "lexicographic" sorting of numbers is pretty wonky too, but at least there's a pretty canonical string representation of a given number.
It seems like a pretty idiosyncratic need without an obvious canonical interpretation, so I'm a little surprised by your surprise at there not being standardish library function for it.
Edit: Oh, how embarrassing, I misunderstood the linked post (I thought it was about JS lexicographically sorting integers, rather than arrays of integers). Well, I guess my surprise applies to both you and the author of the link.
Admittedly, "lexicographic" sorting of numbers is pretty wonky too, but at least there's a pretty canonical string representation of a given number.
It seems like a pretty idiosyncratic need without an obvious canonical interpretation, so I'm a little surprised by your surprise at there not being standardish library function for it.
Edit: Oh, how embarrassing, I misunderstood the linked post (I thought it was about JS lexicographically sorting integers, rather than arrays of integers). Well, I guess my surprise applies to both you and the author of the link.
Lexicographic ordering of two arrays X and Y is (I think) the standard ordering of arrays. Algorithm something like (pseudocode, ignoring different length arrays):
[1,1] < [2,2] < [11,11] < [22,22]
Instead Java says [1,1] < [11,11] < [2,2] < [22,22], because it compares the arrays as strings.
for(i = 0; i < length(X); ++i) {
if(X[i] < Y[i]) X is smaller
if(X[i] > Y[i]) Y is smaller
}
arrays are equal!
[1,1] < [2,2] < [11,11] < [22,22]
Instead Java says [1,1] < [11,11] < [2,2] < [22,22], because it compares the arrays as strings.
Yes - even Typescript, when arrays are given types, doesn't fix it even though it could be done easily.
var x : number[] // should compile: x.sort(function(a,b) { return a - b; })
var y : string[] // should compile: y.sort()
The reason that this isn't done is due to a misplaced ideology about "typescript is just javascript" - or some similar nonsense.
The bigger problem here is that we are using tools that are designed by a committee, and we have almost no hope of getting this fixed.
var x : number[] // should compile: x.sort(function(a,b) { return a - b; })
var y : string[] // should compile: y.sort()
The reason that this isn't done is due to a misplaced ideology about "typescript is just javascript" - or some similar nonsense.
The bigger problem here is that we are using tools that are designed by a committee, and we have almost no hope of getting this fixed.
It can easily be fixed by passing a sorting function...
Well, but then I have to write a comparison function for two arrays of integers. It's not that hard to write, but it took me long enough that I wished the language had it built in (should probably look for it in npm.. if there is left-bad, there must be array-order!)
It is a very easy mistake to make, you pick 'sort' and the resulting code does what you expect. As long as all the timet's have the same number of digits then the string comparison works. You have to have a data that crosses 9/8/2001 to see the problem. (or 3/3/1973 before that)
The javascript compiler isn't going to tell you about this and it only hits a problem with dates older than most programs that are written in javascript.