Scott, Ricardo, great thoughts and great code. It is an interesting issue with many attack vectors; I hope the OP is getting something out of all this...
I will expect at least as much code and analysis for my next posted problem! ;) SEAN O _________ http://www.sean-o.com http://twitter.com/seanodotcom Scott Sauyet-3 wrote: > > > ricardobeat wrote: >> If you need performance, this should be it: >> >> http://jsbin.com/uvuzi/edit >> >> It sorts the rows using the "Fisher-Yates" shuffling algorithm. >> Despite throwing elements around in an array, it's faster than the >> pure mathematical solution because you don't need to filter out >> duplicate random numbers. An even greater improvement can be made by >> using the style.display property directly. > > First of all, thanks for your code. I learned something new today. I > never realized that I could reassign the elements of a jQuery collection > in that manner. > > I don't know why I brought up performance for a client-side JavaScript > issue! It's probably not at all relevant to the OP's problem. But I > think both your technique and mine should have similar performance. The > key factor in either of ours is the number of calls to Math.random(), > and both of us call that $rows.length times. > > Sean O's technique has a worst-case time that is infinite, but it, or a > slight modification of it [1], has an expected time much shorter than > either of ours. In the ten-out-of-fifty case we were working with, our > techniques require 50 iterations, where in his the expected number of > iterations is 11.033. In your ten-out-of-one-thousand example, ours > would be 1000, and his expected number is below 10.05. With the > modification [1], the worst case would be if the number to be selected > were half of the total rows, and then the number of iterations seems to > be about ln(2) * $rows.length, although I haven't attempted to prove this. > > This is related to the Coupon Collector's Problem [2]. I'm pretty sure > the exact expected number of iterations of Sean's technique is > > sum_{i=1}^{SELECTED} {TOTAL / (TOTAL - i + 1)} > > But hey, let's get back to jQuery! :-) > > -- Scott > > > [1] The modification would be, when the requested number of rows is > greater than half the total number of rows, to switch to running the > same algorithm to choose the number of *unselected* rows. > > [2] http://www.google.com/search?q=coupon+collector+problem > > -- View this message in context: http://www.nabble.com/show-hide-random-rows-tp22570300s27240p22599424.html Sent from the jQuery General Discussion mailing list archive at Nabble.com.
