如果显式定义了排序顺序，则排序速度非常慢

Question

正如您可以在下面的代码中检查的那样，通过在属性名称前面加上+或-来定义排序顺序会导致排序速度大大变慢。知道为什么吗？

默认排序(值(：5.84ms

升序排序(+值(：58.59ms

降序排序(-值(：49.28ms

value 和 +value 之间存在差异(两者都返回完全相同的排序顺序(这一事实让我非常困惑。

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')

Answer 1

编写一个返回比较器的函数会更常见，尽管在这种情况下，性能差异似乎取决于 V8 JS 引擎在匹配正则表达式的情况下如何优化代码。

因此，更规范的用法可能是：

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结构中出现相同的值。

Answer 2

这更像是一个注释，但对于一个太长的人来说：对于一个测试场景，如果密钥稍后被扣留，是否有 V8 性能差异，我尝试存储一个原始密钥(正则表达式的结果(并在第一次比较时获取对象的实际密钥(理论上应该是一个暂留或至少可优化的字符串(。

下面是相同的代码，但在排序函数中设置了一个属性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')

Answer 3

我发现动态构建比较函数可以避免速度变慢，并且实际上在我的测试中(尽管很少(在几乎所有情况下都快得多。

      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')