Why is append() slower than + and is there some oversight in the map() solution which slows it down?

Question

I was trying out some variation in implementation of a leetcode example and was surprised by the runtimes. I was expecting it would be better to use map() than classic grandpa style for-loop

In short the problem is to find if a value in the list is smaller or larger than a threshold value

https://leetcode.com/problems/kids-with-the-greatest-number-of-candies/submissions/

Here are the three implementations:

72 ms 13.8 MB

Map over the input list and generate the list of bool

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:

        m=max(candies)-extraCandies
        return list(map( lambda x: x>=m, candies))

40 ms 14 MB

For-loop and append() to list

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:

        m=max(candies)-extraCandies
        ans=[]
        for x in candies:
            ans.append(x>=m)
        return ans

28 ms 13.6 MB

Use + to append to list

class Solution:
    def kidsWithCandies(self, candies: List[int], extraCandies: int) -> List[bool]:

        m=max(candies)-extraCandies
        ans=[]
        for x in candies:
            ans+=[(x>=m)]
        return ans

Why is append() slower than + and is there some oversight in the map() solution which slows it down?

Answer 1

You ask whether there is an oversight in the map solution, slowing it down. There is, in the form of lambda. When passing lambda objects, map is slowed down, as shown here. Passing proper function objects does not have the same restrictions.

Other than that, I was unable to confirm the large performance discrepancy you found between append (40ms) and __iadd__/+= (28ms). In the below tests, append is faster than += by (just) about 2 percent. That is negligible.

Below, five versions of your function are tested. Next to kidsWithCandies_map_builtin, which uses the ge function of the operator module to get a callable ge(a, b) that returns the same as a >= b, the arguably most Pythonic approach is also tested, list comprehension.

from collections import defaultdict, namedtuple
from operator import ge
from pprint import pprint as pp
from timeit import timeit
from typing import List

candy_distribution = namedtuple(
    "CandyDistribution", ["candies", "extra_candies", "solution"]
)

candy_distributions = [
    candy_distribution([2, 3, 5, 1, 3], 3, [True, True, True, False, True]),
    candy_distribution([4, 2, 1, 1, 2], 1, [True, False, False, False, False]),
    candy_distribution([12, 1, 12], 10, [True, False, True]),
]


def kidsWithCandies_map_lambda(candies: List[int], extraCandies: int) -> List[bool]:

    threshold = max(candies) - extraCandies
    return list(map(lambda x: x >= threshold, candies))


def kidsWithCandies_map_builtin(candies: List[int], extraCandies: int) -> List[bool]:

    threshold = max(candies) - extraCandies
    thresholds = [threshold] * len(candies)
    return list(map(ge, candies, thresholds))


def kidsWithCandies_append(candies: List[int], extraCandies: int) -> List[bool]:

    threshold = max(candies) - extraCandies
    ans = []
    for x in candies:
        ans.append(x >= threshold)
    return ans


def kidsWithCandies_iadd(candies: List[int], extraCandies: int) -> List[bool]:

    threshold = max(candies) - extraCandies
    ans = []
    for x in candies:
        ans += [(x >= threshold)]
    return ans


def kidsWithCandies_comprehension(candies: List[int], extraCandies: int) -> List[bool]:

    threshold = max(candies) - extraCandies
    return [element >= threshold for element in candies]


functions_to_runtimes = defaultdict(int)


for func in (
    kidsWithCandies_map_lambda,
    kidsWithCandies_map_builtin,
    kidsWithCandies_append,
    kidsWithCandies_iadd,
    kidsWithCandies_comprehension,
):
    for candy_supply in candy_distributions:
        args = (candy_supply.candies, candy_supply.extra_candies)
        assert candy_supply.solution == func(*args)
        functions_to_runtimes[func.__name__] += timeit("func(*args)", globals=globals())

functions_to_runtimes = {  # sort by value, ascending
    k: v for k, v in sorted(functions_to_runtimes.items(), key=lambda item: item[1])
}

pp(functions_to_runtimes)

with an output of

{'kidsWithCandies_append': 2.2671058810083196,
 'kidsWithCandies_comprehension': 2.3766544990066905,
 'kidsWithCandies_iadd': 2.3180257579660974,
 'kidsWithCandies_map_builtin': 2.9652103499975055,
 'kidsWithCandies_map_lambda': 3.658640267996816}

So while there is not much of a difference between append, comprehension and in-place addition (+=), map is much improved by not using a lambda.

The most non-grandpa style approach is the list comprehension. map was even originally supposed to be dropped from Python 3; as such (but this is speculation), one can suspect that all the performance love and care went towards (list) comprehensions, append and +=. Others have tried here, but map, as a built-in, seems hard to introspect.

I omitted space complexity considerations because these seem similar for all approaches.