访问嵌套列表和数组中没有递归的所有元素 [英] visit all elements in nested lists and dicts without recursion

问题描述

我有一个由嵌套列表和分组组成的结构。我想为每个元素应用
函数。如果没有递归，就可以这样做。

  def visit（data，func）：
 if isinstance（data，dict） ：
 for k，v in data.items（）：
 data [k] = visit（v，func）
返回数据
 elif isinstance（data，list）：
 for i，v in enumerate（data）：
 data [i] = visit（v，func）
 return data 
 else：
 return func（data）
  

递归版本适用于小数据，但是当数据为...时，我会点击RecursionError
异常我寻找一般的方法来消除递归，我发现依赖
首先将递归调用转换为尾部调用，我的问题在于是
在我的例子中的递归调用在一个循环内。

解决方案

这种方法将会起作用。然而，为了纪录，我同意Sven Marnach的说法，如果你正在打破递归限制的嵌套，那么你的数据结构就会出现这样的一些东西。如果Sven猜想，你在你的数据中有循环，这种方法也会破裂。

  data = [1,2，{'a'：1，'b'：{'a' 
 
 def apply（data，f）：
 stack = [] 
 stack.append（data）
 while stack： 
 data = stack.pop（）
 if isinstance（data，dict）：
 for k，v in data.items（）：
 if isinstance（v，（dict，列表）：
 stack.append（v）
 else：
 data [k] = f（v）
 if isinstance（data，list）：
 for我的e枚举（数据）：
如果isinstance（e，（dict，list））：
 stack.append（e）
 else：
 data [i] = f（e）
  

在解释器shell中：

  $ python -i apply.py 
>>> apply（data，lambda x：x + 1）
>>>>数据
 [2，3，{'a'：2，'b'：{'a'：[2，3，4]}}，4] 
>>> 
  

I have a structure consisting of nested lists and dicts. I want to apply a function to every element. How to do it without recursion.

def visit(data, func):
    if isinstance(data, dict):
        for k, v in data.items():
            data[k] = visit(v, func)
        return data
    elif isinstance(data, list):
        for i, v in enumerate(data):
            data[i] = visit(v, func)
        return data
    else:
        return func(data)

The recursive version works for small data, but I hit the RecursionError exception when the data is big.

I looked for general ways to eliminate recursion, the ones I found rely on first transforming the recursive call to a tail call, my problem with this is the recursive call in my example is inside a loop.

解决方案

This approach will work. For the record, though, I agree with Sven Marnach that there is something definitely fishy going on with your data structures if you have nesting that is breaking the recursion limit. If as Sven conjectures,you have cycles in your data, this approach will also break.

data = [1,2, {'a':1, 'b':{'a':[1,2,3]}},3]

def apply(data, f):
    stack = []
    stack.append(data)
    while stack:
        data = stack.pop()
        if isinstance(data, dict):
            for k,v in data.items():
                if isinstance(v, (dict,list)):
                    stack.append(v)
                else:
                    data[k] = f(v)
        if isinstance(data, list):
            for i,e in enumerate(data):
                if isinstance(e, (dict,list)):
                    stack.append(e)
                else:
                    data[i] = f(e)

In the interpreter shell:

$ python -i apply.py
>>> apply(data, lambda x: x + 1)
>>> data
[2, 3, {'a': 2, 'b': {'a': [2, 3, 4]}}, 4]
>>> 

这篇关于访问嵌套列表和数组中没有递归的所有元素的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！