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

- Кого волнует, как работает Array.sort (), если он выполняет свою работу и делает это достаточно быстро, верно?

Так что я пришел с таким настроем на Facebook Hacker Cup, желая выиграть футболку в прошлом году, и проиграл в первом раунде, был разочарован, начал думать, как мне стать лучше, и начал медленно погружаться в мир алгоритмов.

Короче говоря, давайте рассмотрим простой пример:

У нас есть массив целых чисел, и задача найти в нем все неуникальные элементы.

Наивное решение

Подумайте на секунду, как бы вы это сделали, и позвольте мне показать свое первое рабочее решение:

var length = data.length;
var unique = [];
var distinct = [];
for (var i = 0; i < length; i++) {
    var elem = data[i];
    var uniqueInd = unique.indexOf(elem);
    if (uniqueInd > -1) {
        unique.splice(uniqueInd, 1);
    }
    if (distinct.indexOf(elem) === -1) {
        distinct.push(elem);
        unique.push(elem);
    }
}
for (var i = length - 1; i > -1; i--) {
    if (unique.indexOf(data[i]) > -1) {
        data.splice(i, 1);
    }
}
return data;

Когда я писал этот код, я не знал никаких функциональных методов Javascript, таких как map или reduce, поэтому он выглядел длинным. Но это сработало, и я очень гордился собой. Я потратил на это меньше суток.

Я разместил его на https://js.checkio.org/mission/non-unique-elements/, чтобы сравнить с другими решениями.

Хорошее решение

Как только вы отправите туда свой собственный код, вы сможете узнать, как к нему подошли другие ребята.

И эта красавица была на первом месте в списке:

return data.filter(function(a){
    return data.indexOf(a) !== data.lastIndexOf(a)
});

Он короткий и читаемый. Идея блестящая - если первое и последнее вхождение элемента одинаковы, то этот элемент встречается только один раз, поэтому он уникален.

Просто посмотрите на это и сравните с тем, что у меня было. Вы видите эту пропасть?

Я был так впечатлен, что начал проводить другие викторины по соревновательному программированию, которые в какой-то момент привели меня к большой нотации О.

Быстрое решение

Чтобы быстро понять, почему большой O имеет смысл, взгляните на эту диаграмму, взятую из книги Стивена Скиены:

Представьте, что наш алгоритм имеет сложность n квадратов. Это будет означать, что для обработки массива из 1 миллиона чисел потребуется ~ 16,7 мин. Не слишком ли много? Я бы сказал, это с учетом того, что на Facebook Hacker Cup у вас есть только 5 минут, чтобы загрузить результаты, как только вы получите входные данные.

И остается ли наше хорошее решение таким же привлекательным, если посмотреть на него с точки зрения сложности алгоритма? То же, что и мое первое решение, к сожалению, нет. Покажем почему:

indexOf и lastIndexOf в худшем случае выполняют n операций (скажем, у нас есть массив всех уникальных чисел), потому что они в основном перебирают все данные. И мы выполняем их внутри метода filter, который представляет собой цикл из n, поэтому это означает, что мы выполняем n операций n раз, что составляет O (n * n). Ой. Это недопустимо медленно.

Один из способов исправить это - использовать сортировку. Основы науки об алгоритмах говорят нам, что мы можем выполнять сортировку со сложностью O (n * log (n)), то есть, если вы проверяете таблицу выше намного быстрее, чем O (n * n), и занимает разумное время даже для 1 миллиарда записей.

После того, как мы отсортируем список, мы можем использовать другой базовый алгоритм алгоритмов, переопределив методыindexOf и lastIndexOf двоичным поиском. Идея бинарного поиска заключается в том, что на каждом шаге мы разделяем доступный для поиска массив на 2 части и продолжаем поиск только в одной из них. Мы просто проверяем, больше ли число в середине массива или меньше того, которое мы искали, а затем выбираем левую или правую часть данных соответственно, зная, что они отсортированы. Пока у нас не будет массива только из одного элемента, который либо является элементом, который мы ищем, либо нет, и это будет означать, что нашего элемента нет в массиве вообще. Итак, чтобы завершить это, нам нужно x шагов, где 2 в степени x равно n (потому что на каждой итерации мы делим количество наших данных на 2), что дает нам сложность O (log (n)) для поиска как indexOf, так и lastIndexOf. И поскольку O (log (n)) + O (log (n)) = O (log (n)), мы получили сложность O (log (n)) для вызова методов indexOf и lastIndexOf.

Наконец, у нас есть цикл из n (потому что мы перебираем весь массив с filter) со сложностью O (log (n)) внутри каждой итерации, и это дает нам общую сложность O (n * log (n)).

Это то же самое, что и сложность сортировки, поэтому в итоге мы имеем O (n * log (n)) + O (n * log (n)) = O (n * log (n)) для всего алгоритма. Прохладный! Это намного быстрее.

Теперь мы можем обработать даже 1 миллиард записей менее чем за минуту.

И вот как мы можем сделать indexOf со сложностью O (n * log (n)) для отсортированного массива:

function newIndexOf(array, elem, startIndex, endIndex) {
    if (array.length === 1) {
        if (array[1] === elem) {
            return startIndex;
        } else {
            return -1;
        }
    }
  
    var median = Math.floor(array.length / 2);
  
    if (elem <= array[median]) {
        return newIndexOf(array, elem, startIndex, median);
    } else {
        return newIndexOf(array, elem, median + 1, endIndex);
    }
}

lastIndexOf реализация будет такой же, но вместо условия ≤ мы будем использовать условие ‹.

Еще более быстрое решение

Но говорить о веб-сервере с высокой нагрузкой даже ~ 30 секунд - это уже слишком. Можем ли мы сделать это лучше?

Каждый раз, когда я думаю о расширенных утилитах для работы с массивами, я думаю о lodash.js библиотеке. И вот как они предлагают это сделать:

_.transform(_.countBy(array), function(result, count, value) {
    if (count > 1) result.push(value);
}, []);

Во-первых, мы используем метод countBy для вычисления появления каждого элемента. Он дает нам объект JS, в котором элементы являются ключами, а их вхождения - значениями. countBy использует метод JS reduce внутри и занимает O (n) временную сложность, потому что он в основном выполняет итерацию по всему массиву один раз.

Затем с помощью transform мы просматриваем все ключи, которые есть в объекте, и берем те из них, которые имеют значения (вхождения) больше 1, что снова дает нам временную сложность O (n), потому что у нас не может быть более n ключей в этом объекте.

И поскольку O (n) + O (n) = O (n), в конечном результате мы получаем сложность O (n). А если вы посмотрите таблицу выше, то увидите, что теперь мы можем обрабатывать 1 миллиард записей в 30 раз быстрее. Ух ты!

Заключение

Каким-то образом мой краткий анализ подтверждает, что фреймворки и служебные библиотеки, такие как lodash.js, обычно заботятся о временной сложности алгоритмов, и в этом смысле мы можем им доверять.

В то же время легко попасть в ловушку красивого умного кода, который в конечном итоге значительно снизит производительность нашего приложения.

Таким образом, даже если мы не можем сами создавать сложные алгоритмы, хорошо знать, как рассчитать сложность данного алгоритма, потому что тогда мы можем быть уверены, что не получим сюрпризов, когда в какой-то момент мы решим масштабировать наше приложение для больших объемов. .

Если вам действительно интересно, я настоятельно рекомендую классы и книгу Стивена Скиены для обучения, а также платформы https://js.checkio.org/ и https://www.codewars.com/, чтобы получить некоторые упражняться. А может быть, увидимся на следующих соревнованиях по программированию? ;)