Tuesday 28 February 2017

Python 3: How is the look up in a range object faster than a look up in a list?

I was scrolling through a lot of list vs. range related questions on StackOverflow when I came across in one of the answers that look up in a range object is a CONSTANT TIME operation! It doesn't make sense how this can be done in O(1), you're going to have to iterate through the range to see if a number exists. Does the range object work like some hashmap/dictionary?



def usingRange(x):
return x in range(0, 100000000)
print(usingRange(9999999))



def noRange(x):
return x in list(range(0, 100000000))
print(noRange(9999999))

%timeit usingRange(9999999)
%timeit noRange(9999999)


I got the outputs as:




True
True
443 ns ± 8.83 ns per loop (mean ± std. dev. of 7 runs, 1000000 loops each)
6.89 s ± 380 ms per loop (mean ± std. dev. of 7 runs, 1 loop each)


The reason why I want to know why its constant time is because





  1. I was told not to focus so much on learning "tricks" in Python for Programming Interviews! Because everything you do, you will have TO explain the time complexity, so you either memorize that i in list1 is O(N) or you iterate using a for loop over the list:



    for j in range(len(list1)):
    if list1[j] == i:
    print(True)

    else:
    print(False)




and then come to the conclusion that it is, in fact, O(N) because to check if an element existed you go have to iterate over each element of the list till the end of the list (worst case). But some constant time operations seem less obvious! I can live with the fact that a loop in a hash table is O(1) because there is a big concept called Hashing (not gone over it yet), but not sure how it works for range objects.




  1. I was told that it is paramount to know the basics! And do your best to explain every line of what you're writing and why you're writing it in whiteboards. Someone I know was literally ASKED to implement a HASHMAP for an SWE position at a tech VERY FAMOUS company.


  2. I have a LOT of time (1 year) to prepare and be inquisitive about stuff.


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...