performance - Implementación eficiente del árbol en MATLAB

data-structures tree

Question

Clase de arbol en MATLAB

Estoy implementando una estructura de datos de árbol en MATLAB. Agregar nuevos nodos secundarios al árbol, asignar y actualizar valores de datos relacionados con los nodos son operaciones típicas que espero ejecutar. Cada nodo tiene el mismo tipo de data asociados a él. Eliminar nodos no es necesario para mi. Hasta ahora, he decidido sobre una implementación de clase heredada de la clase de handle para poder pasar referencias a nodos alrededor de funciones que modificarán el árbol.

Edición: 2 de diciembre

En primer lugar, gracias por todas las sugerencias en los comentarios y respuestas hasta el momento. Ya me han ayudado a mejorar mi clase de árbol.

Alguien sugirió probar el digraph introducido en R2015b. Todavía tengo que explorar esto, pero dado que no funciona como un parámetro de referencia similar a una clase heredada de un handle , soy un poco escéptico sobre cómo funcionará en mi aplicación. Tampoco me queda claro en este punto qué tan fácil será trabajar con él utilizando data personalizados para nodos y bordes.

Edición: (3 de diciembre) Más información sobre la aplicación principal: MCTS

Inicialmente, asumí que los detalles de la aplicación principal solo tendrían un interés marginal, pero luego de leer los comentarios y la answer de @FirefoxMetzger, me doy cuenta de que tiene implicaciones importantes.

Estoy implementando un tipo de algoritmo de búsqueda de árbol de Monte Carlo . Un árbol de búsqueda se explora y se expande de manera iterativa. Wikipedia ofrece una buena descripción gráfica del proceso:

En mi aplicación realizo un gran número de iteraciones de búsqueda. En cada iteración de búsqueda, atravieso el árbol actual desde la raíz hasta un nodo de hoja, luego amplío el árbol agregando nuevos nodos y repito. Como el método se basa en un muestreo aleatorio, al comienzo de cada iteración no sé en qué nodo de hoja terminaré en cada iteración . En su lugar, esto se determina conjuntamente por los data de los nodos que se encuentran actualmente en el árbol y los resultados de las muestras aleatorias. Todos los nodos que visito durante una única iteración tienen sus data actualizados.

Ejemplo: Estoy en el nodo n que tiene algunos hijos. Necesito acceder a los datos de cada uno de los niños y extraer una muestra aleatoria que determine a cuál de los niños pasaré a continuación en la búsqueda. Esto se repite hasta que se alcanza un nodo de hoja. En la práctica, estoy haciendo esto llamando a una función de search en la raíz que decidirá qué hijo expandir a continuación, recurrir a la search en ese nodo de forma recursiva, y así sucesivamente, finalmente devolver un valor una vez que se alcanza un nodo de hoja. Este valor se utiliza al regresar de las funciones recursivas para actualizar los data de los nodos visitados durante la iteración de búsqueda.

El árbol puede estar bastante desequilibrado, de modo que algunas ramas son cadenas muy largas de nodos, mientras que otras terminan rápidamente después del nivel raíz y no se expanden más.

Implementación actual

A continuación se muestra un ejemplo de mi implementación actual, con un ejemplo de algunas de las funciones miembro para agregar nodos, consultar la profundidad o el número de nodos en el árbol, etc.

classdef stree < handle
    %   A class for a tree object that acts like a reference
    %   parameter.
    %   The tree can be traversed in both directions by using the parent
    %   and children information.
    %   New nodes can be added to the tree. The object will automatically
    %   keep track of the number of nodes in the tree and increment the
    %   storage space as necessary.

    properties (SetAccess = private)
        % Hold the data at each node
        Node = { [] };
        % Index of the parent node. The root of the tree as a parent index
        % equal to 0.
        Parent = 0;
        num_nodes = 0;
        size_increment = 1;
        maxSize = 1;
    end

    methods
        function [obj, root_ID] = stree(data, init_siz)
            % New object with only root content, with specified initial
            % size
            obj.Node = repmat({ data },init_siz,1);
            obj.Parent = zeros(init_siz,1);
            root_ID = 1;
            obj.num_nodes = 1;
            obj.size_increment = init_siz;
            obj.maxSize = numel(obj.Parent);
        end

        function ID = addnode(obj, parent, data)
            % Add child node to specified parent
            if obj.num_nodes < obj.maxSize
                % still have room for data
                idx = obj.num_nodes + 1;
                obj.Node{idx} = data;
                obj.Parent(idx) = parent;
                obj.num_nodes = idx;
            else
                % all preallocated elements are in use, reserve more memory
                obj.Node = [
                    obj.Node
                    repmat({data},obj.size_increment,1)
                    ];

                obj.Parent = [
                    obj.Parent
                    parent
                    zeros(obj.size_increment-1,1)];
                obj.num_nodes = obj.num_nodes + 1;

                obj.maxSize = numel(obj.Parent);

            end
            ID = obj.num_nodes;
        end

        function content = get(obj, ID)
            %% GET  Return the contents of the given node IDs.
            content = [obj.Node{ID}];
        end

        function obj = set(obj, ID, content)
            %% SET  Set the content of given node ID and return the modifed tree.
            obj.Node{ID} = content;
        end

        function IDs = getchildren(obj, ID)
            % GETCHILDREN  Return the list of ID of the children of the given node ID.
            % The list is returned as a line vector.
            IDs = find( obj.Parent(1:obj.num_nodes) == ID );
            IDs = IDs'';
        end
        function n = nnodes(obj)
            % NNODES  Return the number of nodes in the tree.
            % Equal to root + those whose parent is not root.
            n = 1 + sum(obj.Parent(1:obj.num_nodes) ~= 0);
            assert( obj.num_nodes == n);
        end

        function flag = isleaf(obj, ID)
            % ISLEAF  Return true if given ID matches a leaf node.
            % A leaf node is a node that has no children.
            flag = ~any( obj.Parent(1:obj.num_nodes) == ID );
        end

        function depth = depth(obj,ID)
            % DEPTH return depth of tree under ID. If ID is not given, use
            % root.
            if nargin == 1
                ID = 0;
            end
            if obj.isleaf(ID)
                depth = 0;
            else
                children = obj.getchildren(ID);
                NC = numel(children);
                d = 0; % Depth from here on out
                for k = 1:NC
                    d = max(d, obj.depth(children(k)));
                end
                depth = 1 + d;
            end
        end
    end
end

Sin embargo, el rendimiento a veces es lento, y las operaciones en el árbol ocupan la mayor parte del tiempo de cómputo. ¿Qué formas específicas habría para hacer la implementación más eficiente? Incluso sería posible cambiar la implementación a algo más que el tipo de herencia de handle si hay mejoras de rendimiento.

Perfilando los resultados con la implementación actual.

Como agregar nuevos nodos al árbol es la operación más típica (junto con la actualización de los data de un nodo), realicé algunos profiling al respecto. Ejecuté el perfilador en el siguiente código de evaluación comparativa con Nd=6, Ns=10 .

function T = benchmark(Nd, Ns)
% Tree benchmark. Nd: tree depth, Ns: number of nodes per layer
% Initialize tree
T = stree(rand, 10000);
add_layers(1, Nd);
    function add_layers(node_id, num_layers)
        if num_layers == 0
            return;
        end
        child_id = zeros(Ns,1);
        for s = 1:Ns
            % add child to current node
            child_id(s) = T.addnode(node_id, rand);

            % recursively increase depth under child_id(s)
            add_layers(child_id(s), num_layers-1);
        end
    end
end

Resultados del perfilador:

Rendimiento R2015b

Se ha descubierto que R2015b mejora el rendimiento de las funciones OOP de MATLAB . Rediseñé el punto de referencia anterior y de hecho observé una mejora en el rendimiento:

Así que ya son buenas noticias, aunque, por supuesto, se aceptan otras mejoras;)

Reservando la memoria de manera diferente

También se sugirió en los comentarios a utilizar.

obj.Node = [obj.Node; data; cell(obj.size_increment - 1,1)];

para reservar más memoria en lugar del enfoque actual con repmat . Esto mejoró ligeramente el rendimiento. Debo tener en cuenta que mi código de referencia es para datos ficticios, y dado que los data reales son más complicados, es probable que esto ayude. ¡Gracias! Resultados del perfilador a continuación:

Preguntas sobre un rendimiento aún mayor

1. ¿Quizás hay una forma alternativa de mantener la memoria para el árbol que es más eficiente? Lamentablemente, normalmente no sé de antemano cuántos nodos habrá en el árbol.
2. Agregar los nodos nuevos y modificar los data de los nodos existentes son las operaciones más típicas que hago en el árbol. A partir de ahora, en realidad ocupan la mayor parte del tiempo de procesamiento de mi aplicación principal. Cualquier mejora en estas funciones sería muy bienvenida.

Solo como nota final, idealmente me gustaría mantener la implementación como MATLAB puro. Sin embargo, opciones como MEX o el uso de algunas de las funcionalidades integradas de Java pueden ser aceptables.

Answer 1

Puede intentar asignar una cantidad de elementos que sea proporcional a la cantidad de elementos que realmente ha llenado: esta es la implementación estándar para std :: vector en c ++

obj.Node = [obj.Node; data; cell(q * obj.num_nodes,1)];

No recuerdo exactamente pero en MSCC q es 1 mientras que es .75 para GCC.

Esta es una solución que utiliza Java. No me gusta mucho, pero hace su trabajo. Implementé el ejemplo que extrajiste de wikipedia.

import javax.swing.tree.DefaultMutableTreeNode

% Let''s create our example tree
top = DefaultMutableTreeNode([11,21])
n1 = DefaultMutableTreeNode([7,10])
top.add(n1)
n2 = DefaultMutableTreeNode([2,4])
n1.add(n2)
n2 = DefaultMutableTreeNode([5,6])
n1.add(n2)
n3 = DefaultMutableTreeNode([2,3])
n2.add(n3)
n3 = DefaultMutableTreeNode([3,3])
n2.add(n3)
n1 = DefaultMutableTreeNode([4,8])
top.add(n1)
n2 = DefaultMutableTreeNode([1,2])
n1.add(n2)
n2 = DefaultMutableTreeNode([2,3])
n1.add(n2)
n2 = DefaultMutableTreeNode([2,3])
n1.add(n2)
n1 = DefaultMutableTreeNode([0,3])
top.add(n1)

% Element to look for, your implementation will be recursive
searching = [0 1 1];
idx = 1;
node(idx) = top;
for item = searching,
    % Java transposes the matrices, remember to transpose back when you are reading
    node(idx).getUserObject()''
    node(idx+1) = node(idx).getChildAt(item);
    idx = idx + 1;
end
node(idx).getUserObject()''

% We made a new test...
newdata = [0, 1]
newnode = DefaultMutableTreeNode(newdata)
% ...so we expand our tree at the last node we searched
node(idx).add(newnode)

% The change has to be propagated (this is where your recursion returns)
for it=length(node):-1:1,
    itnode=node(it);
    val = itnode.getUserObject()''
    newitemdata = val + newdata
    itnode.setUserObject(newitemdata)
end

% Let''s see if the new values are correct
searching = [0 1 1 0];
idx = 1;
node(idx) = top;
for item = searching,
    node(idx).getUserObject()''
    node(idx+1) = node(idx).getChildAt(item);
    idx = idx + 1;
end
node(idx).getUserObject()''

Answer 2

Sé que esto puede sonar estúpido ... pero ¿qué hay de mantener el número de nodos libres en lugar del número total de nodos? Esto requeriría una comparación con una constante (que es cero), que es el acceso de una sola propiedad.

Otra mejora del vudú sería mover .maxSize cerca de .num_nodes , y colocar ambos antes de la celda .Node . De este modo, su posición en la memoria no cambiará en relación con el inicio del objeto debido al crecimiento de la propiedad .Node (el vudú aquí es que estoy adivinando la implementación interna de los objetos en MATLAB).

Edición posterior Cuando hice un perfil con el .Node movido al final de la lista de propiedades, la mayor parte del tiempo de ejecución se consumió al extender la propiedad .Node , como se esperaba (5,45 segundos, en comparación con 1,25 segundos para la comparación que mencionó).

Answer 3

TL: DR Copia en profundidad todos los datos almacenados en cada inserción, inicializa la célula parent y la celda Node más grandes de lo que esperas que necesites.

Sus datos tienen una estructura de árbol, sin embargo, no está utilizando esto en su implementación. En su lugar, el código implementado es una versión hambrienta de cómputo de una tabla de consulta (en realidad 2 tablas), que almacena los datos y los datos relacionales del árbol.

Las razones por las que digo esto son las siguientes:

• Para insertar, llame a stree.addnote (padre, datos), que almacenará todos los datos en los campos de la stree objeto de árbol Node = {} y Parent = []
• parece saber antes a qué elemento de su árbol desea acceder ya que no se proporciona el código de búsqueda (si usa stree.getchild (ID) para ello, tengo algunas malas noticias)
• Una vez que haya procesado un nodo, lo rastreará usando find() que es una búsqueda de lista

De ninguna manera significa que la implementación sea torpe para los datos, incluso puede ser la mejor, dependiendo de lo que esté haciendo. Sin embargo, sí explica los problemas de asignación de memoria y proporciona sugerencias sobre cómo resolverlos.

Mantener datos como tabla de búsqueda

Una de las formas de almacenar datos es mantener la tabla de consulta subyacente. Solo haría esto, si conoce el ID del primer elemento que desea modificar sin buscarlo . Este caso le permite hacer su estructura más eficiente en dos pasos.

Primero inicie sus arreglos más grandes y luego lo que espera que necesite para almacenar los datos. Si se excede la capacidad de la tabla de consulta, se inicializa una nueva, que es X campos más grandes, y se realiza una copia en profundidad de los datos antiguos. Si necesita expandir capcity una o dos veces (durante todas las inserciones) puede que no sea un problema, pero en su caso, se hace una copia profunda para cada inserción.

En segundo lugar, cambiaría la estructura interna y fusionaría las dos tablas Node y Parent . La razón de esto es que la propagación hacia atrás en su código toma O (depth_from_root * n), donde n es el número de nodos en su tabla. Esto se debe a que find () se repetirá en toda la tabla para cada padre.

En su lugar puedes implementar algo similar a

table = cell(n,1) % n bigger then expected value
end_pointer = 1 % simple pointer to the first free value

function insert(data,parent_ID)
    if end_pointer < numel(table)
        content.data = data;
        content.parent = parent_ID;
        table{end_pointer} = content;
        end_pointer = end_pointer + 1;
    else
        % need more space, make sure its enough this time
        table = [table cell(end_pointer,1)];
        insert(data,parent_ID);
    end
end

function content = get_value(ID)
    content = table(ID);
end

Esto le da acceso instantáneo a la ID los padres sin la necesidad de find() primero, guardando n iteraciones en cada paso, por lo que el costo se convierte en O (profundidad). Si no conoce su nodo inicial, entonces debe find() ese, que cuesta O (n).

Tenga en cuenta que esta estructura no necesita is_leaf() , depth() , nnodes() o get_children() . Si aún los necesita, necesito más información sobre lo que desea hacer con sus datos, ya que esto influye en gran medida en una estructura adecuada.

Estructura de árbol

Esta estructura tiene sentido, si nunca se conoce el ID del primer nodo y, por lo tanto, siempre hay que buscarlo .

El beneficio es que la búsqueda de una nota arbitraria funciona con O (profundidad), por lo que la búsqueda es O (profundidad) en lugar de O (n) y la propagación hacia atrás es O (profundidad ^ 2) en lugar de O (profundidad + n). Tenga en cuenta que la profundidad puede ser desde log (n) para un árbol perfectamente equilibrado, que puede ser posible dependiendo de sus datos, hasta n para el árbol degenerado, que solo es una lista vinculada.

Sin embargo, para sugerir algo apropiado, requeriría más información, ya que cada estructura de árbol tiene su propio nich. Por lo que puedo ver hasta ahora, sugeriría un árbol desequilibrado, que está ''ordenado'' por el simple orden dado por un padre que quiere los nodos. Esto puede optimizarse aún más dependiendo de

• ¿Es posible definir un orden total en sus datos?
• ¿Cómo se tratan los valores dobles (los mismos datos aparecen dos veces)?
• ¿De qué escala son tus datos (miles, millones, ...)?
• es una búsqueda / búsqueda siempre emparejada con la propagación hacia atrás
• ¿Cuánto tiempo duran las cadenas de ''padre-hijo'' en sus datos (o qué tan equilibrado y profundo estará utilizando el árbol este simple orden)
• ¿Hay siempre un solo padre o es el mismo elemento insertado dos veces con padres diferentes?

Felizmente proporcionaré un código de ejemplo para el árbol anterior, solo déjeme un comentario

EDITAR: En su caso, un árbol desequilibrado (que se construye paralelo a hacer el MCTS) parece ser la mejor opción. El código a continuación asume que los datos se dividen en state y score y además que un state es único. Si no es así, esto seguirá funcionando, sin embargo, existe una posible optimización para aumentar el rendimiento de MCTS.

classdef node < handle
    % A node for a tree in a MCTS
    properties
        state = {}; %some state of the search space that identifies the node
        score = 0;
        childs = cell(50,1);
        num_childs = 0;
    end
    methods
        function obj = node(state)
            % for a new node simulate a score using MC
            obj.score = simulate_from(state); % TODO implement simulation state -> finish
            obj.state = state;
        end
        function value = update(obj)
            % update the this node using MC recursively
            if obj.num_childs == numel(obj.childs)
                % there are to many childs, we have to expand the table
                obj.childs = [obj.childs cell(obj.num_childs,1)];
            end
            if obj.do_exploration() || obj.num_childs == 0
                % explore a potential state
                state_to_explore = obj.explore();

                %check if state has already been visited
                terminate = false;
                idx = 1;
                while idx <= obj.num_childs && ~terminate
                    if obj.childs{idx}.state_equals(state_to_explore)
                        terminate = true;
                    end
                    idx = idx + 1;
                end

                %preform the according action based on search
                if idx > obj.num_childs
                    % state has never been visited
                    % this action terminates the update recursion 
                    % and creates a new leaf
                    obj.num_childs = obj.num_childs + 1;
                    obj.childs{obj.num_childs} = node(state_to_explore);
                    value = obj.childs{obj.num_childs}.calculate_value();
                    obj.update_score(value);
                else
                    % state has been visited at least once
                    value = obj.childs{idx}.update();
                    obj.update_score(value);
                end
            else
                % exploit what we know already
                best_idx = 1;
                for idx = 1:obj.num_childs
                    if obj.childs{idx}.score > obj.childs{best_idx}.score
                        best_idx = idx;
                    end
                end
                value = obj.childs{best_idx}.update();
                obj.update_score(value);
            end
            value = obj.calculate_value();
        end
        function state = explore(obj)
            %select a next state to explore, that may or may not be visited
            %TODO
        end
        function bool = do_exploration(obj)
            % decide if this node should be explored or exploited
            %TODO
        end
        function bool = state_equals(obj, test_state)
            % returns true if the nodes state is equal to test_state
            %TODO
        end
        function update_score(obj, value)
            % updates the score based on some value
            %TODO
        end
        function calculate_value(obj)
            % returns the value of this node to update previous nodes
            %TODO
        end
    end
end

Algunos comentarios sobre el código:

• Dependiendo de la configuración, el obj.calculate_value() podría no ser necesario. Por ejemplo, si es un valor que puede calcularse evaluando solo las puntuaciones del niño
• si un state puede tener varios padres, tiene sentido reutilizar el objeto de nota y cubrirlo en la estructura
• como cada node conoce a todos sus hijos, se puede generar fácilmente un subárbol usando un node como nodo raíz
• buscar en el árbol (sin ninguna actualización) es una búsqueda codiciosa recursiva simple
• Dependiendo del factor de bifurcación de su búsqueda, podría valer la pena visitar cada posible hijo una vez (al inicializar el nodo) y luego realizar una randsample(obj.childs,1) para la exploración, ya que esto evita la copia / reasignación de la matriz secundaria
• La propiedad parent se codifica a medida que el árbol se actualiza de forma recursiva, pasando el value primario a la finalización de la actualización de un nodo.
• La única vez que reasigno memoria es cuando un solo nodo tiene más de 50 niños, solo hago una reasignación para ese nodo individual

Esto debería correr mucho más rápido, ya que solo se preocupa por la parte del árbol que se elija y no toca nada más.