如果显式定义sorting顺序,则sorting非常慢

正如你可以检查下面的代码,通过在属性名称前加一个+或者-定义一个sorting顺序,结果是一个非常慢的sorting。 任何想法为什么?

默认sorting(值): 5.84ms

Ascendingsorting(+值): 58.59ms

降序排列( – 值): 49.28ms

value+value之间存在差异(这两者都返回完全相同的sorting顺序)这一事实对我来说非常混乱。

 let arr = [] for (let i = 0; i < 10000; ++i) { arr.push({ _id: 'doc' + i, value: Math.random(), k: i % 20 }) } function sort (...keys) { let data = {} data.sort = [] keys.forEach(key => { const newKey = key.replace(/(\-|\+)/g, '') const order = key[0] === '-' ? -1 : 1 data.sort.push({ key: newKey, order: order }) }) return data } function compare (sortData, a, b) { for (let i = 0; i < sortData.length; ++i) { const data = sortData[i] const _a = a[data.key] const _b = b[data.key] if (_a !== _b) return _a > _b ? data.order : -data.order } return 0 } function exec (data) { let r = arr.slice() if (data.sort) { r.sort((a, b) => { let r = compare(data.sort, a, b) return r }) } return r } function time (f) { let start = performance.now() f() return performance.now() - start } function test (f, n) { let total = 0 for (let i = 0; i < n; ++i) total += time(f) return total / n } const q1 = sort('value') const q2 = sort('+value') const q3 = sort('-value') const sortDefault = () => exec(q1) const sortAsc = () => exec(q2) const sortDesc = () => exec(q3) console.log(' Default Sort (value):', test(sortDefault, 10).toFixed(2) + 'ms') console.log(' Ascending Sort (+value):', test(sortAsc, 10).toFixed(2) + 'ms') console.log('Descending Sort (-value):', test(sortDesc, 10).toFixed(2) + 'ms') 

编写一个返回比较器的函数通常会更平常,但在这种情况下,性能差异可能与V8 JS引擎在正则expression式匹配的情况下如何优化代码有关。

因此更规范的用法可能是:

 function buildSort(...keys) { if (typeof keys[0] === "string") { keys = keys.map(key => { const order = key[0] === '-' ? -1 : 1 key = key.replace(/(\-|\+)/g, '') return { key, order }; }) } return (a, b) => { for (let { key, order } of keys ) { const _a = a[key]; const _b = b[key]; if (_a !== _b) return _a > _b ? order : -order } return 0 } } function exec(comparator) { return arr.slice().sort(comparator); } ... const q1 = buildSort({ key: 'value', order: 1 }); const q2 = buildSort({ key: 'value', order: -1 }); const q3 = buildSort('+value') 

在运行NodeJS 6.9.1的笔记本电脑上,通过{ key: 'value', order: 1 }或者"value"给出0.015秒的运行时间,而传递"+value"在0.46秒内运行,即使名义上这些值相同出现在比较器内使用的keys结构中。

这意味着更多的是作为一个评论,但是太长了一个:对于一个testing场景来看看是否有一个V8的性能差异,如果密钥后来被拦截,我试图存储一个原始密钥(正则expression式的结果)在第一次比较的对象的实际关键(理论上应该是一个interned或至less可优化的string)。

下面是相同的代码,但是在sort函数中设置了一个属性rawkey而不是'key',并且在内部获得密钥与if(!data.key) data.key = Object.keys(a).filter(k=>k==data.rawkey)[0]; 无论是好还是坏,在Chrome中为我创造了相同的性能。 实现只是一个展示案例,并不是安全的,并不是所有的对象都可能具有实际的属性

 let arr = [] for (let i = 0; i < 10000; ++i) { arr.push({ _id: 'doc' + i, value: Math.random(), k: i % 20 }) } function sort (...keys) { let data = {} data.sort = [] keys.forEach(key => { const newKey = key.replace(/(\-|\+)/g, '') const order = key[0] === '-' ? -1 : 1 data.sort.push({ rawkey: newKey, order: order }) }) return data } function compare (sortData, a, b) { for (let i = 0; i < sortData.length; ++i) { const data = sortData[i]; if(!data.key) data.key = Object.keys(a).filter(k=>k==data.rawkey)[0]; const _a = a[data.key] const _b = b[data.key] if (_a !== _b) return _a > _b ? data.order : -data.order } return 0 } function exec (data) { let r = arr.slice() if (data.sort) { r.sort((a, b) => { let r = compare(data.sort, a, b) return r }) } return r } function time (f) { let start = performance.now() f() return performance.now() - start } function test (f, n) { let total = 0 for (let i = 0; i < n; ++i) total += time(f) return total / n } const q1 = sort('value') const q2 = sort('+value') const q3 = sort('-value') const sortDefault = () => exec(q1) const sortAsc = () => exec(q2) const sortDesc = () => exec(q3) console.log(' Default Sort (value):', test(sortDefault, 10).toFixed(2) + 'ms') console.log(' Ascending Sort (+value):', test(sortAsc, 10).toFixed(2) + 'ms') console.log('Descending Sort (-value):', test(sortDesc, 10).toFixed(2) + 'ms') 

我发现dynamic构build比较函数可以避免放缓,而且在我的(尽pipe最小的)testing中几乎所有情况下实际上都快得多。

  Default ( value): 5.47ms Default (+value): 54.17ms Default (-value): 51.90ms eval Function ( value): 3.25ms eval Function (+value): 3.51ms eval Function (-value): 2.99ms 
 let arr = [] for (let i = 0; i < 10000; ++i) { let o = { _id: 'doc' + i, value: Math.random() } arr.push(o) } function sortKeys (...keys) { const data = {} data.sort = [] keys.forEach(key => { if (typeof key === 'string') key = getSortObject(key) if (key.order === undefined) key.order = 1 data.sort.push(key) }) return data } function getSortObject (str) { if (str.match(/^(\+|\-)/)) { return { key: str.substr(1), order: -1 } } else { return { key: str, order: 1 } } } function exec (data, compFn) { let r = arr.slice() if (data.sort) { r.sort(compFn(data.sort)) } return r } // Old comparator, seems to cause optimization problems in the V8 engine. (Chrome/NodeJS/etc.) function comparison (sdata) { return function (a, b) { for (let i = 0; i < sdata.length; ++i) { const data = sdata[i] const _a = a[data.key] const _b = b[data.key] if (_a !== _b) return _a > _b ? data.order : -data.order } return 0 } } // Builds a function from the sort keys. function getCompFunc (sortData) { let str = '' sortData.forEach(sort => { str += `if(a.${sort.key}${sort.order === 1 ? '>' : '<'}b.${sort.key})return 1;` str += `if(a.${sort.key}${sort.order === 1 ? '<' : '>'}b.${sort.key})return -1;` }) str += `return 0;` return Function('a', 'b', str) } function time (f) { let start = performance.now() f() return performance.now() - start } function test (f, n) { let total = 0 for (let i = 0; i < n; ++i) total += time(f) return total / n } const q1 = sortKeys('value') const q2 = sortKeys('+value') const q3 = sortKeys('-value') const sortDefault = () => exec(q1, comparison) const sortAsc = () => exec(q2, comparison) const sortDesc = () => exec(q3, comparison) const sortDefaultEval = () => exec(q1, getCompFunc) const sortAscEval = () => exec(q2, getCompFunc) const sortDescEval = () => exec(q3, getCompFunc) console.log('A:', test(sortDefault, 5).toFixed(2) + 'ms') console.log('B:', test(sortAsc, 5).toFixed(2) + 'ms') console.log('C:', test(sortDesc, 5).toFixed(2) + 'ms') console.log('-') console.log('D:', test(sortDefaultEval, 5).toFixed(2) + 'ms') console.log('E:', test(sortAscEval, 5).toFixed(2) + 'ms') console.log('F:', test(sortDescEval, 5).toFixed(2) + 'ms')