К счастью, большинство компьютеров безумно быстрые. Если ваш набор данных не слишком велик, или время работы должно быть всего лишь достаточно быстрым с точки зрения человека (например, делать что-то каждый раз, когда пользователь жмёт на кнопку) – тогда не имеет значения, написали вы красивое решение, которое работает половину миллисекунды, или очень оптимизированное, которое работает одну десятую миллисекунды.
Удобно примерно подсчитывать, как часто будет вызываться данный кусочек кода. Если у вас есть цикл в цикле (напрямую, или же через вызов в цикле функции, которая внутри также работает с циклом), то код будет выполнен 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 миллиарда базовых пар, во мне есть что-то от моего предка.