| deadowl |
05-15-2015 03:43 PM |
Quote:
Posted by Dusty
(Post 566215)
Nah, it plucks a random player from all entrants. It doesn't start at the beginning of any list.
PHP Code:
while (temp.getqueue.size() < temp.plyrcount) {
temp.p = randomstring(this.("event_" @ eventid));
temp.plyr = findplayer(temp.p);
// other stuff
}
|
Question: Why does it dynamically look up this.("event_" @ eventid) every iteration? I'm assuming that it evaluates to an array of account name strings, and the randomstring function selects one of them. The potential for repeats is also an issue. A single pass method where everyone gets equal probability: http://en.wikipedia.org/wiki/Reservoir_sampling.
My GScript skills are a bit rusty, but here's an attempt instead of doing it in some other language (may not be correct):
PHP Code:
// Reservoir Sampling
// ==============
// **pool**: An array from which to draw samples
// **count**: The desired sample size
// returns a sample array with **count** random elements from **pool**
function sample(pool, count) {
temp.sample = {};
for (temp.prospect : pool) {
if (temp.sample.size() < count) {
temp.sample.add(temp.prospect);
} else {
temp.n = random(0, pool.size() - 1);
if (temp.n < count) {
temp.sample[temp.n] = temp.prospect;
}
}
}
return temp.sample;
}
A weighted version of this algorithm is described by this journal article: http://www.sciencedirect.com/science...2001900500298X. Oddly, Graal is older than the algorithms described by the paper.
My Javascript interpretation of that:
PHP Code:
// Weighted Reservoir Sampling
// ==============
// **population**: A population from which to select a sample
// **weights**: A parallel array to population, to specify weight
// **size**: The desired sample size
// returns a sample array with **size** random elements from **population** influenced by **weights**
function sample(population, weights, size) {
var reservoir, keys, key, threshold, i, j;
reservoir = [];
keys = [];
for (i = 0; i < size; i++) {
reservoir[i] = population[i];
keys[i] = Math.pow(Math.random(), 1 / weights[i]);
}
threshold = Math.min.apply(null, keys);
for (i = size; i < population.length; i++) {
key = Math.pow(Math.random(), 1 / weights[i]);
if (key > threshold) {
j = keys.indexOf(threshold);
reservoir[j] = population[i];
keys[j] = key;
threshold = Math.min.apply(null, keys);
}
}
return reservoir;
}
The weighted one should return a purely random sample if you give every item in the population the same weight. Also, weights can't be 0.
Another javascript version I just wrote of the weighted reservoir sampler that wouldn't require keeping track of all of the players that have entered the queue (which was the point of reservoir samplers, but then even with a known pool they were more efficient than alternatives):
Edit: Added documentation to where things line up with the algorithm description in the journal article. You can see I didn't do things in the same order as described, but you should be able to see where I saved some code and added small efficiencies by reordering it.
PHP Code:
// See http://www.sciencedirect.com/science/article/pii/S002001900500298X#
function WeightedReservoirSampler(length) {
this.length = length;
this.sample = [];
this.keys = [];
this.threshold = Infinity;
}
// R is the reservoir, or [this.sample], or what's going to be the end result.
// m is the size of the reservoir, or [this.length].
// V is the input stream of items, which is of indeterminate length.
// n is the end size of the input stream, or the number of items passed in before the sample is complete.
// v_i is an incoming [item].
// w_i is an associated [weight] for the incoming item.
// u_i is a random number in the range of 0-1, or [Math.random()] generated in association with v_i.
// k_i is a [key] calculated for each item based on its weight, w_i, and the random number, u_i.
// T is a threshold, or [this.threshold], that represents the smallest key value.
WeightedReservoirSampler.prototype.push = function (item, weight) {
var key, index;
if (weight <= 0) return;
// 2. For each item in v_i in R: Calculate a key, k_i = u_i^(1/w_i), where u_i = random(0, 1)
// 5. For each item v_i: Calculate a key, k_i = u_i^(1/w_i), where u_i = random(0, 1)
key = Math.pow(Math.random(), 1 / weight);
// 1. The first m items of V are inserted into R
if (this.sample.length < this.length) {
this.sample.push(item);
this.keys.push(key);
// 4. The smallest key in R is the current threshold T
this.threshold = Math.min(this.threshold, key);
// 3. Repeat steps 4-7 for i = m+1, m+2, ..., n
// 6. If the key k_i is larger than T, then:
} else if (key > this.threshold) {
// 7. The item with the minimum key in R is replaced by item v_i
index = this.keys.indexOf(this.threshold);
this.sample[index] = item;
this.keys[index] = key;
// 4. The smallest key in R is the current threshold T
this.threshold = Math.min.apply(null, this.keys);
}
}
WeightedReservoirSampler.prototype.flush = function () {
var result = this.sample;
this.sample = [];
this.keys = [];
this.threshold = Infinity;
return result;
}
|
