从树递归中返回值列表

Question

从树递归中返回值列表

3

我正在自学数据结构，并在Python中实现k-d树。我有一个方法可以搜索在我的k-d树类中距离某一点一定半径范围内的点：

def within_radius(self, point, radius, result=[]):
    """
    Find all items in the tree within radius of point
    """
    d = self.discriminator

    if in_circle(point, radius, self.data):
        result.append(self.data)

    # Check whether any of the points in the subtrees could be
    # within the circle
    if point[d] - radius < self.data[d] and self.l_child:
        result.append(self.l_child.within_radius(point, radius, result))

    if point[d] + radius > self.data[d] and self.r_child:
        result.append(self.r_child.within_radius(point, radius, result))

    return result

它可以工作，但它返回的列表相当奇怪，其中包含来自使用 result 的递归调用的重复值。有什么好的方法可以将树递归返回的值“累积”到一个列表中吗？我已经思考了一段时间，但实在看不出来。

- muskrat

你可以使用本地结果代替每次传递的值，但仍需将该本地值返回... - Inbar Rose

3个回答

2

我同意mgilson的分析。list是可变类型，list.append是原地操作。这就是它的含义：

有两种类型：可变和不可变。

可变类型在内存中占据相同的位置，即使您更改了它。例如，list和dict是可变类型。这意味着如果您创建了一个名为“myList”的list并以某些方式更改它，则它仍将位于内存中的相同位置。因此，假设您创建了一个在内存位置0x9000的list。然后，执行myList.append(0)不会更改myList在内存中的位置。即使您执行了myList[0] = 'a'，位置也不会改变-它仍将位于0x9000。

当您尝试以任何方式更改不可变类型时，它将“移动”到不同的内存位置。str和tuple是不可变的。这就是为什么您会收到以下错误的原因：

>>> s = 'as'
>>> s[0] = 'b'
Traceback (most recent call last):
  File "<stdin>", line 1, in <module>
TypeError: 'str' object does not support item assignment

这意味着即使您定义了s ='as'（假设s现在位于内存地址0x5000），并将其重新定义为s ='af'，s在内存中的位置也会发生变化。

现在，当您重新分配可变类型时，它在内存中的位置会发生变化。例如，

L = [1,2,3] # 假设内存位置为0x4000 L = [5,6,7] # 内存位置不再是0x4000

这就是“list.append是原地操作”的属性发挥作用的地方。 “list.append是原地操作”表示新元素被添加到列表中而不创建新列表。这就是为什么list.append没有返回值的原因，如下所示：

>>> L = [1,2,3]
>>> ret = L.append(4)
>>> print L
[1, 2, 3, 4]
>>> print ret
None

然而，如果您想创建一个新列表，可以按照以下步骤进行：

>>> L = [1,2,3]
>>> ret = L + [4]
>>> print L
[1, 2, 3]
>>> print ret
[1, 2, 3, 4]

在你的情况下，左右两个递归调用中都将point添加到列表中。这就是为什么会出现重复值的原因。

你可以采用mgilson建议的方法来解决这个问题，或者如果你是Lisp的粉丝（这是一个非常好的Lisp问题），那么你可以使用[1,2,3]+[4]原则，像这样做（未经测试，但应该可以工作）：

def within_radius(self, point, radius, result=[]):
    """
    Find all items in the tree within radius of point
    """
    d = self.discriminator

    temp = []

    if in_circle(point, radius, self.data):
        temp = [self.data]

    # Check whether any of the points in the subtrees could be
    # within the circle
    if point[d] - radius < self.data[d] and self.l_child:
        temp += self.l_child.within_radius(point, radius, result)

    if point[d] + radius > self.data[d] and self.r_child:
        temp += self.r_child.within_radius(point, radius, result)

    return result+temp

希望这能帮到您。

- inspectorG4dget

1

以下是一些想法：

如果您想返回唯一的结果，您应该使用一个集合，并在返回时将其转换为列表。唯一的问题是，self.data必须是不可变的，例如元组而不是列表。
因为您正在通过递归线程result并将递归调用的结果添加到其中，所以您明确地将每个命中至少两次添加到结果中。通过递归线程结果，可以避免创建和丢弃数据结构，因此您可能只需这样做。
正如mgilson指出的那样，由于Python处理默认参数的方式，将result设置为空列表在函数声明中不会产生您想要的效果。每次调用within_radius而没有显式传递result时，命中将累积每个调用的结果，而不仅仅是单个调用的结果。（有意义吗？请参见this）。mgilson的答案也指出了这一点。

考虑到所有这些，我可能会这样做：

def within_radius(self, point, radius, result=None):
    d = self.discriminator

    result = set() if result is None else result

    if in_circle(point, radius, self.data):
        result.add(self.data)
    if point[d] - radius < self.data[d] and self.l_child:
        self.l_child.within_radius(point, radius, result)
    if point[d] + radius > self.data[d] and self.r_child:
        self.r_child.within_radius(point, radius, result)

    return list(result)

- Eric

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- mgilson · Accepted Answer

我不确定这是否是最干净的方法，但每当我像这样进行递归时，我经常添加一个关键字参数，它是要返回的列表。这样，当我修改列表时，我总是修改同一个列表：

def recurse(max, _output=None):
    if _output is None:
        _output = []

    #do some work here, add to your list
    _output.append(max)

    if max <= 0: #Some condition where the recursion stops
        return _output
    else:        #recurse with new arguments so that we'll stop someday...
        return recurse(max-1, _output=_output)

这个方法的实现是因为当停止条件True时，_output列表被返回并传递回整个函数调用栈。

我使用下划线变量名来表示它只能在函数内部使用。这是对下划线前缀变量通常用于类中表示变量是“私有”的轻微扩展，但我认为它可以表达出要点...

请注意，这与您拥有的内容并没有太大区别。 但是，使用您的版本，result将会在调用之间保持存在，因为result = []在函数创建时就已经被计算了。此外，您的版本正在附加返回值（即列表本身）。当您考虑到列表保存多个对自身的引用时，这变得非常复杂...