>>> random.sample(xrange(0, 1000000000), 5) [5258132, 23096612, 43529214, 91062733, 4912658] This ran in a few milliseconds on my old macbook in python. It

>>> random.sample(xrange(0, 1000000000), 5) [5258132, 23096612, 43529214, 91062733, 4912658] This ran in a few milliseconds on my old macbook in python. It is an iterator over 1 billion element list. Looking at the source, they seem to track previous selections for large populations in a set, for which lookup of "x in y" is avg O(1). https://svn.python.org/projects/python/tags/r32/Lib/random.py https://svn.python.org/projects/python/tags/r32/Lib/random.p...