Как получить измененное дерево из неизменного дерева, максимизируя повторное использование узлов

У меня есть данные древовидной структуры, как это:

[{
    id: 54,
    name:123,
    children: [{
        id: 54,
        name:123,
        children: [{
            id: 154,
            name:1234,
            children []...
        }]
    }]
}, {
 ...
}]

Я использую Angular 2. Насколько я знаю, обнаружение изменений активируется всякий раз, когда изменяется вход, и ваша стратегия обнаружения изменений onPush,

Чтобы оптимизировать обновления древовидной структуры (например, переключение узла на вложенном уровне или изменение любых атрибутов такого узла), я использовал Immutable.

Как Immutable может помочь мне оптимизировать мои обновления? Я читал, что Immutable повторно использует ссылки из старых данных для создания новых объектов при каждом изменении данных.

Как эффективно использовать неизменяемые структуры данных для обновления узлов на уровне вложенности?

Предположения

  1. У меня нет keyPath для любого из узлов.
  2. Каждый узел имеет уникальный id значение свойства, которое можно использовать для запроса данных дерева (но как?)

Проблемы

  1. Как я могу обновить узел где-нибудь на вложенном уровне? Что может быть наиболее эффективным способом обращения к этому узлу?
  2. Как обновить несколько узлов? Я слышал о withMutations API, но есть ли другой эффективный способ?

Мой подход

  1. Глубоко скопируйте все, а затем измените вновь созданный объект:

    var newState = deepClone(oldState) // deep copy everything and construct a new object 
newState.nodes.forEach(node => {
    if(node.id == 54) {
        node.id = 789;
    }
})

  2. Что я пытаюсь реализовать:

    var newState = Immutable.fromJS(oldState) // create an immutable object 
newState = newState.find(node => {
    node.set("id", 123);
}); // any changes to object will return new object

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

Вид дерева в immutablejs

Источник

1 ответ

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

Более подробно: как только вы используете метод для изменения определенного значения свойства, вы получите новый объект, возвращаемый для этого конкретного узла. Затем, чтобы повторно внедрить этот новый узел в ваше дерево, т. Е. В список дочерних элементов родителя, вы будете использовать метод, который создаст новый список дочерних элементов (поскольку свойство children также является неизменным). Теперь проблема заключается в том, чтобы прикрепить этот дочерний список к родительскому, что приведет к созданию нового родительского узла и т. Д. В конечном итоге вы воссоздаете все узлы-предки узла, который хотите изменить, давая вам новый экземпляр дерева, который будет иметь некоторое повторное использование узлов, которых не было в пути от корня к узлу.

Чтобы повторно использовать ваше изображение, вы получите что-то вроде этого:

Неизменяемый API может сделать это для вас с помощью updateInметод (илиsetInесли ваше обновление касается только одного свойства целевого узла). Вам нужно будет передать ему ключевой путь, чтобы определить (вложенный) узел, который вы хотите изменить.

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

function findKeyPathOf(tree, childrenKey, predicate) {
    var path;
    if (Immutable.List.isList(tree)) {
        tree.some(function (child, i) {
            path = findKeyPathOf(child, childrenKey, predicate);
            if (path) return path.unshift(i); // always returns truthy
        });
        return path;
    } 
    if (predicate(tree)) return [];
    path = findKeyPathOf(tree.get(childrenKey), childrenKey, predicate);
    if (path) return [childrenKey].concat(path);
}

Вы должны передать ему дерево, имя свойства, которое имеет детей (такchildrenв вашем случае), и функция, которая будет определять узел, который вы ищете. Допустим, вы хотите путь к узлу с идентификатором 4, тогда вы бы назвали его так:

var keyPath = findKeyPathOf(tree, 'children', node => node.get('id') == 4);

Этот ключевой путь может выглядеть примерно так: изменение индекса в массиве иchildrenсвойство, обеспечивающее более глубокий массив:

[0, 'children', 0, 'children', 1]

Затем, чтобы изменить узел по этому пути, вы должны сделать что-то вроде этого:

var newTree = tree.updateIn(keyPath, node => node.set('name', 'Hello'));

Вот демонстрация с некоторыми примерами данных:

// Function to get the path to a certain node in the tree
function findKeyPathOf(tree, childrenKey, predicate) {
    var path;
    if (Immutable.List.isList(tree))
        childrenKey = tree.findKey(child =>
            path = findKeyPathOf(child, childrenKey, predicate));
    else if (predicate(tree)) 
        return [];
    else
        path = findKeyPathOf(tree.get(childrenKey), childrenKey, predicate);
    return path && [childrenKey].concat(path);
}

// Function to compare two trees
function differences(tree1, tree2, childrenKey) {
    if (Immutable.List.isList(tree1)) {
        return tree1.reduce(function (diffs, child, i) {
            return diffs.concat(differences(child, tree2.get(i), childrenKey));
        }, []);
    }
    return (tree1 !== tree2 ? [tree1] : []) 
        .concat(differences(tree1.get(childrenKey), tree2.get(childrenKey),
                            childrenKey));
}

// Sample data
var tree = [{
    id: 1,
    name: 'Mike',
    children: [{
        id: 2,
        name: 'Helen',
        children: [{
            id: 3,
            name: 'John',
            children: []
        },{
            id: 4,
            name: 'Sarah',
            children: [{
                id: 5,
                name: 'Joy',
                children: []
            }]
        }]
    }]
}, {
    id: 6,
    name: 'Jack',
    children: [{
        id: 7,
        name: 'Irene',
        children: []
    },{
        id: 8,
        name: 'Peter',
        children: []
    }]
}];

// Create immutable tree from above plain object:
var tree = Immutable.fromJS(tree);

// Use the function to find the node with id == 4:
var keyPath = findKeyPathOf(tree, 'children', node => node.get('id') == 4);

// Found it?
if (keyPath) {
    // Set 'name' to 'Hello' in that node:
    var newTree = tree.updateIn(keyPath, node => node.set('name', 'Hello'));
    // Print the new tree:
    console.log(newTree.toJS());
    // Compare all nodes to see which ones were altered:
    var altered = differences(tree, newTree, 'children').map(x => x.get('id'));
    console.log('IDs of nodes that were replaced: ', altered);
} else {
    console.log('Not found!');
}
.as-console-wrapper { max-height: 100% !important; top: 0; }
<script src="https://cdnjs.cloudflare.com/ajax/libs/immutable/3.8.1/immutable.min.js"></script>

Источник
Другие вопросы по тегам