python – starmap is faster than loop operation?

Question:

Here is the code that solves the problem from here:

def maximizingXor(l, r):
    return max([i^j for i in range(l, r+1) for j in range(i, r+1)])

And here is my not so elegant solution using modules:

from itertools import combinations, starmap
from operator import xor

# Complete the maximizingXor function below.
def maximizingXor(l, r):
    return max(starmap(xor, combinations(range(l,r+1),2)))

It is not so beautiful, but it turned out to be faster by l=10, r=15:
%timeit gives 3.81 µs ± 156 ns on my solution and 8.67 µs ± 1.1 µs per loop for solution without functions calling on a solution without modules.

So – a question. Why faster? After all, in theory, the code is the same. And a more general question – in what cases is it more expedient to use modules, and in what cases – to write in the forehead?

I'm confused by the fact that specifically here "in the forehead" is used as if the built-in operation i^j , which, in theory, should have been faster than doing the same, but using the function – the XOR operator. And come on you)

PS: as it turned out, my solution turned out to be a little more "reasonable" than the straightforward one and counts fewer elements. It would be more fair to compare with i+1 instead of i

def maximizingXor(l, r):
    return max([i^j for i in range(l, r+1) for j in range(i+1, r+1)])

however, the improvement was not decisive, namely %timeit gives 6.62 µs ± 83.4 ns

PPS: Well, for the sake of completeness – tuple just add brackets:

def maximizingXor_t(l, r):
    return max(tuple(starmap(xor, combinations(range(l,r+1),2))))

here %timeit gives 4.11 µs ± 77.2 ns . That is, the generator, when thrust into the tuple, slows down …

Answer:

Something confuses me… Namely, that the result of combinations(range(l,r+1),2) and for i in range(l, r+1) for j in range(i, r+1) different. More specifically, the double range variant produces more elements.

Rewrote the algorithm and ran:

from itertools import combinations

l=10
r=15

print(list(combinations(range(l,r+1),2)))
print([x for x in combinations(range(l,r+1),2)])
print([(i, j) for i in range(l, r+1) for j in range(i, r+1)])

Result:

[(10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (11, 12), (11, 13), (11, 14), (11, 15), (12, 13), (12, 14), (12, 15), (13, 14), (13, 15), (14, 15)]
[(10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (11, 12), (11, 13), (11, 14), (11, 15), (12, 13), (12, 14), (12, 15), (13, 14), (13, 15), (14, 15)]
[(10, 10), (10, 11), (10, 12), (10, 13), (10, 14), (10, 15), (11, 11), (11, 12), (11, 13), (11, 14), (11, 15), (12, 12), (12, 13), (12, 14), (12, 15), (13, 13), (13, 14), (13, 15), (14, 14), (14, 15), (15, 15)]

Let's compare the performance of combinations, combinations_with_replacement and nested loop:

from timeit import timeit
NUMBER = 10000

elapsed = timeit("""\
list(combinations(range(l,r+1),2))
""", setup="""
from itertools import combinations
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
list(combinations_with_replacement(range(l,r+1),2))
""", setup="""
from itertools import combinations_with_replacement
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
[x for x in combinations(range(l,r+1),2)]
""", setup="""
from itertools import combinations
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
[x for x in combinations_with_replacement(range(l,r+1),2)]
""", setup="""
from itertools import combinations_with_replacement
l=10
r=15
""", number=NUMBER)
print(elapsed)

elapsed = timeit("""\
[(i, j) for i in range(l, r+1) for j in range(i, r+1)]
""", setup="""
l=10
r=15
""", number=NUMBER)
print(elapsed)

Result:

0.015679950736771395 : list(combinations(range(l,r+1),2))
0.019574358240705608 : [x for x in combinations(range(l,r+1),2)]
0.017971126274343937 : list(combinations_with_replacement(range(l,r+1),2))
0.023044554609408532 : [x for x in combinations_with_replacement(range(l,r+1),2)]
0.04071618284619548  : [(i, j) for i in range(l, r+1) for j in range(i, r+1)]

As seen:

  • combinations generates fewer elements and is faster than combinations_with_replacement .

  • combinations_with_replacement with the same result is faster than a list generator with nested loops

  • The code with a list generator is slower than the same one, but obtained through a call to list : list(...) is faster than [x for x in ...] . However, here the example is not entirely suitable – in such cases, additional actions are performed in the list generator, and not just shifting the value.

Post Views: 5
Scroll to Top