tel*_*t99 412 python optimization list flatten
是的,我知道这个主题已经被覆盖过了(这里,这里,这里,这里),但据我所知,除了一个之外,所有解决方案都在这样的列表中失败:
L = [[[1, 2, 3], [4, 5]], 6]
期望的输出是什么
[1, 2, 3, 4, 5, 6]
或者甚至更好,一个迭代器.我看到的唯一适用于任意嵌套的解决方案可以在这个问题中找到:
def flatten(x):
result = []
for el in x:
if hasattr(el, "__iter__") and not isinstance(el, basestring):
result.extend(flatten(el))
else:
result.append(el)
return result
flatten(L)
这是最好的型号吗？我忽略了什么吗？任何问题？
Cri*_*ian 358
使用生成器函数可以使您的示例更容易阅读,并可能提高性能.
def flatten(l):
for el in l:
if isinstance(el, collections.Iterable) and not isinstance(el, basestring):
for sub in flatten(el):
yield sub
else:
yield el
我使用2.6中添加的Iterable ABC.
在Python 3中,basestring不再是,但你可以使用元组str并bytes在那里获得相同的效果.
该yield from运营商从发生器一次一个返回的项目.这句法委派到子发生器在3.3加入
def flatten(l):
for el in l:
if isinstance(el, collections.Iterable) and not isinstance(el, (str, bytes)):
yield from flatten(el)
else:
yield el
Jos*_*Lee 46
我的解决方案
import collections
def flatten(x):
if isinstance(x, collections.Iterable):
return [a for i in x for a in flatten(i)]
else:
return [x]
更简洁,但几乎相同.
Ale*_*lli 34
根据@Andrew在评论中的要求,@ unutbu的非递归解决方案的生成器版本:
def genflat(l, ltypes=collections.Sequence):
l = list(l)
i = 0
while i < len(l):
while isinstance(l[i], ltypes):
if not l[i]:
l.pop(i)
i -= 1
break
else:
l[i:i + 1] = l[i]
yield l[i]
i += 1
这个发电机的略微简化版本:
def genflat(l, ltypes=collections.Sequence):
l = list(l)
while l:
while l and isinstance(l[0], ltypes):
l[0:1] = l[0]
if l: yield l.pop(0)
dan*_*lmo 33
使用递归和duck typing的生成器(针对Python 3更新):
def flatten(L):
for item in L:
try:
yield from flatten(item)
except TypeError:
yield item
list(flatten([[[1, 2, 3], [4, 5]], 6]))
>>>[1, 2, 3, 4, 5, 6]
unu*_*tbu 26
这个版本flatten避免了python的递归限制(因此适用于任意深度,嵌套的iterables).它是一个可以处理字符串和任意迭代(甚至是无限迭代)的生成器.
import itertools as IT
import collections
def flatten(iterable, ltypes=collections.Iterable):
remainder = iter(iterable)
while True:
first = next(remainder)
if isinstance(first, ltypes) and not isinstance(first, (str, bytes)):
remainder = IT.chain(first, remainder)
else:
yield first
以下是一些展示其用途的示例:
print(list(IT.islice(flatten(IT.repeat(1)),10)))
# [1, 1, 1, 1, 1, 1, 1, 1, 1, 1]
print(list(IT.islice(flatten(IT.chain(IT.repeat(2,3),
{10,20,30},
'foo bar'.split(),
IT.repeat(1),)),10)))
# [2, 2, 2, 10, 20, 30, 'foo', 'bar', 1, 1]
print(list(flatten([[1,2,[3,4]]])))
# [1, 2, 3, 4]
seq = ([[chr(i),chr(i-32)] for i in range(ord('a'), ord('z')+1)] + list(range(0,9)))
print(list(flatten(seq)))
# ['a', 'A', 'b', 'B', 'c', 'C', 'd', 'D', 'e', 'E', 'f', 'F', 'g', 'G', 'h', 'H',
# 'i', 'I', 'j', 'J', 'k', 'K', 'l', 'L', 'm', 'M', 'n', 'N', 'o', 'O', 'p', 'P',
# 'q', 'Q', 'r', 'R', 's', 'S', 't', 'T', 'u', 'U', 'v', 'V', 'w', 'W', 'x', 'X',
# 'y', 'Y', 'z', 'Z', 0, 1, 2, 3, 4, 5, 6, 7, 8]
虽然flatten可以处理无限生成器,但它无法处理无限嵌套:
def infinitely_nested():
while True:
yield IT.chain(infinitely_nested(), IT.repeat(1))
print(list(IT.islice(flatten(infinitely_nested()), 10)))
# hangs
sam*_*ias 24
这是我的递归flatten的功能版本,它处理元组和列表,并允许你输入任何位置参数的混合.返回一个生成整个序列的生成器,arg by arg:
flatten = lambda *n: (e for a in n
for e in (flatten(*a) if isinstance(a, (tuple, list)) else (a,)))
用法:
l1 = ['a', ['b', ('c', 'd')]]
l2 = [0, 1, (2, 3), [[4, 5, (6, 7, (8,), [9]), 10]], (11,)]
print list(flatten(l1, -2, -1, l2))
['a', 'b', 'c', 'd', -2, -1, 0, 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11]
Mar*_*son 18
Pandas 有一个函数可以做到这一点。正如您提到的，它返回一个迭代器。
In [1]: import pandas
In [2]: pandas.core.common.flatten([[[1, 2, 3], [4, 5]], 6])
Out[2]: <generator object flatten at 0x7f12ade66200>
In [3]: list(pandas.core.common.flatten([[[1, 2, 3], [4, 5]], 6]))
Out[3]: [1, 2, 3, 4, 5, 6]
cla*_*lay 13
这是另一个更有趣的答案......
import re
def Flatten(TheList):
a = str(TheList)
b,crap = re.subn(r'[\[,\]]', ' ', a)
c = b.split()
d = [int(x) for x in c]
return(d)
基本上,它将嵌套列表转换为字符串,使用正则表达式去除嵌套语法,然后将结果转换回(展平)列表.
kev*_*kev 10
def flatten(xs):
res = []
def loop(ys):
for i in ys:
if isinstance(i, list):
loop(i)
else:
res.append(i)
loop(xs)
return res
您可以使用deepflatten第三方包iteration_utilities:
>>> from iteration_utilities import deepflatten
>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> list(deepflatten(L))
[1, 2, 3, 4, 5, 6]
>>> list(deepflatten(L, types=list)) # only flatten "inner" lists
[1, 2, 3, 4, 5, 6]
它是一个迭代器,因此您需要迭代它(例如通过将其包装list或在循环中使用它).在内部,它使用迭代方法而不是递归方法,并且它被编写为C扩展,因此它可以比纯python方法更快:
>>> %timeit list(deepflatten(L))
12.6 µs ± 298 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit list(deepflatten(L, types=list))
8.7 µs ± 139 ns per loop (mean ± std. dev. of 7 runs, 100000 loops each)
>>> %timeit list(flatten(L)) # Cristian - Python 3.x approach from https://stackoverflow.com/a/2158532/5393381
86.4 µs ± 4.42 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit list(flatten(L)) # Josh Lee - https://stackoverflow.com/a/2158522/5393381
107 µs ± 2.99 µs per loop (mean ± std. dev. of 7 runs, 10000 loops each)
>>> %timeit list(genflat(L, list)) # Alex Martelli - https://stackoverflow.com/a/2159079/5393381
23.1 µs ± 710 ns per loop (mean ± std. dev. of 7 runs, 10000 loops each)
我是iteration_utilities图书馆的作者.
尝试创建一个可以在Python中压缩不规则列表的函数很有趣,但当然这就是Python的目的(使编程变得有趣).以下生成器运行良好,但有一些注意事项:
def flatten(iterable):
try:
for item in iterable:
yield from flatten(item)
except TypeError:
yield iterable
这将拉平,你可能想单独留在家中的数据类型(如bytearray,bytes和str对象).此外,代码依赖于从非迭代请求迭代器引发a的事实TypeError.
>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> def flatten(iterable):
try:
for item in iterable:
yield from flatten(item)
except TypeError:
yield iterable
>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>>
编辑:
我不同意以前的实施.问题是你不应该能够压扁不可迭代的东西.这令人困惑,并给出了错误的论点印象.
>>> list(flatten(123))
[123]
>>>
以下生成器几乎与第一个生成器相同,但没有尝试展平不可迭代对象的问题.如果给出不恰当的论点,它会失败.
def flatten(iterable):
for item in iterable:
try:
yield from flatten(item)
except TypeError:
yield item
使用提供的列表测试生成器工作正常.但是,新代码将TypeError在向其提供不可迭代对象时引发.示例显示在新行为的下方.
>>> L = [[[1, 2, 3], [4, 5]], 6]
>>> list(flatten(L))
[1, 2, 3, 4, 5, 6]
>>> list(flatten(123))
Traceback (most recent call last):
File "<pyshell#32>", line 1, in <module>
list(flatten(123))
File "<pyshell#27>", line 2, in flatten
for item in iterable:
TypeError: 'int' object is not iterable
>>>
我更喜欢简单的答案。没有发电机。没有递归或递归限制。只是迭代：
def flatten(TheList):
listIsNested = True
while listIsNested: #outer loop
keepChecking = False
Temp = []
for element in TheList: #inner loop
if isinstance(element,list):
Temp.extend(element)
keepChecking = True
else:
Temp.append(element)
listIsNested = keepChecking #determine if outer loop exits
TheList = Temp[:]
return TheList
这适用于两个列表：内部 for 循环和外部 while 循环。
内部 for 循环遍历列表。如果它找到一个列表元素，它 (1) 使用 list.extend() 将该部分展平为一级嵌套，并且 (2) 将 keepChecking 切换为 True。keepchecking 用于控制外层 while 循环。如果外循环设置为 true，则会触发内循环进行另一遍。
这些传递不断发生，直到找不到更多嵌套列表为止。当最终在没有找到任何内容的情况下发生传递时，keepChecking 永远不会跳到 true，这意味着 listIsNested 保持 false 并且外部 while 循环退出。
然后返回展平的列表。
测试运行
flatten([1,2,3,4,[100,200,300,[1000,2000,3000]]])
[1, 2, 3, 4, 100, 200, 300, 1000, 2000, 3000]
尽管选择了一个优雅且非常Python化的答案，但我仅出于审查目的而提出我的解决方案：
def flat(l):
ret = []
for i in l:
if isinstance(i, list) or isinstance(i, tuple):
ret.extend(flat(i))
else:
ret.append(i)
return ret
请告诉我们这段代码的好坏？
这是一个简单的函数，可以展平任意深度的列表。无递归，避免堆栈溢出。
from copy import deepcopy
def flatten_list(nested_list):
"""Flatten an arbitrarily nested list, without recursion (to avoid
stack overflows). Returns a new list, the original list is unchanged.
>> list(flatten_list([1, 2, 3, [4], [], [[[[[[[[[5]]]]]]]]]]))
[1, 2, 3, 4, 5]
>> list(flatten_list([[1, 2], 3]))
[1, 2, 3]
"""
nested_list = deepcopy(nested_list)
while nested_list:
sublist = nested_list.pop(0)
if isinstance(sublist, list):
nested_list = sublist + nested_list
else:
yield sublist
我没有在这里查看所有已经可用的答案，但这是我想出的一个行，借用了 lisp 的第一个和其余列表处理方式
def flatten(l): return flatten(l[0]) + (flatten(l[1:]) if len(l) > 1 else []) if type(l) is list else [l]
这是一个简单的和一个不那么简单的案例 -
>>> flatten([1,[2,3],4])
[1, 2, 3, 4]
>>> flatten([1, [2, 3], 4, [5, [6, {'name': 'some_name', 'age':30}, 7]], [8, 9, [10, [11, [12, [13, {'some', 'set'}, 14, [15, 'some_string'], 16], 17, 18], 19], 20], 21, 22, [23, 24], 25], 26, 27, 28, 29, 30])
[1, 2, 3, 4, 5, 6, {'age': 30, 'name': 'some_name'}, 7, 8, 9, 10, 11, 12, 13, set(['set', 'some']), 14, 15, 'some_string', 16, 17, 18, 19, 20, 21, 22, 23, 24, 25, 26, 27, 28, 29, 30]
>>>
在尝试回答这样的问题时，您确实需要给出您作为解决方案提出的代码的局限性。如果只是关于性能，我不会太介意，但是作为解决方案提出的大多数代码（包括已接受的答案）都无法展平任何深度大于 1000 的列表。
当我说大多数代码时，我指的是使用任何形式的递归（或调用递归的标准库函数）的所有代码。所有这些代码都失败了，因为对于进行的每个递归调用，（调用）堆栈增长一个单位，并且（默认）python 调用堆栈的大小为 1000。
如果您不太熟悉调用堆栈，那么以下内容可能会有所帮助（否则您可以滚动到Implementation）。
想象一下，您进入一个带有编号房间的巨大地牢，寻找宝藏。你不知道那个地方，但你有一些关于如何找到宝藏的指示。每个迹象都是一个谜（难度各不相同，但你无法预测它们会有多难）。你决定考虑一下节省时间的策略，你有两个观察：
进入地牢时，您会注意到这里有一个小笔记本。你决定用它来写下你解谜后退出的每个房间（进入新房间时），这样你就可以回到入口。这是一个天才的想法，您甚至不会花一分钱来实施您的策略。
你进入地牢，成功解开前 1001 个谜语，但你没有计划的事情来了，你借来的笔记本没有空间了。你决定放弃你的任务，因为你宁愿没有宝藏也不愿永远迷失在地牢里（这看起来确实很聪明）。
基本上，这与寻找宝藏完全相同。地牢是计算机的内存，你现在的目标不是寻找宝藏，而是计算一些函数（为给定的x找到f(x)）。指示只是帮助您解决f(x)的子程序。您的策略与调用堆栈策略相同，笔记本是堆栈，房间是函数的返回地址：
x = ["over here", "am", "I"]
y = sorted(x) # You're about to enter a room named `sorted`, note down the current room address here so you can return back: 0x4004f4 (that room address looks weird)
# Seems like you went back from your quest using the return address 0x4004f4
# Let's see what you've collected
print(' '.join(y))
您在地牢中遇到的问题在这里是相同的，调用堆栈的大小是有限的（这里是 1000），因此，如果您输入太多函数而没有返回，那么您将填充调用堆栈并出现错误就像“亲爱的冒险家，很抱歉，您的笔记本已满”：RecursionError: maximum recursion depth exceeded。请注意，您不需要递归来填充调用堆栈，但非递归程序调用 1000 个函数而不返回的可能性很小。同样重要的是要了解，一旦您从函数返回，调用堆栈就会从使用的地址中释放（因此名称“堆栈”，返回地址在进入函数之前被推入并在返回时被拉出）。在简单递归的特殊情况下（函数f调用它自己一次——一遍又一遍——）你会f一遍又一遍地进入，直到计算完成（直到找到宝藏），然后返回，f直到你回到你f最初调用的地方。调用堆栈将永远不会从任何东西中释放，直到它从一个接一个地从所有返回地址中释放为止。
这实际上非常简单：“如果您不知道递归可以深入多深，请不要使用它”。这并不总是正确的，因为在某些情况下，可以优化尾调用递归 (TCO)。但是在python中，情况并非如此，即使“写得很好”的递归函数也不会优化堆栈使用。Guido 有一篇关于这个问题的有趣帖子：尾递归消除。
有一种技术可用于使任何递归函数迭代，我们可以将这种技术称为自带笔记本。例如，在我们的特定情况下，我们只是在探索一个列表，进入一个房间相当于进入一个子列表，您应该问自己的问题是如何从列表返回到其父列表？答案没那么复杂，重复以下直到stack为空：
address和indexin a推stack入（注意列表地址+索引也是一个地址，因此我们只使用与调用堆栈使用的技术完全相同的技术）；yield它（或将它们添加到列表中）；stack return address(和index)返回到父列表。另请注意，这等效于树中的 DFS，其中一些节点是子列表A = [1, 2]，一些是简单项：（0, 1, 2, 3, 4对于L = [0, [1,2], 3, 4]）。树看起来像这样：
L
|
-------------------
| | | |
0 --A-- 3 4
| |
1 2
DFS 遍历预序是：L, 0, A, 1, 2, 3, 4。请记住，为了实现迭代 DFS，您还“需要”一个堆栈。我之前提出的实现导致具有以下状态（对于stack和flat_list）：
init.: stack=[(L, 0)]
**0**: stack=[(L, 0)], flat_list=[0]
**A**: stack=[(L, 1), (A, 0)], flat_list=[0]
**1**: stack=[(L, 1), (A, 0)], flat_list=[0, 1]
**2**: stack=[(L, 1), (A, 1)], flat_list=[0, 1, 2]
**3**: stack=[(L, 2)], flat_list=[0, 1, 2, 3]
**3**: stack=[(L, 3)], flat_list=[0, 1, 2, 3, 4]
return: stack=[], flat_list=[0, 1, 2, 3, 4]
在此示例中，堆栈最大大小为 2，因为输入列表（以及树）的深度为 2。
对于实现，在 python 中你可以通过使用迭代器而不是简单的列表来简化一点。对（子）迭代器的引用将用于存储子列表返回地址（而不是同时拥有列表地址和索引）。这不是一个很大的区别，但我觉得这更具可读性（也更快一点）：
def flatten(iterable):
return list(items_from(iterable))
def items_from(iterable):
cursor_stack = [iter(iterable)]
while cursor_stack:
sub_iterable = cursor_stack[-1]
try:
item = next(sub_iterable)
except StopIteration: # post-order
cursor_stack.pop()
continue
if is_list_like(item): # pre-order
cursor_stack.append(iter(item))
elif item is not None:
yield item # in-order
def is_list_like(item):
return isinstance(item, list)
另外，请注意，在is_list_likeI have 中isinstance(item, list)，可以对其进行更改以处理更多输入类型，在这里我只想拥有最简单的版本，其中 (iterable) 只是一个列表。但你也可以这样做：
def is_list_like(item):
try:
iter(item)
return not isinstance(item, str) # strings are not lists (hmm...)
except TypeError:
return False
这将字符串视为“简单项目”，因此flatten_iter([["test", "a"], "b])将返回["test", "a", "b"]而不是["t", "e", "s", "t", "a", "b"]。请注意，在这种情况下，iter(item)对每个项目调用两次，让我们假设这是读者的练习，以使它更清晰。
最后，请记住，您不能L使用 using打印无限嵌套列表，print(L)因为它会在内部使用对__repr__( RecursionError: maximum recursion depth exceeded while getting the repr of an object) 的递归调用。出于同样的原因，flatten涉及的解决方案str将失败并显示相同的错误消息。
如果您需要测试您的解决方案，您可以使用此函数生成一个简单的嵌套列表：
def build_deep_list(depth):
"""Returns a list of the form $l_{depth} = [depth-1, l_{depth-1}]$
with $depth > 1$ and $l_0 = [0]$.
"""
sub_list = [0]
for d in range(1, depth):
sub_list = [d, sub_list]
return sub_list
这给出：build_deep_list(5)>>> [4, [3, [2, [1, [0]]]]]。
| 归档时间： |
|
| 查看次数： |
120906 次 |
| 最近记录： |