1

3 つの numpy 配列 (id、parent_id) (ルート要素のparent_id は -1) を持つ次のデータ構造体を想定します。

import numpy as np
class MyStructure(object):
  def __init__(self):
    """
    Default structure for now:

          1
         / \
        2   3
           / \
          4   5
    """
    self.ids = np.array([1,2,3,4,5])
    self.parent_ids = np.array([-1, 1, 1, 3, 3])

  def id_successors(self, idOfInterest):
    """
    Return logical index.
    """
    return self.parent_ids == idOfInterest

  def subtree(self, newRootElement):
    """
    Return logical index pointing to elements of the subtree.
    """
    init_vector = np.zeros(len(self.ids), bool)
    init_vector[np.where(self.ids==newRootElement)[0]] = 1
    if sum(self.id_successors(newRootElement))==0:
      return init_vector
    else:
      subtree_vec = init_vector
      for sucs in self.ids[self.id_successors(newRootElement)==1]:
        subtree_vec += self.subtree(sucs)
      return subtree_vec

これは、多くのID (>1000)で非常に遅くなります。それを実装するより速い方法はありますか？

4

4 に答える 4

4

あなたを傷つけているのは再帰自体ではないと思いますが、すべてのステップで（すべての要素にわたって）非常に幅広い操作が多数あります。検討：

init_vector[np.where(self.ids==newRootElement)[0]] = 1

これは、すべての要素のスキャンを実行し、一致するすべての要素のインデックスを計算してから、最初の要素のインデックスのみを使用します。この特定の操作は、リスト、タプル、および配列のメソッド インデックスとして利用でき、そこではより高速です。ID が一意の場合、init_vector は単純に ids==newRootElement です。

if sum(self.id_successors(newRootElement))==0:

再びすべての要素を線形スキャンし、次に配列全体を縮小して、一致するものがあるかどうかを確認します。このタイプの操作にはanyを使用しますが、ここでもすべての要素をチェックする必要はありません。「if newRootElement が self.parent_ids にない場合」で問題は解決しますが、for を実行することは完全に有効であるため、必要ありません。空のリストをループします。

最後に、最後のループがあります。

for sucs in self.ids[self.id_successors(newRootElement)==1]:

今回は、id_successors 呼び出しが繰り返され、結果が不必要に 1 と比較されます。その後にのみ再帰が行われ、上記のすべての操作が各ブランチに対して (異なる newRootElement に対して) 繰り返されることを確認します。

コード全体は、単方向ツリーの逆トラバーサルです。私たちには両親がいて、子供が必要です。numpy が設計されているような幅広い操作を行う場合は、それらをカウントするのが最善です。したがって、私たちが気にする唯一の操作は、親ごとの子のリストを作成することです。1回の反復でそれを行うのはそれほど難しくありません:

import collections
children=collections.defaultdict(list)
for i,p in zip(ids,parent_ids):
  children[p].append(i)

def subtree(i):
  return i, map(subtree, children[i])

必要な正確な構造は、ツリーの変更頻度、ツリーの大きさ、分岐の量、要求する必要があるサブツリーの大きさと数など、さらに多くの要因によって異なります。たとえば、上記のディクショナリとリストの構造は、メモリ効率があまりよくありません。あなたの例もソートされているため、操作がさらに簡単になります。

于 2010-07-29T12:31:04.490 に答える
4

Python 2.6 を使用している場合、psyco モジュールを使用しようとしましたか? コードを劇的に高速化できる場合があります。

再帰的なデータ構造: リストを考慮しましたか?

あなたの例も標準リストです：

[1, 2 , [3, [4],[5]]]

また

[1, [2, なし, なし], [3, [4, なし, なし],[5, なし, なし]]]

私のきれいなプリンターで：

[1, 
  [2, None, None], 
  [3, 
    [4, None, None], 
    [5, None, None]]]

サブツリーの準備が整いました。正しいツリーに値を挿入するのに時間がかかります。heapq モジュールがニーズに合っているかどうかも確認する価値があります。

また、Guido 自身がhttp://python.org/doc/essays/graphs.htmlでトラバースとツリーに関する洞察を提供しています。

これは、基本的なリスト型の置換として実際に Python に提案されたものの、その関数で拒否された、いくつかの高度に見えるツリーのものです。ブリストモジュール

于 2010-07-28T07:12:14.820 に答える
3

理論的には、すべてのアルゴリズムは反復的にも再帰的にも書くことができます。しかし、これは誤謬です (チューリング完全性など)。実際には、反復を介して任意にネストされたツリーをウォークすることは、一般的に実行可能ではありません。最適化する必要があるとは思えません (少なくとも subtree_vec をインプレースで変更しています)。何千もの要素に対して xを実行することは、繰り返し実行するか再帰的に実行するかに関係なく、本質的に非常に高価です。具体的な実装では、せいぜい数回のマイクロ最適化が可能であり、せいぜい 5% 未満の改善が得られます。同じデータが何度も必要な場合は、キャッシュ/メモ化が最善の策です。たぶん、誰かがあなたの特定のツリー構造のための派手な O(log n) アルゴリズムを持っているかもしれません。

于 2010-07-28T07:02:57.297 に答える
0

これが私の答えです（クラスにアクセスせずに書かれているため、インターフェースは少し異なりますが、十分に高速かどうかをテストできるようにそのまま添付しています）：
=========== ============ファイルgraph_array.py==========================


import collections
import numpy

def find_subtree(pids, subtree_id):
    N = len(pids)
    assert 1 <= subtree_id <= N

    subtreeids = numpy.zeros(pids.shape, dtype=bool)
    todo = collections.deque([subtree_id])

    iter = 0
    while todo:
        id = todo.popleft()
        assert 1 <= id <= N
        subtreeids[id - 1] = True

        sons = (pids == id).nonzero()[0] + 1
        #print 'id={0} sons={1} todo={2}'.format(id, sons, todo)
        todo.extend(sons)

        iter = iter+1
        if iter>N:
            raise ValueError()

    return subtreeids

=======================ファイルgraph_array_test.py======================ファイル===


import numpy
from graph_array import find_subtree

def _random_graph(n, maxsons):
    import random
    pids = numpy.zeros(n, dtype=int)
    sons = numpy.zeros(n, dtype=int)
    available = []
    for id in xrange(1, n+1):
        if available:
            pid = random.choice(available)

            sons[pid - 1] += 1
            if sons[pid - 1] == maxsons:
                available.remove(pid)
        else:
            pid = -1
        pids[id - 1] = pid
        available.append(id)
    assert sons.max() <= maxsons
    return pids

def verify_subtree(pids, subtree_id, subtree):
    ids = set(subtree.nonzero()[0] + 1)
    sons = set(ids) - set([subtree_id])
    fathers = set(pids[id - 1] for id in sons)
    leafs = set(id for id in ids if not (pids == id).any())
    rest = set(xrange(1, pids.size+1)) - fathers - leafs
    assert fathers & leafs == set()
    assert fathers | leafs == ids
    assert ids & rest == set()

def test_linear_graph_gen(n, genfunc, maxsons):
    assert maxsons == 1
    pids = genfunc(n, maxsons)

    last = -1
    seen = set()
    for _ in xrange(pids.size):
        id = int((pids == last).nonzero()[0]) + 1
        assert id not in seen
        seen.add(id)
        last = id
    assert seen == set(xrange(1, pids.size + 1))

def test_case1():
    """
            1
           / \
          2   4
         /
        3
    """
    pids = numpy.array([-1, 1, 2, 1])

    subtrees = {1: [True, True, True, True],
                2: [False, True, True, False],
                3: [False, False, True, False],
                4: [False, False, False, True]}

    for id in xrange(1, 5):
        sub = find_subtree(pids, id)
        assert (sub == numpy.array(subtrees[id])).all()
        verify_subtree(pids, id, sub)

def test_random(n, genfunc, maxsons):
    pids = genfunc(n, maxsons)
    for subtree_id in numpy.arange(1, n+1):
        subtree = find_subtree(pids, subtree_id)
        verify_subtree(pids, subtree_id, subtree)

def test_timing(n, genfunc, maxsons):
    import time
    pids = genfunc(n, maxsons)
    t = time.time()
    for subtree_id in numpy.arange(1, n+1):
        subtree = find_subtree(pids, subtree_id)
    t = time.time() - t
    print 't={0}s = {1:.2}ms/subtree = {2:.5}ms/subtree/node '.format(
        t, t / n * 1000, t / n**2 * 1000),

def pytest_generate_tests(metafunc):
    if 'case' in metafunc.function.__name__:
        return
    ns = [1, 2, 3, 4, 5, 10, 20, 50, 100, 1000]
    if 'timing' in metafunc.function.__name__:
        ns += [10000, 100000, 1000000]
        pass
    for n in ns:
        func = _random_graph
        for maxsons in sorted(set([1, 2, 3, 4, 5, 10, (n+1)//2, n])):
            metafunc.addcall(
                funcargs=dict(n=n, genfunc=func, maxsons=maxsons),
                id='n={0} {1.__name__}/{2}'.format(n, func, maxsons))
            if 'linear' in metafunc.function.__name__:
                break

===================py.test --tb=short -v -s test_graph_array.py============

...
test_graph_array.py:72: test_timing[n=1000 _random_graph/1] t=13.4850590229s = 13.0ms/サブツリー = 0.013485ms/サブツリー/ノード PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/2] t=0.318281888962s = 0.32ms/サブツリー = 0.00031828ms/サブツリー/ノード PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/3] t=0.265519142151s = 0.27ms/サブツリー = 0.00026552ms/サブツリー/ノード PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/4] t=0.24147105217s = 0.24ms/サブツリー = 0.00024147ms/サブツリー/ノード PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/5] t=0.211434841156s = 0.21ms/サブツリー = 0.00021143ms/サブツリー/ノード PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/10] t=0.178458213806s = 0.18ms/サブツリー = 0.00017846ms/サブツリー/ノード PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/500] t=0.209936141968s = 0.21ms/サブツリー = 0.00020994ms/サブツリー/ノード PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/1000] t=0.245707988739s = 0.25ms/サブツリー = 0.00024571ms/サブツリー/ノード PASS
...

ここでは、すべてのツリーのすべてのサブツリーが取得されます。興味深い値は、ツリーを抽出する平均時間です。厳密に線形のツリーを除いて、サブツリーあたり ~0.2ms です。ここで何が起こっているのかわかりません。

于 2010-07-29T09:41:47.507 に答える