An Efficient Method for Weighted Sampling without Replacement
Chee Kuan Wong, Malcolm C. Easton · SIAM Journal on Computing · 1980
In this note, an efficient method for weighted sampling of K objects without replacement from a population of n objects is proposed. The method requires $O(K\log n)$ additions and comparisons, and $O(K)$ multiplications and random number generations while the method proposed by Fagin and Price requires $O(Kn)$ additions and comparisons, and $O(K)$ divisions and random number generations.