Почему один алгоритм быстрее другого (добавление чисел со связанным списком)

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 из большего списка). Я полагаю, что причина того, почему первый работает медленнее, связана с полом и операцией по модулю? Сначала я думал, что секунда будет работать медленнее из-за многочисленных преобразований строковых типов.

Answer 1

Оба решения имеют одинаковую сложность по времени O(max(n,m)), где n и m - это длина связанных входных списков.

Чтобы выяснить разницу во времени мс, мы должны вместо этого посмотретьна некоторые накладные расходы в каждом решении.

В первом решении вы используете numpy, для импорта которого требуется время. Вы можете использовать нативный sum_.val // 10 вместо np.floor(sum_.val / 10). Это, вероятно, значительно ускорит решение.

Использование оценки производительности в этой строке показывает значительное улучшение скорости (~ 18x). Вероятно, есть также издержки при импорте numy в leetcode.

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!