Парсинг зацикленных структур на Python

Question

Предположим, у нас есть какой-то список:

>>> l = [1, 2, 3, [4, [5], [6, 7]]]

И нам нужно узнать сумму его членов. Все понятно, обычная рекурсия:

>>> def list_sum(l):
        r = 0
        for i in l:
            if type(i) == int:
                r += i
            elif type(i) == list:
                r += list_sum(i)
        return r

>>> list_sum(l)
28

А теперь мы кое-что сделаем со списком.

>>> l.append(l)
>>> l
[1, 2, 3, [4, [5], [6, 7]], [...]]

Это называется "зациклить" список. Снова попробуем вычислить сумму членов. И конечно же...

>> list_sum(l)
    Traceback (most recent call last):
      File "<pyshell#22>", line 1, in <module>
        list_sum(l)
      File "<pyshell#17>", line 7, in list_sum
        r += list_sum(i)
      File "<pyshell#17>", line 7, in list_sum
        r += list_sum(i)
      File "<pyshell#17>", line 7, in list_sum
        r += list_sum(i)
      [Previous line repeated 1022 more times]
      File "<pyshell#17>", line 4, in list_sum
        if type(i) == int:
    RecursionError: maximum recursion depth exceeded in comparison

Так, и как с этим бороться?

>>> def new_sum(l):
        r = 0
        for i in l:
            if type(i) == int:
                r += i
            elif type(i) == list:
                if i is l:
                    pass
                else:
                    r += new_sum(i)
        return r

>>> new_sum(l)
28

Запутаем список еще сильнее:

>>> l[3].append(l)
>>> l
[1, 2, 3, [4, [5], [6, 7], [...]], [...]]

...и уже не работает:

>>> new_sum(l)
    Traceback (most recent call last):
      File "<pyshell#40>", line 1, in <module>
        new_sum(l)
      File "<pyshell#36>", line 10, in new_sum
        r += new_sum(i)
      File "<pyshell#36>", line 10, in new_sum
        r += new_sum(i)
      File "<pyshell#36>", line 10, in new_sum
        r += new_sum(i)
      [Previous line repeated 1022 more times]
      File "<pyshell#36>", line 4, in new_sum
        if type(i) == int:
    RecursionError: maximum recursion depth exceeded in comparison

Вопрос: возможен ли парсинг подобных структур за реальное время? Я, конечно, могу написать функцию полного перебора, которая не будет давать зацикливаться рекурсии, но сложность алгоритма явно возрастет на несколько порядков. Существуют алгоритмы для ускоренного "прохода" по таким спискам?

P. S. Нет, это чисто теоретическая задача. Если попробовать реализовать это не на питоне, а в "Проводнике", то винда быстро выскажет все, что о мне думает. Так что реальных аналогов задача не имеет. Мне просто нечего делать)

Answer 1

NB Идеи фильтрации и фильтрации именно по id заимствованы из комментариев к вопросу.

Функция traverse обходит вложенные списки. Циклические ссылки фильтруются через множество посещённых id - visited. Мало отличается от обхода графа в глубину:

def traverse(v):
    visited = set()

    def rec(v):
        if isinstance(v, list):
            if id(v) not in visited:
                visited.add(id(v))
                for vv in v:
                    yield from rec(vv)
        else:
            yield v

    yield from rec(v)


lst = [1, 2, 3, [4, [5], [6, 7]]]
lst.append(lst)
lst[3].append(lst)
print(lst)
print(*traverse(lst))
print(sum(traverse(lst)))

$ python traverse.py
[1, 2, 3, [4, [5], [6, 7], [...]], [...]]
1 2 3 4 5 6 7
28

P.S. Раз случилась рекурсия, надо добавить версию без рекурсии. Порядок обхода узлов изменился на обратный, но смысл прежний:

def traverse(v):
    visited = set()

    stack = [v]
    while stack:
        v = stack.pop()
        if isinstance(v, list):
            if id(v) not in visited:
                visited.add(id(v))
                # stack.extend(reversed(v))  # если нужно сохранить порядок
                stack.extend(v)
        else:
            yield v


lst = [1, 2, 3, [4, [5], [6, 7]]]
lst.append(lst)
lst[3].append(lst)
print(lst)
print(*traverse(lst))
print(sum(traverse(lst)))

$ python traverse.py
[1, 2, 3, [4, [5], [6, 7], [...]], [...]]
7 6 5 4 3 2 1
28

БЛОГ НА HUSL

Парсинг зацикленных структур на Python

Ответы (1 шт):