主页 / 问题 / 1565980
Accepted
Глеб
Asked:2024-02-12 18:53:58 +0000 UTC2024-02-12 18:53:58 +0000 UTC

解析Python中的循环结构

  • 772

假设我们有某种列表：

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

问题：是否可以实时解析这样的结构？我当然可以编写一个详尽的搜索函数，不会让递归进入循环，但算法的复杂度显然会增加几个数量级。是否有算法可以加快“通过”此类列表的速度？

PS 不，这是一个纯粹的理论任务。如果我尝试不在 Python 中而是在 Explorer 中实现这一点，那么 Windows 会很快告诉我它对我的所有想法。所以这个任务没有真正的类似物。我只是无事可做）

python

1 个回答

  1. Best Answer

    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

    PS一旦发生了递归，就需要添加不带递归的版本。遍历节点的顺序颠倒了，但含义是一样的：

    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
    • 3

相关问题