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