Sunday, 18 September 2016

python - Why is `in range()` so much faster than nested loops? How much faster?

I am doing this problem on HackerRank. I'm not specifically looking for ways to solve the problem better, though of course those are welcome (I wonder if there is some use of the yield keyword here, or something that would let me dynamically bound the portions of range() being compared to y * y).



What I'm really curious about is why one way I solved the problem alleviated a bunch of timeouts, and I think it has to do with the way the in keyword works with range - I am guessing it doesn't just run a loop and compare all elements?



Code that caused all the timeouts:



def squares(a, b):
max_square = int(math.sqrt(b) // 1)
min_square = int(math.sqrt(a) // 1)

counter = 0
for n in range(a, b + 1):
for y in range(min_square, max_square + 1):
if y * y == n:
counter += 1
return counter


Code that alleviated all but one timeout:




def squares(a, b):
max_square = int(math.sqrt(b) // 1)
min_square = int(math.sqrt(a) // 1)
counter = 0
for y in range(min_square, max_square + 1):
if (y * y) in range(a, b + 1):
counter += 1
return counter



After reading a bit about ranges, I decided to try this code, which alleviated all of the timeouts. I take it this is because ranges are something like a hybrid of lists and generators, by creating the range once and saving it as a list I was able to alleviate the re-creation of the range on each check of if? With a simple function like this, I'm frankly surprised that Python would re-generate the same range on each run rather than referring back to the same object; probably I'm missing something here?



def squares(a, b):
max_square = int(math.sqrt(b) // 1)
min_square = int(math.sqrt(a) // 1)
counter = 0
the_range_list = list(range(min_square, max_square + 1))
for y in the_range_list:
if (y * y) in range(a, b + 1):
counter += 1

return counter


I don't know how to benchmark, so if anyone can show me the actual time differences, that would be cool. But really I'd like to know: why is the second version is apparently so much faster?



Testcases:



print(squares(35, 70))
>>> 3
print(squares(100, 1000))

>>> 22
print(squares(3, 9))
>>> 2
print(squares(17, 24))
>>> 0

No comments:

Post a Comment

c++ - Does curly brackets matter for empty constructor?

Those brackets declare an empty, inline constructor. In that case, with them, the constructor does exist, it merely does nothing more than t...