为什么一个算法比另一个算法更快（使用链表添加数字）

Question

我需要帮助理解为什么下面问题的第二个解决方案比第一个运行更快。

该问题来自leetcode。 问题是：

给定两个非空链表，表示两个非负整数。 数字以相反的顺序存储，并且它们的每个节点包含一个数字。 将两个数字相加并将其作为链表返回。 您可以假设这两个数字除了数字0本身外不包含任何前导零。

其中一个解决方案是：

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

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        sum_ = ListNode(0)
        root = sum_
        carry_over = 0

        # O(n of bigger list) - time
        # if there are still numbers to be added in list 1 or list 2, do
        while l1 or l2:
            # if list 1 is not null and has a value
            if l1 and l1.val:
                # add it to our sum ListNode value
                sum_.val += l1.val
            if l2 and l2.val:
                sum_.val += l2.val

            # we might need to carry over the decimal from the previous sum
            sum_.val += carry_over
            # if the new sum is >= 10, then we need to carry over the decimal
            carry_over = np.floor(sum_.val / 10)

            # if carry over is more than zero, we need to just use the remainder. i.e. if 11, then sum at this location is 1; and we carry over 1 forward.
            if carry_over > 0: sum_.val = sum_.val % 10

            # type case from float to int. Why are we in float anyway?
            sum_.val = int(sum_.val)

            l1_next = l1 and l1.next
            l2_next = l2 and l2.next

            # continue, if there are more numbers
            if l1_next or l2_next:
                sum_.next = ListNode(0)
                sum_ = sum_.next
                l1 = l1.next if l1_next else None
                l2 = l2.next if l2_next else None
            # stop here, if no more numbers to add.
            else:
                if carry_over:
                    sum_.next = ListNode(int(carry_over))
                l1, l2 = None, None

        return root

另一个是：

class Solution:
    def addTwoNumbers(self, l1: ListNode, l2: ListNode) -> ListNode:
        # these are array representation of the linked list
        input_1 = []
        input_2 = []

        # loop through all nodes in l1 linked list and add to input_1
        while l1 is not None:
            input_1.append(str(l1.val))
            l1 = l1.next

        while l2 is not None:
            input_2.append(str(l2.val))
            l2 = l2.next

        # this is string numbers from l1 and l2, but in the correct order (not reversed)
        input_1 = "".join(reversed(input_1))
        input_2 = "".join(reversed(input_2))

        # now typecast the strings to integers and add
        out = str(int(input_1) + int(input_2))

        # lastly, create a ListNode with this number to bbe returned
        last = None
        for x in out:
            n = ListNode(x)
            n.next = last
            last = n

        return last

第一个解决方案运行时间约为200毫秒，而第二个解决方案运行时间为100毫秒。我可以看出两者都是O（较大列表的n）。我想第一个运行较慢的原因是因为需要进行floor和modulo操作？最初，我认为第二个会因为需要进行大量字符串类型转换而运行更慢。

- Naz

---

从在线评测或比赛中你不应该学习的一件事是他们命名变量的方式。不要使用一个或两个字母的无描述性名称，而是用能描述其用途的名称来命名它们。此外，要包括注释来描述你的代码，它是做什么的以及为什么要这样做。最后，不要将这些网站作为学习资源，而是作为练习你已经在其他地方学到的东西的方式（例如参加真正的课程）。 - Some programmer dude

1. 同意；
2. 完成；
3. 没有像你说的那样学习和练习。好奇为什么第一个解决方案的性能比第二个差了一倍。

- Naz

你总是可以使用line_profiler。 - roganjosh

@isquared-KeepitReal 当您询问性能时，请包含用于基准测试解决方案的代码。 - a_guest

提交解决方案时，性能将在LeetCode上进行测试。 - Naz

@isquared-KeepitReal 那就没有意义了。如果你不知道正在进行基准测试的内容，那么你就无法讨论它。他们甚至可能包括导入numpy所需的时间，谁知道呢。与性能相关的问题必须在某种程度上是自包含的，即您要同时呈现性能基准测试的方法和结果。即使在这种情况下性能是在某个服务器上完成的，运行自己的性能测试也并不困难。只有当它们显示类似的结果时，您才可以开始进行知情讨论，例如在StackOverflow上。 - a_guest

Answer 1

这两种解决方案的时间复杂度都为 O(max(n,m))，其中n和m是输入链表的长度。

为了找出毫秒级时间差异，我们应该查看每个解决方案中的一些开销。

在第一种解决方案中，您使用了numpy，它需要时间来导入。您可以使用本机的sum_.val // 10，而不是np.floor(sum_.val / 10)。这很可能会显著加快解决方案的速度。

对这一行进行性能评估显示出了显着的速度提升（约为18倍）。在leetcode中还可能存在从导入numpy中产生的开销。

timeit.timeit('np.floor(x / 10)', globals=globals(), number=1000000)
# 0.826268769800663

timeit.timeit('x // 10', globals=globals(), number=1000000)
# 0.04531952366232872

在第二个解决方案中，主要的加速是通过使用"".join()从列表中获取字符串。这是O(n)。如果该解决方案使用字符串连接，我们将看到O(n^2)，因为字符串是不可变的，并且您必须不断将两个字符串复制到一个新字符串中。

差劲字符串连接性能的示例：

input_1 = ""
while l1 is not None:
    input_1 += str(l1.val))
    l1 = l1.next

需要注意的是，leetcode的性能评估会在每次提交时更改。尽管您应该看到第一种解决方案的运行时间在删除numpy使用后有显着改善！

- repoleved

---

字符串拼接技巧，赞！ - Naz