Я пытался оптимизировать это:
const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];
const getMode = (arr) => arr
.sort(
(a, b) =>
arr.reduce((acu, cur) => (cur === a ? (acu += 1) : cur)) -
arr.reduce((acu, cur) => (cur === b ? (acu += 1) : cur))
)
.pop();
console.log(getMode(NUMBERS));Я тоже думал об этом:
const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];
const mode = (arr) => arr
.sort(
(a, b) =>
arr.filter((v) => v === a).length - arr.filter((v) => v === b).length
)
.pop();
console.log(mode(NUMBERS))Как вы думаете, что можно улучшить?
3 ответа
Чтобы повысить производительность, вы можете уменьшить сложность кода.
В настоящее время сложность ваших подходов O (n² log (n)) как sort функция O (п журнал (п)) и на каждой итерации вы используете filter или же reduce который имеет сложность На).
Я могу предложить один подход, при котором вам не нужно сортировать элементы, поэтому сложность метода будет На) при использовании V8 Движок JavaScript (для дополнительной информации) иначе O (п журнал (п)). Оцените этот подход:
const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];
const getMode = (arr) => {
let [maxFreq, result] = [-1, -1];
arr.reduce((acu, cur) => {
acu.set(cur, (acu.has(cur) ? acu.get(cur) : 0)+1)
return acu;
}, new Map())
.forEach((value, key) => {
if(value > maxFreq){
maxFreq = value;
result = key;
}
});
return result;
}
console.log(getMode(NUMBERS))Я изменил ответ HandsomeCoder.
На самом деле это O (n), потому что доступ к объекту — O (1)
const NUMBERS = [2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9];
function getMode(array) {
function buildFrequencyMap(array) {
return array.reduce((acu, number) => {
acu[number] = acu[number] !== undefined ? acu[number] + 1 : 0
return acu;
}, {})
}
function maxFrequency(frequencyMap) {
let maxFreq = -1, result = -1
Object.entries(frequencyMap).forEach(([key, value]) => {
if(value > maxFreq){
maxFreq = value;
result = key;
}
});
return result
}
const frequencyMap = buildFrequencyMap(array)
return maxFrequency(frequencyMap);
}
console.log(getMode(NUMBERS))Сортировать!
Никогда не используйте сортировку для получения максимума или минимума. Сортировка используется только для упорядочивания всех элементов в массиве.
Если вам нужен максимум в массиве, вы можете использовать Math.max(...[1,2,3,4,5,6,5,4,3,2]) выражает 6.
Если вам нужно связанное значение, связанное с максимальным или минимальным значением, вам потребуется выполнить итерацию вручную, сохраняя максимальное значение и связанные данные по мере нахождения новых значений.
Переписать
В этом примере проверяется количество значений по сравнению с макс. max и сохраните максимальное количество и значение maxVal подсчитанной стоимости
Для подсчета значений он использует карту, которая использует хеш-карту и $ O (1) $ для поиска, который сделает функцию $ O (п) $
function getMode(data) {
var max = -Infinity, maxVal, counts = new Map(), c;
for (const v of data) {
c = ++(counts.get(v) ?? (counts.set(v, c = {count: 0}), c)).count;
[max, maxVal] = c > max ? [c, v] : [max, maxVal];
}
return maxVal;
}
console.log(getMode([2, 2, 2, 2, 2, 4, 5, 5, 5, 5, 5, 5, 5, 5, 9]))Вы также можете проверить, больше ли max, чем (n / 2), и выйти, как если бы счетчик больше половины элементов, значение должно быть наиболее частым.
Да … @PavloSlavynskyy … спасибо, что поправили!
— HandsomeCoder
@PavloSlavynskyy согласно этому (stackoverflow.com/questions/33611509/…) в V8 JavaScript Engine временная сложность поиска и поиска равна O (1)
— HandsomeCoder