1

以下のように定義されたノード データ構造があり、find_matching_node メソッドが Pythonic または効率的かどうか確信が持てませんでした。私はジェネレーターに精通していませんが、それらを使用したより良い解決策があると思います。何か案は？

class HierarchyNode():

    def __init__(self, nodeId):
        self.nodeId = nodeId
        self.children = {} # opted for dictionary to help reduce lookup time

    def addOrGetChild(self, childNode):
        return self.children.setdefault(childNode.nodeId,childNode)


    def find_matching_node(self, node):
        '''
        look for the node in the immediate children of the current node.
        if not found recursively look for it in the children nodes until 
        gone through all nodes
        '''
        matching_node = self.children.get(node.nodeId)
        if matching_node:
            return matching_node
        else:
            for child in self.children.itervalues():
                matching_node = child.find_matching_node(node)
                if matching_node:
                    return matching_node
            return None
4

2 に答える 2

0

ツリーで必要な他の操作と、この再帰を実行する必要がある頻度に応じて、すべての子孫ノードをノードのディクショナリに格納できるため、この再帰関数全体を単一のディクショナリ ルックアップにすることができます。

于 2012-06-08T21:46:24.727 に答える
0

FWIW、車輪を再発明するよりも、再利用可能なツリーデータ構造を使用する方が良いかもしれません. ランタイムとワークロードに応じて、CPython について私が見た中で最高のものは、ここで説明されています: http://stromberg.dnsalias.org/~strombrg/python-tree-and-heap-comparison/

...しかし、要するに、私が見た最高のものは splay ツリー、AVL ツリー、および treap でした。

于 2012-06-08T22:36:06.697 に答える