Попытка решения алгоритмической задачки снова завершилась в «Википедии»...
На просторах Codewars можно найти задачу, которая звучит примерно так:
Дан массив чисел длиной n. Известно, что одно число встречается в нём более, чем n/2 раз. Найти это число.
Например, arr = [1, 0, 5, 1, 5, 5, 5], ответ 5.
В такой постановке задача выглядит очень простой — её можно решить в лоб и достаточно эффективно. Поэтому автор добавляет тесты на производительность, в которых:
100 тесткейсов с длиной массива 1_000_001, ограничение времени на тесткейс 15ms.
Внимание — дальше будут спойлеры! Поэтому, сперва можете попытаться решить исходную задачу
Вариант №1. Словарь.
Чтобы было от чего отталкиваться — сперва решим задачу как раз таки «в лоб», первым пришедшим в голову способом — используя подсчет при помощи словаря/ассоциативного массива. Так мы можем решить задачу за O(n):
function mostAppear(arr){
const limit = Math.ceil(arr.length / 2);
const d = new Map();
for (const item of arr) {
const itemCount = d.has(item) ? d.get(item) + 1 : 1;
if (itemCount >= limit) return item;
d.set(item, itemCount);
};
};
Прогоняем тесты — среднее время около 80-90ms, т.е. в 6 раз медленнее нужного! Можно конечно заменить цикл for of на обычный for и это даст несколько миллисекунд, но всё равно не поможет :)
Кстати, если воспользоваться случаем и, эксперимента ради, вместо Map использовать Object, то данный код станет в полтора раза медленней — 120-140ms. Поэтому, там где нужен ассоциативный массив, лучше использовать Map — несмотря на то, что и то и то внутри реализовано хэш-таблицей. Семантика, наличие нужных методов, сохранение типа ключа (а Object приводит всё к строке), ну и в конце концов — лучшая производительность.
Вариант №2. Типизированный массив.
Итак, код работает, но недостаточно быстро. Можно ли ещё как-то его ускорить, не меняя алгоритм? По условию конкретно этой задачи — у нас в исходном массиве находятся целые числа, а значит можно, пожертвовав памятью, выделить дополнительный массив и использовать его как ассоциативный, где ключом будет индекс. Так мы избавляемся от хэш-функции и обращаемся сразу в нужную ячейку памяти.
Ну... гхм... избавились бы, если бы не тот факт, что стандартные массивы в JS — это, по сути, те же самые объекты. Конечно, с оптимизациями для однотипных упорядоченных данных, но тем не менее. Поэтому простая замена словаря на массив даст нам всё те же ~80ms.
Зато у нас есть типизированные массивы! А они предоставляют доступ к сырым двоичным данным. А ещё интересны тем, что разделены на буферы и представления, что позволяет довольно гибко хранить свои данные. Но нам нужен самый простой и обычный вариант:
function mostAppear(arr){
const limit = Math.ceil(arr.length / 2);
const d = new Uint32Array(1000001);
for (const item of arr) {
const itemCount = d[item] += 1;
if (itemCount >= limit) return item;
};
};
Код работает довольно быстро — 19-25ms — почти 4-кратное ускорение! Но на этом этапе у меня закончились идеи для оптимизации изначально неправильного решения :D
Вариант №3. Правильный :)
Пора бы подумать, зачем в условии этой задачи написано про n/2 раз! Википедия подсказывает, что в 1981 году Р. Бойер и Дж. Мур опубликовали алгоритм нахождения преобладающего элемента последовательности — алгоритм большинства голосов Бойера–Мура или Boyer–Moore majority vote algorithm. Очень простой и элегантный алгоритм, сложность которого O(n), а используемая память всего лишь O(1)!
Принимаем один из элементов за кандидата и считаем голоса — если следующий элемент такой же, то +1 голос, если другой, то -1 голос. Как только голосов стало 0 и меньше, значит берём другого кандидата. Получается, что элемент-кандидат, который встречается чаще, чем в половине случаев — наберёт столько голосов, что другие не смогут отнять. Плюс небольшая микро-оптимизация, досрочно завершающая цикл.
function mostAppear(arr){
const limit = Math.ceil(arr.length / 2);
let vote = 0;
let candidate = arr[0];
for (const item of arr) {
if (item === candidate) {
vote += 1;
} else {
vote -= 1;
}
if (vote <= 0) {
vote = 1;
candidate = item;
}
if (vote >= limit) break;
}
return candidate;
};
Время выполнения — 8-9ms, задача решена!
Забавно, что все три варианта решают задачу за один проход по исходному массиву, но производительность на больших задачах отличается на порядок. Тем не менее, если отбросить погоню за миллисекундами, то первый вариант уже вполне достаточен и более универсален. Но зачтут ли его на алгоритмическом интервью? Лично я сомневаюсь :)
