Марейн Хавербеке - Выразительный JavaScript

Мой дед, Филиберт Хавербеке, упомянут в файле с данными. Начиная с него я могу отследить свой род в поисках самого древнего из предков, Паувелса ван Хавербеке, моего прямого предка. Теперь я хочу подсчитать, какой процент ДНК у меня от него (в теории).

Чтобы пройти от имени предка до объекта, представляющего его, мы строим объект, который сопоставляет имена и людей.

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– полезная часть общего словаря для работы со структурой данных типа фамильного древа.