gpt4 book ai didi

python - 为什么在此实现中递归比迭代更快? (Python 反转链表)

转载 作者:行者123 更新时间:2023-12-01 07:42:13 24 4
gpt4 key购买 nike

我已经解决了"reverse a linked list"迭代和递归都有问题。结果出乎我的意料。我正在使用 leetcode,所以我的迭代版本击败了所有 python3 提交的 27.7%,而我的递归版本击败了 95.97% 的解决方案。我知道这可能是由于尾部调用优化造成的,但我不明白它是怎么回事。有人可以澄清一下吗?

这是我的两种实现的代码:

# Definition for singly-linked list.
# class ListNode:
# def __init__(self, x):
# self.val = x
# self.next = None

#def reverseList(self, head: ListNode) -> ListNode:
#
# prev = None
#
# while head:
# headsNext = head.next
# head.next = prev
# prev = head
# head = headsNext
#
# head = prev
#
# return head

class Solution:
def reverseList(self, head: ListNode, prev = None) -> ListNode:

if not head:
return prev

headsNext = head.next
head.next = prev
prev = head



return self.reverseList(headsNext, prev)

最佳答案

我做了一些性能测试,两个功能非常接近。这可能会使误差范围内的差异下降,并给人一种递归版本更快的印象。

您可以通过减少分配数量来确保迭代版本更快:

def reverseList1( head: ListNode) -> ListNode:            
prev = None
while head:
prev,head.next,head = head,prev,head.next
return prev

即使你在递归函数中做同样的事情:

def reverseList2(head: ListNode, prev = None) -> ListNode:
if not head: return prev
prev,head.next,head = head,prev,head.next
return reverseList2(head, prev)

编辑运行多次性能测试后,结果发现性能差异并不显着。迭代和递归版本有时在每次测试运行时执行得更快或更快。这意味着,考虑到所有版本在给定误差范围的情况下都表现相同,速度得分毫无意义。

关于python - 为什么在此实现中递归比迭代更快? (Python 反转链表),我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/56640075/

24 4 0
Copyright 2021 - 2024 cfsdn All Rights Reserved 蜀ICP备2022000587号
广告合作:1813099741@qq.com 6ren.com