Array#sort implementations are not interoperable

Jussi Kalliokoski jussi.kalliokoski at gmail.com
Sat Dec 1 07:12:55 PST 2012


Oops, sorry everyone, looks like I had a serious copy-paste mishap with
gmail. :/

On Sat, Dec 1, 2012 at 3:10 PM, Jussi Kalliokoski <
jussi.kalliokoski at gmail.com> wrote:

> Hello everyone,
>
> I was thinking about sorting algorithms yesterday and I realized that ES
> implementations may have different sorting algorithms in use, and decided
> to try it out. Now, if you sort strings or numbers, it doesn't matter, but
> you may be sorting objects by a key and this is where things get nasty
> (think non-deterministic vs deterministic). Here's an example:
>
> function shuffle (arr, depth) {
>   var tmp = []
>
>   var pi = String(Math.PI).substr(2)
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>     i = (i + +pi[p]) % arr.length
>     p = (p + 1) % pi.length
>
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>   }
>
>   if (!depth) return tmp
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>   return {
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
> var sorted = original.slice().sort(function (a, b) {
>
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
> console.log(sorted.map(function (item) { return item.unique }))
>
> function shuffle (arr, depth) {
>   /* it's a silly way to shuffle, but at least it's deterministic. */
>   var tmp = []
>
>   var pi = String(Math.PI).substr(2)
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>     i = (i + +pi[p]) % arr.length
>     p = (p + 1) % pi.length
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>   }
>
>   if (!depth) return tmp
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>   return {
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
> var sorted = original.slice().sort(function (a, b) {
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
> console.log(sorted.map(function (item) { return item.unique }))
>
> In Firefox, you get:
>
> ["s", "m", "q", "l", "e", "b", "k", "i", "f", "g", "o", "j", "d", "t",
> "n", "c", "a", "p", "h", "r", "u"]
> ["f", "h", "a", "e", "b", "g", "j", "d", "c", "l", "r", "q", "o", "k",
> "t", "n", "p", "u", "i", "m", "s"]
>
> In Chrome, you get:
>
> ["s", "m", "q", "l", "e", "b", "k", "i", "f", "g", "o", "j", "d", "t",
> "n", "c", "a", "p", "h", "r", "u"]
> ["f", "h", "a", "g", "e", "b", "j", "d", "c", "l", "r", "o", "q", "k",
> "n", "t", "p", "u", "i", "m", "s"]
>
> Real world consequences of this may include:
>
>  * A blog where posts are sorted by date ("YYYY/MM/DD"). Different
> browsers will show the posts in different order if Array#sort is used to
> accomplish this. Not a very severe consequence.
>  * A spreadsheet application. If it has some order-dependent algorithm to
> calculate values, different browsers can give different results for the
> same research data.
>
> Now I'm not sure what could be done to this, if anything even should be,
> just thought I'd bring it up.
>
> Cheers,
> Jussi
>
> function shuffle (arr, depth) {
>   var tmp = []
>
>   var pi = String(Math.PI).substr(2)
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>     i = (i + +pi[p]) % arr.length
>
>     p = (p + 1) % pi.length
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>   }
>
>   if (!depth) return tmp
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>   return {
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
> var sorted = original.slice().sort(function (a, b) {
>
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
> console.log(sorted.map(function (item) { return item.unique }))function shuffle (arr, depth) {
>   var tmp = []
>
>
>   var pi = String(Math.PI).substr(2)
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>     i = (i + +pi[p]) % arr.length
>     p = (p + 1) % pi.length
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>
>   }
>
>   if (!depth) return tmp
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>
>   return {
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
> var sorted = original.slice().sort(function (a, b) {
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
> console.log(sorted.map(function (item) { return item.unique }))function shuffle (arr, depth) {
>   var tmp = []
>
>   var pi = String(Math.PI).substr(2)
>
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>     i = (i + +pi[p]) % arr.length
>     p = (p + 1) % pi.length
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>   }
>
>   if (!depth) return tmp
>
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>   return {
>
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
> var sorted = original.slice().sort(function (a, b) {
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
>
> console.log(sorted.map(function (item) { return item.unique }))function shuffle (arr, depth) {
>   var tmp = []
>
>   var pi = String(Math.PI).substr(2)
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>
>     i = (i + +pi[p]) % arr.length
>     p = (p + 1) % pi.length
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>   }
>
>   if (!depth) return tmp
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
>
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>   return {
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
>
> var sorted = original.slice().sort(function (a, b) {
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
> console.log(sorted.map(function (item) { return item.unique }))
>
> function shuffle (arr, depth) {
>   var tmp = []
>
>   var pi = String(Math.PI).substr(2)
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>     i = (i + +pi[p]) % arr.length
>     p = (p + 1) % pi.length
>
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>   }
>
>   if (!depth) return tmp
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>   return {
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
> var sorted = original.slice().sort(function (a, b) {
>
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
> console.log(sorted.map(function (item) { return item.unique }))function shuffle (arr, depth) {
>   var tmp = []
>
>
>   var pi = String(Math.PI).substr(2)
>   var i = 0
>   var p = 0
>
>   while (arr.length) {
>     i = (i + +pi[p]) % arr.length
>     p = (p + 1) % pi.length
>     tmp.push(arr[i])
>     arr.splice(i, 1)
>
>   }
>
>   if (!depth) return tmp
>
>   return shuffle(tmp, depth - 1)
> }
>
> var unique = 'abcdefghijklmnopqrstu'
> var sorter = 'deggeaeasemiuololizor'
>
> var arr = Array.apply(null, Array(unique.length)).map(function (a, i) {
>
>   return {
>     unique: unique[i],
>     sorter: sorter.charCodeAt(i)
>   }
> })
>
> var original = shuffle(arr, 3)
> var sorted = original.slice().sort(function (a, b) {
>   return a.sorter - b.sorter
> })
>
> console.log(original.map(function (item) { return item.unique }))
> console.log(sorted.map(function (item) { return item.unique }))
>
>
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://mail.mozilla.org/pipermail/es-discuss/attachments/20121201/44021616/attachment-0001.html>


More information about the es-discuss mailing list