Why is one algorithm faster than the other (adding numbers with linked list)

user_2812237 0
Viewed 104

I need help understanding why the second solution to the below problem runs faster than the first one.

The problem is taken from the leetcode. The problem is:

You are given two non-empty linked lists representing two non-negative integers. The digits are stored in reverse order and each of their nodes contain a single digit. Add the two numbers and return it as a linked list. You may assume the two numbers do not contain any leading zero, except the number 0 itself.

One solution is:

# 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

And the other is:

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

The first solution runs at about 200 ms, while the second at 100ms. I can see that both are O(n of the bigger list). I suppose that the reason why the first one runs slower is due to the floor and modulo operation? Initially, I thought that second would run slower because of the numerous string type conversions.

linked-list python performance
1 Answers

Both solutions are the same time complexity O(max(n,m)) where n and m are the length of the input linked lists.

In order to figure out the ms time difference, we should instead look at some of the overheads in each solution.

In the first solution, you're using numpy, which takes time to import. You could use the native sum_.val // 10 instead of np.floor(sum_.val / 10). This will likely speed up the solution significantly.

Using a performance evaluation on this one line shows a significant speed improvement (~18x). There's probably also overhead from the import of numpy in leetcode.

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

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

In the second solution, the main speed-up here is by using "".join() to get a string from a list. This is O(n). If the solution had used string concatenation instead, we'd be seeing O(n^2) because strings are immutable and you'd have to continuously copy both strings into a new one.

Example of poor str concatenation performance:

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

It's important to note that the leetcode performance evaluation will change on each submission. Although you should see a significant improvement in the runtime of the first solution once removing the use of numpy!

user_71945530
Related