1

我需要展平一些嵌套列表。写完 flatten 函数后，我自然是想看看有多少种方法可以破解它。我终于通过 pypy 运行它，很高兴地发现当列表变得非常深时，pypy 的运行速度明显快于 cpython。

但是，我看到一个奇怪的情况，一个更大、更复杂的列表、更多种类的元素的测试实际上比“更简单”的列表执行得更快。

元素较少的测试 1 的运行速度始终比测试 2 慢大约一秒（使用时间 pypy ./script.py）。

def flatten(lol):
    if not any([isinstance(i, list) for i in lol]):
        return lol

    flatter = [i for i in lol if not isinstance(i, list)]
    for sublist in lol:
        if isinstance(sublist, list):
            flatter.extend(sublist)
    return flatten(flatter)

def silly(l):
    return [l, [l]]

nested_function = [["kaplutis", ["mucus", ["my brain", ["is","filled",["with",["pus",]]]]]], "santa gertrudis",[[[[["innermost",flatten(["in", "func"])]]]]]]

tuples = ["empty tuple retained-->", (), ("2-tuple not flattened",), ("I'm the only thing in this tuple")]

dicts = [{"hip": "hop", "ster": "toad"}]

lone_dict = {"lone": 1, "dict": 2}

silly_list = ["1"]
for i in range(20):
    silly_list = silly(silly_list)

# test 1 - only the absurdly nested list
print(len(flatten(silly_list)))

# test 2 - absurdly nested list, with 
lol = [nested_function, tuples, dicts, lone_dict, silly_list]
print(len(flatten(lol)))

我唯一能想到的是，当 JIT 在第二个测试中处理“silly_list”之前的更简单的嵌套列表时，我遇到了一些意外的优化。

4

2 回答 2

1

这个特殊的 flatten 函数确实在 cpython 和 pypy 中遇到了各种不好的性能点

我们前段时间在 irc 上发现了它，修复是创建一个完全不同的 flatten 函数，它在 cpython 中更快，在 pypy 上更快

我不记得网址了，如果 OP 能提供就好了

基本代码是

def flatten(items, akk=None)
 if akk is None:
   akk  = []
 for item in items:
   if isinstance(item, list):
     flatten(item, akk)
   else:
     akk.append(item)
于 2012-08-24T08:07:33.637 回答
0

包含代码的答案而不是评论

很难理解你的代码做了什么。确保它是正确的。后期优化。您可以针对以下内容测试结果：

def flatten(lst, nonscalar_types=list):
    for x in lst:
        if isinstance(x, nonscalar_types):
            yield from flatten(x) # pep 380
        else:
            yield x # non-list type

例子

print(sum(1 for _ in flatten(lol)))
于 2012-06-20T20:17:39.733 回答