如何加速Python链表的递归调用

Question

我有一个名为min_max的递归函数;它被传递一个链表;它返回一个包含最小值和最大值的2元组。如果链表为空，则min_max返回(None, None)。例如，如果我们将此函数调用为min_max(list_to_ll([1, 3, 7, 2, 0]))，则返回的结果将是(0, 7)。

class LN:
    def __init__(self,value,next=None):
        self.value = value
        self.next  = next
def list_to_ll(l):
    if l == []:
        return None
    front = rear = LN(l[0])
    for v in l[1:]:
        rear.next = LN(v)
        rear = rear.next
    return front

def min_max(ll):
    if ll == None:
        return (None,None)
    else:
        result = (ll.value,ll.value)
        if ll.next != None:
            return (min(result[0],min_max(ll.next)[0]),max(result[1],min_max(ll.next)[1]))
        else:
            return result
if __name__ == '__main__':
    print('nTesting min_max')
    print(min_max(None))
    print(min_max(list_to_ll([0])))
    print(min_max(list_to_ll([7, 3, 5, 2, 0])))
    print(min_max(list_to_ll([1, 3, 5, 2, 7])))
    values = [i for i in range(1,100)]
    print(values)
    print(min_max(list_to_ll(values)))

我的问题是如何加快我的递归调用min_max链表上可能有100个元素?我可以传递与5-7个元素链接的test_case，但与100个元素我的函数是不有效的。谢谢。

Answer 1

目前，这一行:

return (min(result[0],min_max(ll.next)[0]),max(result[1],min_max(ll.next)[1]))

递归地调用min_max 两次以获得最小值和最大值-这意味着您将2**n调用min_max而不是n，这是一个巨大的惩罚。相反,考虑:

min_, max_ = min_max(ll.next) # call once
return min(min_, ll.value), max(max_, ll.value) # use the two values