Currently I have a collection of hundreds of thousands of IDs as integers, and I am performing the following task (lets say this collection is stored in a list cache for now):
cache = list()
# lets say this cache is populated
for x in range(0,1000000):
if x not in cache:
#do_something
How expensive is it for me to use a list to search for not in something? Would I benefit from using another data structure, and if so which one would be best?
You should consider using a set. While it's worst case time complexity for x in cache would still be O(n), the average case is O(1) (source).
If you could create the data in cache via a generator, you could forgo creating a list on the order of 1e5 and reap the memory savings. Then, you could simply test x not in with the following:
desired_id = 123456
cache = some_function_to_generate_integer_ids() # cache is a generator
print desired_id in cache
in which False will be printed if desired_id is not in cache.