BST遍历递归比从

使用使用超矩形搜索的KD树,可以很容易地在google上搜索到它的细节,所以我把它留给您的兴趣。我在搜索与优化区域查询的一部分相关的内容时,遇到了 yield from 语法;因此强调它在尾部递归函数上的使用,因为Python没有优化那些函数。

我用这个语法实现了我的两个遍历函数(其中一个是嵌套的)来做一些测试,结果发现它实际上比递归方法慢,尽管我不确定为什么(但我相信在做了一些快速测试之后,它是嵌套函数的一部分)。

呼叫者:

def search(node, point, eps):
    region = make_region(point, eps)
    return [found 
            for found 
            in range_search(node, region) 
            if sqdist(found, point) <= (eps ** 2)
            ]

外部(递归):

def range_search(node, region, found=None):
    if found is None:
        found = []
    if node.is_leaf():
        found.append(node.value)
    else:
        if region.contains(node.bounds):
            dissolve(node, found)
        elif region.intersects(node.bounds):
            if node.left:
                range_search(node.left, region, found)
            if node.right:
                range_search(node.right, region, found)
    return found

内部(递归):

def dissolve(node, found):
    if not node.is_leaf():
        if node.left:
            dissolve(node.left, found)
        if node.right:
            dissolve(node.right, found)
    else:
        found.append(node.value)

外部(发电机):

def range_search(node, region):
    if node.is_leaf():
        yield node.value
    else:
        if region.contains(node.bounds):
            yield from dissolve(node)
        elif region.intersects(node.bounds):
            yield from range_search(node.left, region) if node.left else ()
            yield from range_search(node.right, region) if node.right else ()

内部(发电机):

def dissolve(node):
    if node:
        yield from dissolve(node.left) if node.left else ()
        if node.is_leaf():
            yield node.value
        yield from dissolve(node.right) if node.right else ()

时间相隔甚远,但我从未想过,如果Python没有针对它进行优化,递归会更慢,但它是针对生成器之类的迭代。

例如,通过 search() 方法通过递归,程序在2.18s内完成,而生成器在2.5s内完成;同样,没有什么剧烈的意外。我是否错误地将函数从递归转换为生成?