Цена
В счастливом краю элегантного кода и красивых радуг живёт гадское чудище по имени Неэффективность.
Программа, обрабатывающая массив, красивее всего представляется в виде последовательности явно разделённых шагов, каждый из которых что-то делает с массивом и возвращает новый массив. Но наслоение всех этих промежуточных массивов стоит дорого.
Точно так же, передача функции в forEach, чтобы та прошлась по массиву за нас, удобна и проста в понимании. Но вызов функций в JavaScript обходится дороже по сравнению с циклами.
Так же обстоят дела со многими техниками, улучшающими читаемость программ. Абстракции добавляют слои между чистой работой компьютера и теми концепциями, с которыми мы работаем – и в результате компьютер делает больше работы. Это не железное правило – есть языки, которые позволяют добавлять абстракции без ухудшения эффективности, и даже в JavaScript опытный программист может найти способы писать абстрактный и быстрый код. Но это проблема встречается часто.
К счастью, большинство компьютеров безумно быстрые. Если ваш набор данных не слишком велик, или время работы должно быть всего лишь достаточно быстрым с точки зрения человека (например, делать что-то каждый раз, когда пользователь жмёт на кнопку) – тогда не имеет значения, написали вы красивое решение, которое работает половину миллисекунды, или очень оптимизированное, которое работает одну десятую миллисекунды.
Удобно примерно подсчитывать, как часто будет вызываться данный кусочек кода. Если у вас есть цикл в цикле (напрямую, или же через вызов в цикле функции, которая внутри также работает с циклом), то код будет выполнен N×M раз, где N – количество повторений внешнего цикла, а M – внутреннего. Если во внутреннем цикле есть ещё один цикл, повторяющийся P раз, тогда мы уже получим N×M×P, и так далее. Это может приводить к большим числам, и когда программа тормозит, проблему часто можно локализовать в небольшом кусочке кода, находящемся внутри самого внутреннего цикла.
Пра-пра-пра-пра-пра-…
Мой дед, Филиберт Хавербеке, упомянут в файле с данными. Начиная с него я могу отследить свой род в поисках самого древнего из предков, Паувелса ван Хавербеке, моего прямого предка. Теперь я хочу подсчитать, какой процент ДНК у меня от него (в теории).
Чтобы пройти от имени предка до объекта, представляющего его, мы строим объект, который сопоставляет имена и людей.
var byName = {};
ancestry.forEach(function(person) {
byName[person.name] = person;
});
console.log(byName["Philibert Haverbeke"]);
// → {name: "Philibert Haverbeke", …}
Задача – не просто найти у каждой из записей отца и посчитать, сколько шагов получается до Паувелса. В истории семьи было несколько браков между двоюродными родственниками (ну, маленькие деревни и т.д.). В связи с этим ветви семейного дерева в некоторых местах соединяются с другими, поэтому генов у меня получается больше, чем 1/2 в степени G (G – количество поколений между Паувелсом и мною). Эта формула исходит из предположения, что каждое поколение расщепляет генетический фонд надвое.
Разумно будет провести аналогию с reduce, где массив низводится до единственного значения путём последовательного комбинирования данных слева направо. Здесь нам тоже надо получить единственное число, но при этом нужно следовать линиям наследственности. А они формируют не простой список, а дерево.
Мы считаем это значение для конкретного человека, комбинируя эти значения его предков. Это можно сделать рекурсивно. Если нам нужен какой-то человек, нам надо подсчитать нужную величину для его родителей, что в свою очередь требует подсчёта её для его прародителей, и т.п. По идее нам придётся обойти бесконечное множество узлов дерева, но так как наш набор данных конечен, нам надо будет где-то остановиться. Мы просто назначим значение по умолчанию для всех людей, которых нет в нашем списке. Логично будет назначить им нулевое значение – люди, которых нет в списке, не несут в себе ДНК нужного нам предка.
Принимая данные о человеке, функцию для комбинирования значений от двух предков и значение по умолчанию, функция reduceAncestors "конденсирует" значение из семейного древа.
function reduceAncestors(person, f, defaultValue) {
function valueFor(person) {
if (person == null)
return defaultValue;
else
return f(person, valueFor(byName[person.mother]),
valueFor(byName[person.father]));
}
return valueFor(person);
}
Внутренняя функция valueFor работает с одним человеком. Благодаря рекурсивной магии она может вызвать себя для обработки отца и матери этого человека. Результаты вместе с объектом person передаются в f, которая и вычисляет нужное значение для этого человека.
Теперь мы можем использовать это для подсчёта процента ДНК, которое мой дедушка разделил с Паувелсом ванн Хавербеке, и поделить это на четыре.
function sharedDNA(person, fromMother, fromFather) {
if (person.name == "Pauwels van Haverbeke")
return 1;
else
return (fromMother + fromFather) / 2;
}
var ph = byName["Philibert Haverbeke"];
console.log(reduceAncestors(ph, sharedDNA, 0) / 4);
// → 0.00049
Человек по имени Паувелс ванн Хавербеке, очевидно, делит 100% ДНК с Паувелсом ванн Хавербеке (полных тёзок в списке данных нет), поэтому для него функция возвращает 1. Все остальные делят средний процент их родителей.
Статистически, у меня примерно 0,05% ДНК совпадает с моим предком из XVI века. Это, конечно, приблизительное число. Это довольно мало, но так как наш генетический материал составляет примерно 3 миллиарда базовых пар, во мне есть что-то от моего предка.
Можно было бы подсчитать это число и без использования reduceAncestors. Но разделение общего подхода (обход древа) и конкретного случая (подсчёт ДНК) позволяет нам писать более понятный код и использовать вновь части кода для других задач. Например, следующий код выясняет процент известных предков данного человека, доживших до 70 лет.
function countAncestors(person, test) {
function combine(person, fromMother, fromFather) {
var thisOneCounts = test(person);
return fromMother + fromFather + (thisOneCounts ? 1 : 0);
}
return reduceAncestors(person, combine, 0);
}
function longLivingPercentage(person) {
var all = countAncestors(person, function(person) {
return true;
});
var longLiving = countAncestors(person, function(person) {
return (person.died - person.born) >= 70;
});
return longLiving / all;
}
console.log(longLivingPercentage(byName["Emile Haverbeke"]));
// → 0.145
Не нужно относиться к таким расчётам слишком серьёзно, так как наш набор содержит произвольную выборку людей. Но код демонстрирует, что reduceAncestors – полезная часть общего словаря для работы со структурой данных типа фамильного древа.
Связывание
Метод bind, который есть у всех функций, создаёт новую функцию, которая вызовет оригинальную, но с некоторыми фиксированными аргументами.
Следующий пример показывает, как это работает. В нём мы определяем функцию isInSet, которая говорит, есть ли имя человека в заданном наборе. Для вызова filter мы можем либо написать выражение с функцией, которое вызывает isInSet, передавая ей набор строк в качестве первого аргумента, или применить функцию isInSet частично.
var theSet = ["Carel Haverbeke", "Maria van Brussel",
"Donald Duck"];
function isInSet(set, person) {
return set.indexOf(person.name) > -1;
}
console.log(ancestry.filter(function(person) {
return isInSet(theSet, person);
}));
// → [{name: "Maria van Brussel", …},
// {name: "Carel Haverbeke", …}]
console.log(ancestry.filter(isInSet.bind(null, theSet)));
// → … тот же результат
Вызов bind возвращает функцию, которая вызовет isInSet с первым аргументом theSet, и последующими аргументами такими же, какие были переданы в bind.
Первый аргумент, который сейчас установлен в null, используется для вызовов методов – так же, как было в apply. Мы поговорим об этом позже.
Итог
Возможность передавать вызов функции другим функциям – не просто игрушка, но очень полезное свойство JavaScript. Мы можем писать выражения "с пробелами" в них, которые затем будут заполнены при помощи значений, возвращаемых функциями.
У массивов есть несколько полезных методов высшего порядка – forEach, чтобы сделать что-то с каждым элементом, filter – чтобы построить новый массив, где некоторые значения отфильтрованы, map – чтобы построить новый массив, каждый элемент которого пропущен через функцию, reduce – для комбинации всех элементов массива в одно значение.
У функций есть метод apply для передачи им аргументов в виде массива. Также у них есть метод bind для создания копии функции с частично заданными аргументами.
Упражнения
Свёртка
Используйте метод reduce в комбинации с concat для свёртки массива массивов в один массив, у которого есть все элементы входных массивов.
var arrays = [[1, 2, 3], [4, 5], [6]];
// Ваш код тут
// → [1, 2, 3, 4, 5, 6]
Разница в возрасте матерей и их детей
Используя набор данных из примера, подсчитайте среднюю разницу в возрасте между матерями и их детьми (это возраст матери во время появления ребёнка). Можно использовать функцию average, приведённую в главе.
Обратите внимание – не все матери, упомянутые в наборе, присутствуют в нём. Здесь может пригодиться объект byName, который упрощает процедуру поиска объекта человека по имени.
function average(array) {
function plus(a, b) { return a + b; }
return array.reduce(plus) / array.length;
}
var byName = {};
ancestry.forEach(function(person) {
byName[person.name] = person;
});
// Ваш код тут
// → 31.2
Историческая ожидаемая продолжительность жизни
Мы считали, что только последнее поколение людей дожило до 90 лет. Давайте рассмотрим этот феномен поподробнее. Подсчитайте средний возраст людей для каждого из столетий. Назначаем столетию людей, беря их год смерти, деля его на 100 и округляя: Math.ceil(person.died / 100).
function average(array) {
function plus(a, b) { return a + b; }
return array.reduce(plus) / array.length;
}
// Тут ваш код
// → 16: 43.5
// 17: 51.2
// 18: 52.8
// 19: 54.8
// 20: 84.7
// 21: 94
В качестве призовой игры напишите функцию groupBy, абстрагирующую операцию группировки. Она должна принимать массив и функцию, которая вычисляет группу для элементов массива, и возвращать объект, который сопоставляет названия групп массивам членов этих групп.
Every и some
У массивов есть ещё стандартные методы every и some. Они принимают как аргумент некую функцию, которая, будучи вызванной с элементом массива в качестве аргумента, возвращает true или false. Так же, как && возвращает true, только если выражения с обеих сторон оператора возвращают true, метод every возвращает true, когда функция возвращает true для всех элементов массива. Соответственно, some возвращает true, когда заданная функция возвращает true при работе хотя бы с одним из элементов массива. Они не обрабатывают больше элементов, чем необходимо – например, если some получает true для первого элемента, он не обрабатывает оставшиеся.
Напишите функции every и some, которые работают так же, как эти методы, только принимают массив в качестве аргумента.
// Ваш код тут
console.log(every([NaN, NaN, NaN], isNaN));
// → true
console.log(every([NaN, NaN, 4], isNaN));
// → false
console.log(some([NaN, 3, 4], isNaN));
// → true
console.log(some([2, 3, 4], isNaN));
// → false
6. Тайная жизнь объектов
Проблема объектно-ориентированных языков в том, что они тащат с собой всё своё неявное окружение. Вам нужен был банан – а вы получаете гориллу с бананом, и целые джунгли впридачу.
Джо Армстронг, в интервью Coders at Work
Термин "объект" в программировании сильно перегружен значениями. В моей профессии объекты – стиль жизни, тема священных войн и любимое заклинание, не теряющее своей магической силы.
Стороннему человеку всё это непонятно. Начнём же с краткой истории объектов как концепции в программировании.
История
Эта история, как большинство историй о программировании, начинается с проблемы сложности. Одна из идей говорит, что сложность можно сделать управляемой, разделив её на небольшие части, изолированные друг от друга. Эти части стали называть объектами.
Объект – твёрдая скорлупа, скрывающая липкую сложность внутри, и вместо неё предлагающая нам несколько ручек настройки и контактов (вроде методов), представляющих интерфейс, посредством которого объект нужно использовать. Идея в том, что интерфейс относительно прост, и при работе с ним позволяет игнорировать все сложные процессы, происходящие внутри объекта.
Простой интерфейс может спрятать много сложного.