Lazily load files at random from large directory

I have about a million files in my directory, and their number is likely to grow. For machine learning, I would like to randomly sample from those files without replacement. How can I do this very quickly? os.listdir(path) is too slow for me.