Есть ли более быстрый способ получить поддеревья из древовидных структур в python, чем стандартное «рекурсивное»?

Question

Давайте предположим следующую структуру данных с тремя массивами (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

Это получение очень медленно для многих идентификаторов (> 1000).Есть ли более быстрый способ реализовать это?

Answer 1

Я думаю, что не рекурсия как таковая причиняет вам боль, а множество очень широких операций (по всем элементам) для каждого шага.Рассмотрим:

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

. При этом выполняется сканирование всех элементов, вычисляется индекс каждого соответствующего элемента, а затем используется только индекс первого.Эта конкретная операция доступна как индекс метода для списков, кортежей и массивов - и там быстрее.Если идентификаторы уникальны, init_vector - это просто ids == newRootElement.

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

Снова линейное сканирование каждого элемента, затем сокращение всего массива, просто чтобы проверить, есть ли совпадения.Используйте any для этого типа операции, но опять же нам даже не нужно выполнять проверку всех элементов - «если newRootElement не в self.parent_ids» делает работу, но это не обязательно, так каквполне допустимо сделать цикл for над пустым списком.

Наконец, есть последний цикл:

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

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

Весь код является обратным обходом однонаправленного дерева.У нас есть родители и нужны дети.Если мы хотим выполнять широкие операции, например, для которых предназначена numpy, мы бы лучше их подсчитали - и, таким образом, единственная операция, о которой мы заботимся, - это создание списка детей на одного родителя.Это не очень сложно сделать с помощью одной итерации:

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])

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

Answer 2

Вы пытались использовать модуль psyco, если вы используете Python 2.6?Иногда это может значительно ускорить код.

Рассматривали ли вы рекурсивную структуру данных: список?

Ваш пример также является стандартным списком:

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

или

[1, [2, Нет, Нет], [3, [4, None, None], [5, None, None]]]

Моим симпатичным принтером :

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

Поддерево уже готово, вам понадобится некоторое время для вставки значений в правильное дерево.Также стоит проверить, соответствует ли модуль heapq вашим потребностям.

Также сам Гвидо дает некоторое представление о обходе и деревьях в http://python.org/doc/essays/graphs.html,, может быть, вы знаете об этом.

Вот некоторые продвинутые древовидные элементы, фактически предложенные для Python в качестве базовой замены типа списка, но отклоненные в этой функции. Модуль Blist

Answer 3

Теоретически, каждый алгоритм может быть написан как итеративно, так и рекурсивно.Но это заблуждение (например, полнота по Тьюрингу).На практике обход произвольно вложенного дерева с помощью итерации обычно неосуществим.Я сомневаюсь, что есть что оптимизировать (по крайней мере, вы модифицируете subtree_vec на месте).Выполнение x на тысячах элементов является по своей сути чертовски дорогим, независимо от того, делаете ли вы это итеративно или рекурсивно.В лучшем случае возможны несколько микрооптимизаций для конкретной реализации, которые в лучшем случае дадут улучшение <5%.Лучшим вариантом будет кэширование / запоминание, если вам нужны одни и те же данные несколько раз.Может быть, у кого-то есть причудливый алгоритм O (log n) для вашей конкретной древовидной структуры в рукаве, я даже не знаю, возможен ли он (я бы предположил, что нет, но манипулирование деревьями - это не мой посох жизни).1003 *

Answer 4

Это мой ответ (написан без доступа к вашему классу, поэтому интерфейс немного отличается, но я прилагаю его как есть, чтобы вы могли проверить, достаточно ли он быстр):
======================= file 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/subtree = 0.013485ms/subtree/node PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/2] t=0.318281888962s = 0.32ms/subtree = 0.00031828ms/subtree/node PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/3] t=0.265519142151s = 0.27ms/subtree = 0.00026552ms/subtree/node PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/4] t=0.24147105217s = 0.24ms/subtree = 0.00024147ms/subtree/node PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/5] t=0.211434841156s = 0.21ms/subtree = 0.00021143ms/subtree/node PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/10] t=0.178458213806s = 0.18ms/subtree = 0.00017846ms/subtree/node PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/500] t=0.209936141968s = 0.21ms/subtree = 0.00020994ms/subtree/node PASS
test_graph_array.py:72: test_timing[n=1000 _random_graph/1000] t=0.245707988739s = 0.25ms/subtree = 0.00024571ms/subtree/node PASS
...

Здесь берется каждое поддерево каждого дерева, и интересным значением является среднее время для извлечения дерева: ~ 0,2 мс на поддерево, за исключением строго линейных деревьев. Я не уверен, что здесь происходит.