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 < [email protected]> 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 })) > >
_______________________________________________ es-discuss mailing list [email protected] https://mail.mozilla.org/listinfo/es-discuss
