[Python] Python list Get Item not O(1)?

I am trying to optimize a piece of code and I saw a lot of time spent into picking a random index out of a list.

Using the following timeit, I am seeing that Get Item against a larger list can take ~3x longer, while generating the random index is constant time:

import timeit
setup = f"""
import random
test_10m = [x for x in range(10000000)]
test_1m = [x for x in range(1000000)]
test_10k = [x for x in range(10000)]
test_1k = [x for x in range(1000)]
"""

print(timeit.timeit('test_10m[int(random.random()*10000000)]', number=1000000, setup=setup))
print(timeit.timeit('test_1m[int(random.random()*1000000)]', number=1000000, setup=setup))
print(timeit.timeit('test_10k[int(random.random()*10000)]', number=1000000, setup=setup))
print(timeit.timeit('test_1k[int(random.random()*1000)]', number=1000000, setup=setup))
print(timeit.timeit('int(random.random()*10000000)', number=1000000, setup=setup))
print(timeit.timeit('int(random.random()*1000000)', number=1000000, setup=setup))
print(timeit.timeit('int(random.random()*10000)', number=1000000, setup=setup))
print(timeit.timeit('int(random.random()*1000)', number=1000000, setup=setup))


Example output (Python 3.8.6):

0.7138307300047018
0.5209437379962765
0.2407058280077763
0.22641731501789764

0.21460772102000192
0.21099105197936296
0.20940051099751145
0.21421014302177355


I am getting similar results in Python 3.9.21.

Questions:

• 
  How does the wiki claim O(1) for Get Item? Ie. What am I missing?
  
  
• 
  Is there a faster way to get a random value out of a large list (large>=100000 for now)
  

Continue reading...