时间戳

首页 > 解决方案 > 如何根据计算量大的键函数有效地对数组进行排序？

javascript - 如何根据计算量大的键函数有效地对数组进行排序？

问题描述

我问了这个关于使用键函数对数组进行排序的问题，结果发现无法避免使用比较函数。

问题是

  1. 我有一个计算量很大的关键函数，我不得不把它变成一个比较函数
  2. 我正在对一组对象进行排序，这意味着我不能使用哈希表来记忆我的关键函数的结果

这是一个示例数组和（便宜的）键功能：

myArr = [{'foo': 5, 'bar': 'hello'}, {'foo': 3, 'bar': 'world'}];
keyFunc = obj => obj.foo;  // sort by the value of the `foo` attribute

myArr.sort(???);
// result should be [{'foo': 3, 'bar': 'world'}, {'foo': 5, 'bar': 'hello'}]

鉴于这些情况，如何有效地对数组进行排序？

标签： javascriptsorting

解决方案

由于我们希望每个数组元素只运行一次昂贵的键函数，我们别无选择，只能使用某种记忆。将键值与每个元素相关联的最简单方法可能是创建一个[key, element]对数组，然后我们可以对其进行排序：

myArr = [{'foo': 5, 'bar': 'hello'}, {'foo': 3, 'bar': 'world'}];
keyFunc = obj => obj.foo;

// compute the key of each array element
keyedArr = myArr.map(obj => [keyFunc(obj), obj]);

// sort the array based on the key
keyedArr.sort((a, b) => a[0] - b[0])

// remove the key values from the array
result = keyedArr.map(pair => pair[1]);
// result: [{'foo': 3, 'bar': 'world'}, {'foo': 5, 'bar': 'hello'}]

请注意，这仅在 key 函数返回数字时才有效。

推荐阅读