Как я могу эффективно отсортировать массив на основе вычислительно дорогой ключевой функции?

Question

Я задал этот вопрос о сортировке массива с помощью ключевой функции, где оказалось, что нет способа избежать использования функции сравнения.

Проблема в том, что

1. У меня есть вычислительно дорогая функция key , которую я каким-то образом должен превратить в сравнение функцию
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'}]

УчитываяВ этих обстоятельствах, как я могу эффективно отсортировать мой массив?

Answer 1

Поскольку мы хотим запускать дорогостоящую ключевую функцию только один раз для каждого элемента массива, у нас нет другого выбора, кроме как использовать какой-то вид памятки.Самый простой способ связать значение ключа с каждым элементом - это, вероятно, создать массив из [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'}]

Обратите внимание, что это работает, только если функция ключа возвращает число.