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

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 -> 链或标准库，但对于任意嵌套的容器：

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

如果您正在寻找优化和一些乐趣...... 递归是好的，但不要忘记递归错误。

输入：

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导入到代码中，也许使用它的flatten方法？它非常快，适合您的需求。