Это новая серия, которую я решил начать исключительно для собственного удовольствия, чтобы исследовать различные алгоритмические решения проблем, с которыми можно столкнуться при написании кода, используя различные парадигмы (например, функциональные, императивные и т. Д.). Цель состоит в том, чтобы описать проблему, а затем пройтись по различным реализациям. Я не обещаю, что реализации будут всеобъемлющими или что будет охвачена наиболее эффективная реализация. Это просто для развлечения ... если вам нравятся такие вещи!

Примечание. Все эти примеры будут использовать современный JavaScript. Если вам неудобно читать код с использованием современного JavaScript, вы все равно сможете следовать за ним, и я попытался предоставить некоторые эквиваленты. Что касается остальных примеров, вам может потребоваться дополнительное исследование, чтобы понять, что происходит.

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

Вам предоставлен список предметов. Список может содержать массивы, и в этом случае вам нужно рассмотреть все элементы внутри каждого массива, независимо от их глубины (в разумных пределах, конечно). Функция будет вызываться с переменным количеством аргументов и должна возвращать самый большой элемент. Если нет самого большого элемента (например, если дан пустой список), результат должен быть undefined.

На что следует обратить внимание:

  • Список будет вероятно числовым. Но он может содержать строки. Мы определим «наибольший» как соответствующий оператору JavaScript «больше чем» и всему приведению типов, которое подразумевает простоту.
  • Использование Math.max является обманом и в любом случае дает неверные результаты, поскольку не может обрабатывать произвольные строки.

Пример:

Учитывая список 1, 10, [5, 9], [12, [900], [34, 56, 7600]], 34, реализация должна вернуть 7600. Или, учитывая список 'hello', 'world', 'strings', ['are', 'fun'], реализация должна вернуть 'world'.

The Boilerplate

Все функции будут упакованы следующим образом:

function findMax(...args) {
    /* algorithm */
}

Если вы не знакомы с современным JavaScript, это ... может показаться немного странным. Все, что он делает, - это собирает все аргументы, переданные в findMax, и помещает их в массив с именем args.

Императивный способ (без рекурсии)

Сегодня JavaScript часто пишется с использованием функционального стиля, но он также хорошо разбирается в императивном стиле. Итак, начнем с этого - и, надеюсь, вы начнете видеть выразительные преимущества использования функционального стиля.

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

Обычно мы использовали бы рекурсию, но давайте пока не будем включать рекурсию в уравнение. Это означает, что нам придется отслеживать значения, которые нам нужны, чтобы обрабатывать самих себя ... стек звучит примерно правильно. Нам также нужно будет отслеживать самую большую ценность, которую мы нашли на данный момент.

let largest;
const stack = args;
/* algorithm here */
return largest;

Затем нам нужно перебрать стек. Но поскольку это стек, нам не следует использовать обычный for цикл - нет, нам нужно выполнять цикл, пока в стеке еще есть элементы. Лучшим кандидатом для этого является цикл while:

while (stack.length > 0) {
    const candidate = stack.pop();
    /* algorithm here */
}

Как только мы вытащим из стека объект-кандидат, нам нужно решить, что с ним делать. Если это массив, отсутствие рекурсии не является серьезным препятствием - просто поместите элементы внутри массива обратно в стек (это легко сделать с помощью ...):

if (Array.isArray(candidate)) {
    stack.push(...candidate);
}

Знаете ли вы, что Array#push может принимать более одного параметра? Да, он может одновременно помещать в стек несколько элементов. 🎉

Если кандидат не является массивом, нам просто нужно сравнить его с нашим текущим самым большим элементом:

else if (largest === undefined || candidate > largest) {
    largest = candidate;
}

Et voil à! Теперь у нас есть метод, который возвращает самый большой элемент в списке без рекурсии.

Полный код:

function findMax(...args) {
    let largest;
    const stack = args;
    while (stack.length > 0) {
        const candidate = stack.pop();
        if (Array.isArray(candidate)) {
            stack.push(...candidate);
        } else if (largest === undefined || candidate > largest) {
            largest = candidate;
        }    
    }
    return largest;
}

Императивная рекурсия

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

let largest;
/* algorithm here */
return largest;

Поскольку мы собираемся использовать рекурсию, мы можем безопасно перебирать каждый элемент в списке с помощью цикла for...of (цикл for, конечно, тоже подойдет):

for (let candidate of args) {
    /* algorithm here */
}

Внутри цикла for...of нам нужно решить, что делать с элементом-кандидатом. Если это массив, нам нужно определить самый большой элемент внутри массива ... эй, звучит знакомо? Мы уже делаем это! Итак…

if (Array.isArray(candidate)) {
    candidate = findMax(...candidate);
}

Если вы не знакомы с рекурсией, приведенное выше снова вызывает нашу findMax функцию, только с элементами в массиве кандидатов, а не с исходными аргументами. Если обнаруживается, что другой кандидат является массивом, он снова вызовет findMax и так далее, пока не будет обнаружено что-то, что не является массивом. Это должно звучать очень похоже на стек, который мы использовали в предыдущем разделе.

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

if (largest === undefined || candidate > largest) {
    largest = candidate;
}

При этом мы сравним кандидата с наибольшим известным значением, независимо от того, является ли он массивом или нет.

Полный код:

function findMax(...args) {
    let largest;
    for (let candidate of args) {
        if (Array.isArray(candidate)) {
            candidate = findMax(...candidate);
        }
        if (largest === undefined || candidate > largest) {
            largest = candidate;
        }
    }
    return largest;
}

Использование функционального стиля

До сих пор мы использовали императивное программирование. Давайте переключимся и займемся чем-нибудь функциональным.

Во-первых, нам понадобится функция, которая может сгладить список, чтобы в нем не было массивов. Вместо этого элементы внутри любых массивов распределяются по самому списку.

Это не так уж сложно:

function flatten(...args) {
    return args.reduce((acc, item) => [
        ...acc, ...(Array.isArray(item) ? flatten(...item) 
                                        : [item])
    ], []);
}

Ой, подожди, кого я шучу? 😱 Если вы не знакомы с синтаксисом или Array#reduce, это похоже на кошмар. Итак, добавим несколько комментариев:

function flatten(...args) {
    return args.reduce(
        /* acc is short for "accumulator" here */
        (acc, item) => [
            ...acc, // spread the accumulator out
            /* we'll spread the item out into multiple arguments */
            ...(Array.isArray(item)
                /* If the item is an array...
                 * we need to use recursion, so spread the array out
                 * and call ourselves again. */
                ? flatten(...item)
                /* Otherwise, return array containing a single item
                 * so that spread can still work */
                : [item])
        ],
        /* Make the starting point for Array#reduce an array with no
         * items. This will be returned if there is nothing to 
         * flatten, but also serves as the initial value to `acc` 
         * above (the accumulator) */
        []
    );
}

Честно говоря, я не уверен, что с комментариями так лучше ... Может быть, подсветка синтаксиса поможет:

Ну что ж ... когда вы привыкнете к функциональному программированию, в этом появится большой смысл ... поверьте мне ... 🐍 ... (Да ладно ... Книга джунглей Диснея! первая … Я единственный, кому это кажется немного смешным…?)

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

const largest = (a, b) => (
    [a = b, b = a] = [a, b],
    a > b ? a : b
);
return flatten(args).reduce(largest, undefined);

Подождите… что? Как в мире это это работает? 😲 Пора больше комментариев!

const largest = (a, b) => (
    // This is "array destructuring"; it lets us extract
    // values out of arrays based on their position.
    // here, we are extracting `a` and `b` from the RHS
    // (right hand side), and then assigning those
    // to the variables in the LHS.
    // But what about those "=" assignments? Those are
    // the defaults that get assigned if the destructured
    // item happens to be undefined. So, if `a` is undefined,
    // `a` will be given the value of `b` (and vice versa).
    // In terms of comparing largest, that's OK, since if both
    // `a` and `b` are equal, it doesn't matter which we
    // return as the largest, but ultimately this lets us
    // ensure we aren't comparing undefined to anything other
    // than undefined.
    [a = b, b = a] = [a, b],
    
    // and now that we have two values, we can safely compare
    // them and get a useful result.
    // note: comma returns the last expression evaluated,
    // but evaluates all the expressions in the list.
    a > b ? a : b
);
// So how does the above work with Array#reduce?
// The first parameter to the reduce callback (`a` above)
// is still technically acting as an accumulator, only
// it's not accumulating an array of items -- it's just
// holding the largest value we've encountered thus far.
return flatten(args).reduce(largest, undefined);

Ладно ... неужели я наполовину слишком умен? Это работает точно так же:

const largest = (a, b) => 
    (a === undefined) ? b
     : (b === undefined) ? a 
     : (a > b) ? a 
     : b;
return flatten(args).reduce(largest, undefined);

😠 Черт возьми ... Я фанат стрелочных функций и тернарных операторов. Попробуем еще раз:

function largest(a, b) {
    if (a === undefined) return b;
    if (b === undefined) return a;
    if (a > b) return a;
    return b;
}
return flatten(args).reduce(largest, undefined);

Примечание. Я не собираюсь снова перечислять все фрагменты кода - вы только что все это видели!

Функциональная сортировка

Когда вы думаете о чем-либо самом большом, на ум сразу приходит сортировка. В конце концов, легко придумать, как выровнять список, отсортировать его по возрастанию и затем вернуть последний элемент в списке. Это всегда будет наибольшее значение. (Или сделайте обратное: отсортируйте его в порядке убывания и верните первый элемент.)

Но сначала оговорка: сортировка массивов в JavaScript не чиста; они видоизменяют исходный массив. То есть:

const arr = [3, 2, 1];
arr.sort();
console.log(arr); // [1, 2, 3]

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

Итак, сначала мы определяем функцию сортировки - здесь мы будем использовать только возрастающий порядок:

const ascendingOrder = (a, b) => a < b ? -1 : a > b ? 1 : 0;

Итак, я снова перехожу к стрелочным функциям и тернарным операторам. 💥

Тем не менее, приведенная выше конструкция является довольно типичной конструкцией, когда дело доходит до сортировки, но на тот случай, если ваши глаза захотят вылезти из своих сокетов, глядя на это (при условии, что они еще этого не сделали), вот эквивалент без каких-либо функций массива или тернарные операторы:

function ascendingOrder(a, b) {
    if (a < b) return -1;
    if (a > b) return 1;
    return 0;
}

Затем нам нужно сгладить входящие аргументы:

return flatten(args)

затем отсортируйте их (обратите внимание, это технически изменяет предыдущий результат, но это результат царапины, поэтому это не проблема):

.sort(ascendingOrder)

… А затем получить последнее значение в массиве:

.pop();

Ух!

Вау ... это было много, не так ли? Но теперь у нас есть несколько реализаций, которые решают проблему с использованием разных стилей программирования и алгоритмов, каждая из которых имеет разный уровень производительности и использования памяти. Можете ли вы выбрать, какие реализации имеют лучшую производительность? Какой из них ты предпочитаешь читать? Какой из них ты предпочитаешь писать? Вы можете придумать другие способы решения проблемы?

Ни один стиль или алгоритм не всегда верны. Ремонтопригодность и удобочитаемость не менее важны (если не больше), чем умный код. Производительность может быть даже более важной, если вы имеете дело с большими списками или вам нужно выполнять алгоритм много раз подряд. С другой стороны, если вы работаете в среде с ограниченным объемом памяти, вам нужно решение, которое работает с наименьшими накладными расходами на память. В конечном итоге вам нужно выбрать стиль и алгоритм, которые подходят для ваших конкретных нужд.

Да, и если вы хотите поиграть с различными реализациями или создать свою собственную, загляните на соответствующую площадку. Если вам нужно испытательное снаряжение, в котором можно поиграть, Я сделал его специально для вас!