惯用的 Python：传播产量还是压平序列？

发布于 2024-10-07 11:16:36 字数 779 浏览 8 评论 0原文

我正在编写一个 ~~breadth~~ 深度优先树遍历函数，我想要做的是：

def traverse(node):
    yield node
    for n in node.children:
        yield_all traverse(n) # << if Python had a yield_all statement

这个想法是最终得到树中的节点的（平坦）序列。

方法#1：（传播产量）

def traverse(node):
    yield node
    for n in node.children:
        for m in traverse(n):
            yield m

方法#2：（展平序列）

def traverse(node):
    return itertools.chain([node],*(traverse(n) for n in node.children))

第一种方法看起来更干净，但我觉得在每个级别显式yield子树中的每个节点很奇怪。

第二种方法很简洁，有点脏，但它符合我在 Haskell 中编写的内容：

traverse node = node : concatMap traverse (children node)

所以我的问题是：哪个更好？或者我错过了最好的第三个选择？

原文

I'm writing a ~~breadth~~ depth-first tree traversal function, and what I want to do is this:

def traverse(node):
    yield node
    for n in node.children:
        yield_all traverse(n) # << if Python had a yield_all statement

The idea is to end up with a (flat) sequence of nodes in the tree.

Approach #1: (propagating yields)

def traverse(node):
    yield node
    for n in node.children:
        for m in traverse(n):
            yield m

Approach #2: (flattening sequences)

def traverse(node):
    return itertools.chain([node],*(traverse(n) for n in node.children))

The first approach seems more clean, but I feel weird explicitly yielding each node in the subtree at each level.

The second approach is terse and slightly dirty, but it matches what I would write in Haskell:

traverse node = node : concatMap traverse (children node)

So my question is: Which is better? Or am I missing a best 3rd option?

分享到QQ

分享到微博

如果你对这篇内容有疑问，欢迎到本站社区发帖提问参与讨论，获取更多帮助，或者扫码二维码加入 Web 技术交流群。

发布评论

需要登录才能够评论，你可以免费注册一个本站的账号。

梦里梦着梦中梦 2024-10-14 11:16:36

[更新]参见PEP-380，这个yield all 语法从 Python 3.3 开始可用，如下所示产量：

def traverse(node):
    yield node
    for n in node.children:
        yield from traverse(n)

[UPDATE] See PEP-380, this yield all syntax is available starting from Python 3.3 as yield from:

def traverse(node):
    yield node
    for n in node.children:
        yield from traverse(n)

回复收藏 0 原文

来日方长 2024-10-14 11:16:36

我会先去。几次后你就会超过传播产量。 :-)

回复收藏 0 原文

天气好吗我好吗 2024-10-14 11:16:36

这是一个意见问题，所以所有的答案都只是价值判断。但据我所知，没有优雅的第三种方法。

我的观点是，第一种方式毫无疑问会获胜。它更清晰、更容易阅读——Python 不是 Haskell，尽管它可以做一些函数式的事情，而且通常函数式方法看起来并不那么整洁。

回复收藏 0 原文

℉服软 2024-10-14 11:16:36

遍历节点位置：

def iter_tree(t, i=0, j=0):
    yield (i, j), t
    for j, n in enumerate(t.children):
        yield from iter_tree(n, i + 1, j)

for (i, j), n in iter_tree(t):
    print(i*'    ', (i, j), n)

Traversing with node position:

def iter_tree(t, i=0, j=0):
    yield (i, j), t
    for j, n in enumerate(t.children):
        yield from iter_tree(n, i + 1, j)

for (i, j), n in iter_tree(t):
    print(i*'    ', (i, j), n)

回复收藏 0 原文

~没有更多了~