0

Why do just writing the code in different order or style, changes the overall runtime?

For eg:

Why is result += "1" is more faster than result = "1" + result ?

More detailed example:

After writing a successful program for this Leetcode problem - Add Binary

here I have 2 code snippets both SAME, but a very subtle difference.

CODE 1

def addBinary(a, b):
    max_len = max(len(a), len(b))
    a = a.zfill(max_len)
    b = b.zfill(max_len)

    result = ""
    carry = 0

    for i in range(len(a)-1, -1, -1):
        x = int(a[i])
        y = int(b[i])

        _sum = x + y + carry

        if _sum == 3:
            result += "1"
            carry = 1
        elif _sum == 2:
            result += "0"
            carry = 1
        elif _sum == 1:
            result += "1"
            carry = 0
        else:
            result += "0"
            carry = 0

    if carry == 1:
        result += "1"

    return result[::-1]

CODE 2

def addBinary(a, b):
    max_len = max(len(a), len(b))
    a = a.zfill(max_len)
    b = b.zfill(max_len)

    result = ""
    carry = 0

    for i in range(len(a)-1, -1, -1):
        x = int(a[i])
        y = int(b[i])

        _sum = x + y + carry

        if _sum == 3:
            result = "1" + result
            carry = 1
        elif _sum == 2:
            result = "0" + result
            carry = 1
        elif _sum == 1:
            result = "1" + result
            carry = 0
        else:
            result = "0" + result
            carry = 0

    if carry == 1:
        result += "1"

    return result

The runtime for CODE 1 is 16 ms, and the runtime for CODE 2 is 47 ms. Why?

Evg
  • 25,259
  • 5
  • 41
  • 83
Vaibhav Shukla
  • 66
  • 1
  • 9
  • 1
    Check out [this](https://stackoverflow.com/questions/15376509/when-is-i-x-different-from-i-i-x-in-python) question – 0x263A Jan 27 '22 at 21:09

1 Answers1

0

Adding characters to the end is optimised internally to reuse the same string (array of characters) in memory. Adding at the beginning requires creating a new string, with the position of each character shifted.

Alex Hall
  • 34,833
  • 5
  • 57
  • 89
  • hmm, that explains. very silly to ask but... are there any resources/places where we can learn these CORE basics of programming – Vaibhav Shukla Jan 27 '22 at 21:15
  • 1
    @VaibhavShukla this is an obscure CPython implementation detail, not a core basic. Something similar is how `list.append` is faster than `list.insert(0, ...)`, although a `deque` is able to have similar performance on both ends. If you want to learn more about this, look into data structures and algorithms. – Alex Hall Jan 27 '22 at 21:26