Sampling a population

[Mitja Trampus]

Brian Quinlan wrote:
> The fastest algorithm that I have been able to devise for doing so is: 
> O(n * log(len(lst))). Can anyone think or a solution with a better time 
> complexity? If not, is there an obviously better way to do this 
> (assuming n is big and the list size is small).


If list is indeed short, I'd say common sense speaks against complicating and optimizing 
further - you can only get log(len(lst))-fold speedup, which is in your case more or less 
a small constant. _IF_ this part of code later turns out to be a bottleneck, you might 
profit more by porting it to C than searching for an O(n) solution, if it even exists.