优化算法以处理元组、集合和字典

Question

我有一个列表展平算法：

def flatten(s):
    if not s:
        return s
    if isinstance(s[0], (list, set, tuple)):
        return flatten(s[0]) + flatten(s[1:])
    return s[:1] + flatten(s[1:])

但是如果您组合两种不同数据类型，它就不起作用了。例如，元组中的列表。有没有办法做到这一点？也可以将字典扁平化吗？值，而不是键。

Answer 1

通常建议使用 itertools -> chain 或标准库，但对于任意嵌套的容器：

xlen = len(x)
result = []    

def flatten(x, i, xlen, result):
  if i >= xlen:
    return
  if not isinstance(x[i], (list, set, tuple)):
    result.append(x[i])
  else:
    flatten(list(x[i]), 0, len(x[i]), result)
  flatten(x, i+1, xlen, result)

您可以为空容器等添加边角情况

Answer 2

SO 上有多种算法可以展平嵌套列表和元组，但我们会坚持使用您的算法。第一个观察结果是您编写的算法不适用于 set 个实例，因为它们不可订阅。所以集合必须去：

def flatten(s):
    if not s:
        return s
    if isinstance(s[0], (list, tuple)):
        return list(flatten(s[0])) + list(flatten(s[1:]))
    return list(s[:1]) + list(flatten(s[1:]))

flatten([[1,2,(3,4,(5,6))]])

打印：

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

Answer 3

如果您正在寻找优化和一些乐趣...... 递归没问题，但不要忘记 RecursionError。

输入：

from datetime import datetime
from typing import Sequence


def timer(f):
    def wrapped(s):
        start = datetime.now()
        result = f(s)
        print(datetime.now() - start)
        return result
    return wrapped


@timer
def str_method(s: Sequence):
    return [int(x) for x in
            str(s).replace("(", "[").replace(")", "]")[1:-1].replace("[", "").replace("]", "")
            if x not in [",", " "]]


def flatten(s: Sequence):
    if not s:
        return s
    if isinstance(s[0], (list, tuple)):
        return list(flatten(s[0])) + list(flatten(s[1:]))
    return list(s[:1]) + list(flatten(s[1:]))

if __name__ == '__main__':
    s = [1, 2, (3, 4, (5, 6))]
    start = datetime.now()
    print(flatten(s))
    print(datetime.now() - start)
    print(str_method(s))
    print("-")
    s = [(x, ) for x in range(100)]
    start = datetime.now()
    flatten(s)
    print(datetime.now() - start)
    str_method(s)
    print("-")
    s = [(x, ) for x in range(100000)]
    start = datetime.now()
    try:
        print(flatten(s))
    except RecursionError:
        print("RecursionError")
    str_method(s)

输出：

[1, 2, 3, 4, 5, 6]
0:00:00.000022 # flatten
0:00:00.000041 # str_method
[1, 2, 3, 4, 5, 6]
-
0:00:00.000369 # flatten
0:00:00.000122 # str_method
-
RecursionError # flatten
0:00:00.186894 # str_method

Answer 4

其他答案都有效，但如果您将 sympy 导入到您的代码中，也许可以使用它的展平方法？速度非常快，适合您的需求。

优化算法以处理元组、集合和字典

Optimize algorithm to work with tuples, sets and dictionarys

python

algorithm

flatten