javascript - 如果显式定义排序顺序，排序会非常慢

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