17

所以我在 Python 中编写了一个简单的二叉树并遇到了 [...]

我不认为这与 Ellipsis 对象有关,它似乎与无限循环有关(由于 Python 的浅拷贝?)。但是,这个无限循环的来源以及为什么在访问时扩展时它没有得到扩展是我完全不知道的

>>> a
[[[[[], [], 8, 3], [[], [], 3, 2], 6, 3], [], 1, 4], [[], [], -4, 2], 0, 0]
>>> Keys(a)#With a+b
[0, 1, 6, 8, 3, -4]
>>> Keys(a)#With [a,b]
[8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...]]
>>> Keys(a)[1]#??
[8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...], 8, [...], [...], 3, [...], [...], 6, [...], [...], 1, [...], [...], -4, [...], [...], 0, [...], [...]]

使用 a+b 的版本

def Keys(x,y=[]):
    if len(x):y+=[x[2]]+Keys(x[0],y)+Keys(x[1],y)#Though it seems I was using y=y[:]+, this actually outputs an ugly mess
    return y

使用 [a,b] 的版本

def Keys(x,y=[]):
    if len(x):y+=[x[2],Keys(x[0],y),Keys(x[1],y)]
    return y

那么究竟是什么[...]?

4

9 回答 9

25

It can also appear if you have a circular structure with a list pointing to itself. Like this:

>>> a = [1,2]
>>> a.append(a)
>>> a
[1, 2, [...]]
>>> 

Since python can't print out the structure (it would be an infinite loop) it uses the ellipsis to show that there is recursion in the structure.


I'm not quite sure if the question was what what going on or how to fix it, but I'll try to correct the functions above.

In both of them, you first make two recursive calls, which add data to the list y, and then AGAIN append the returned data to y. This means the same data will be present several times in the result.

Either just collect all the data without adding to any y, with something like

return [x[2]]+keys(x[0])+keys(x[1])

or just do the appending in the calls, with something like

y += [x[2]]
keys(x[0], y) #Add left children to y...
keys(x[1], y) #Add right children to y...
return y

(Of course, both these snippets need handling for empty lists etc)

@Abgan also noted that you really don't want y=[] in the initializer.

于 2008-12-29T03:02:35.953 回答
6

I believe, that your 'tree' contains itself, therefore it contains cycles.

Try this code:

   a = [1,2,3,4]
   print a
   a.append(a)
   print a

The first print outputs:

  [1,2,3,4]

while the second:

  [1,2,3,4, [...]]
 

The reason is using

 def Keys(x,y=[]):
 
This is wrong and evil. List is a mutable object, and when used as a default parameter, it is preserved between function calls. So each y += "anything" operation adds to the same list (in all function calls, and since the function is recursive...)


See the Effbot or Devshed for more details on mutable objects passed as default values for functions.

于 2008-12-29T03:08:33.070 回答
5

I don't understand your code above, but the [...] I think is the Python interpreter skipping infinite data structures. For example:

>>> a = [0, 1]
>>> a[0] = a
>>> a
[[...], 1]

It looks like your tree structure is becoming looped.

The answers about slice objects are beside the point.

于 2008-12-29T03:03:22.253 回答
4

I don't believe this to be related to the Ellipsis object, more it seems to have something to do with an infinity loop (due to Python's shallow copy?). The source of this infinity loop and why it doesn't get expanded while expanding when accessed is something I'm completely lost to, however

Look at the following code:

>>> a = [0]
>>> a.append(a)
>>> print a
[0, [...]]

How is Python supposed to print a? It is a list that contains a zero and a reference to itself. Hence it is a list that contains a zero and a reference to a list

[0, [...]]

which in turn contains a zero and a reference to a list

[0, [0, [...]]]

which in turn contains a zero and a reference to a list, and so on, recursively:

[0, [0, [0, [...]]]]
[0, [0, [0, [0, [...]]]]]
[0, [0, [0, [0, [0, [...]]]]]]
...

There is nothing wrong with the recursive data structure itself. The only problem is that it cannot be displayed, for this would imply an infinite recursion. Hence Python stops at the first recursion step and deals with the infinity issue printing only the ellipsis, as was pointed out in previous answers.

于 2008-12-29T03:15:38.203 回答
4

如果您使用 PrettyPrinter,输出将是不言自明的

>>> l = [1,2,3,4]
>>> l[0]=l
>>> l
[[...], 2, 3, 4]
>>> pp = pprint.PrettyPrinter(indent = 4)
>>> pp.pprint(l)
[<Recursion on list with id=70327632>, 2, 3, 4]
>>> id(l)
70327632

换句话说,它就像

在此处输入图像描述

于 2013-03-10T17:47:02.917 回答
2

编辑:如上所述,这不是 Ellipsis 对象,而是循环列表的结果。我在这里开枪了。如果您在一些实际代码中而不是输出中找到省略号,那么了解省略号对象是一个很好的后置知识。


Python 中的 Ellipsis 对象用于扩展切片表示法。它没有在当前的 Python 核心库中使用,但可供开发人员在自己的库中定义。例如,NumPy(或 SciPy)使用 this 作为其数组对象的一部分。您需要查看 tree() 的文档以准确了解 Ellipsis 在此对象中的行为方式。

来自Python 文档

3.11.8 省略号对象

此对象由扩展切片表示法使用(请参阅 Python 参考手册)。它不支持特殊操作。只有一个省略号对象,名为 Ellipsis(内置名称)。

它被写为省略号。

于 2008-12-29T02:56:36.480 回答
1

Ok, so in points:

  1. You're creating infinite data structure:

    def Keys(x,y=[])
    will use the same 'y' in each call. This just isn't correct.

  2. The print statement, however, is clever enough not to print an infinite data, but to mark self-reference with a [...] (known as Ellipsis)

  3. The Python will allow you to address such structure correctly, so you can write
    a.keys()[1][1][1]
    and so on. Why shouldn't you?
  4. The y = y[:] statement simply copies the list y. Can be done more soundly with y = list(y)

Try using the following code:

def Keys(x,y=None):
    if y is None:
        y = []
    if len(x):
        y += [x[2], Keys(x[0],y), Keys(x[1],y)]
    return y

But still I guess that it can bite you. You're still using the same variable y (I mean the same object) in three places in one expression:

 y += [x[2], Keys(x[0], y), Keys(x[1], y)] 

Is that what you really want to achieve? Or maybe you should try:

def mKeys(x,y=None):
    if y is None:
        y = []
    if len(x):
       z = [x[2], mKeys(x[0], y), mKeys(x[1],y)]
       return z
   return []
于 2008-12-29T03:46:18.393 回答
1

对于两个版本的功能 Keys 的区别,请注意以下区别:

y+=[x[2]]+Keys(x[0],y)+Keys(x[1],y)

该语句右侧的值是一个列表,其中包含 x[2],加上 ELEMENTS OF Keys(x[0],y) 和 ELEMENTS OF Keys(x[1],y)

y+=[x[2],Keys(x[0],y),Keys(x[1],y)]

该语句右侧的值是一个包含 x[2]、加上 LIST Keys(x[2],y) 和 LIST Keys(x[1],y) 的列表。

所以使用 [a,b] 的版本会导致 y 包含它自己作为它的元素。

其他一些注意事项:

  1. 由于在 python 中,默认值对象在定义函数时创建一次,所以第一个版本不会像示例所示那样工作。它将包含一些密钥的多个副本。简而言之很难解释,但是您可以通过在每次调用 Keys 时打印 x、y 的值来获得一些想法。

    这可以通过在我的机器上使用 python 2.5.2 运行该函数来确认。

  2. 另外因为默认值在函数定义时只定义一次,即使函数第一次正常工作,当用不同的 a 调用时它也不会工作,因为第一个二叉树中的键将保留在 y 中。

    您可以通过两次调用 Keys(a) 或在两个不同的列表上调用它来看到这一点。

  3. 此问题不需要第二个参数。函数可以是这样的:

    def Keys(a): if a = []: return [] else: return [a[2]]+Keys(a[0])+Keys(a[1])

    定义一个递归函数基本上包含两部分,解决子问题和合并结果。在您的代码中,组合结果部分重复了两次:一次通过将它们累积在 y 中,一次通过将列表相加。

于 2008-12-29T06:20:54.913 回答
1

问题是因为列表元素之一正在引用列表本身。因此,如果尝试打印所有元素,那么它将永远不会结束。

插图:

x = range(3)
x.append(x)
x[3][3][3][3][3][0] = 5
print x

输出:

[5, 1, 2, [...]]

x[3]是指x自己。也一样x[3][3]

这可以在 这里更好地可视化

于 2016-07-23T16:35:28.607 回答