I did write it myself, mainly because it is trivially simple and O(n).
sub shuffle
{
# Move each element to a random location
my $arrayref = shift;
my $temp;
for (my $i = 0; $i < scalar @$arrayref; $i++)
{
my $r = rand( scalar @$arrayref);
$temp = $arrayref->[$r];
$arrayref->[$r] = $arrayref->[$i];
$arrayref->[$i] = $temp;
}
}
I do recall that day when all the weighted selection questions came out, but this one is somewhat unique in that every item must be selected... it is only the order of selection that needs to be randomized.
PS:
As far as playing the game, work is currently focused on a GUI and a web based auto-host. I'll let you know how it goes. | [reply]
[d/l] |
The fact that you needed to visit each element once is why I think your shuffle-and-shift approach is best, as opposed to the integrated thrust approach which has come up a couple times in this thread. The shuffle out of List:Util will scale the same as your implementation, but will likely have a lower constant and use less memory since it uses map in place of a for loop. I've also gotten admonished on using C-style for loops - maybe swap to for my $i (0 .. $#$arrayref) to reduce the bug risk.
If you do dig the the idea of picking weighted ships in place of the shuffle approach, you can swap it to O(n) (or actually O(n*m^2), where m is # of bins) by sorting and caching bounds, so you don't have to count up each ship. Maybe something like this:
my %shipToActBins = ();
foreach my $ship (@shipsInCombat) {
# Add ship to initiative hash
if (not exists $shipToActBins{$ship->{thruster}}) {
$shipToActBins{$ship->{thruster}} = [];
}
push @{$shipToActBins{$ship->{thruster}}}, $ship;
}
my %weights = ();
for (keys %shipToActBins) {
$weights{$_} = 2 * $_ + 1;
}
SHIP: for (0 .. $#shipsInCombat) {
my $ship;
my $sum = 0;
my @bounds = ();
for (sort keys %shipToActBins) {
if (@{$shipToActBins{$_}} == 0) {
delete ($shipToActBins{$_});
} else {
$sum += $weights{$_}*@{$shipToActBins{$_}};
push @bounds, $sum;
}
}
my $roll = int(rand($sum));
CHOOSE: for (sort keys %shipToActBins) {
if ($bounds[0] >= $roll) {
$roll = int(($bounds[0] - $roll - 1)/$weights{$_});
$ship = splice(@{$shipToActBins{$_}},$roll,1);
last CHOOSE;
} else {
shift @bounds;
}
}
#...
#Simulated mayhem
#...
}
| [reply]
[d/l]
[select] |
As I understand this, for each "round", the weight for every ship is calculated, and then every ship is picked -- at random, biased by weight.
Using a weighted selection, this is O(n^2) in the number of ships. Using your shuffled ballots it's essentially linear in the number of ballots, which is some multiple of the number of ships. The downside of the ballots scheme being that the finer the gradation of ballots, the larger the multiple.
As the number of ships approaches 1,000, O(n^2) may become a pain. The only thing I can think of is a divide and conquer strategy, along the lines below. This code:
includes a "simple" weighted selection implementation. and a "tree" implementation, which for more than 70-odd ships, constructs a form of tree selection structure, which does not slow down so quickly as the number of ships increases. supports weights to any grain, though it uses integer weights internally. Assumes weights are given as floating values, scaling to hundredths for processing. (This scaling is configurable.) allows the weight of ship(s) not yet selected to be adjusted. for 100 ships the tree runs slightly faster; at 200 ships it's nearly twice as fast; at 1,000 it is seven times faster.
That O(n^2) will get you, every time.
| [reply]
[d/l] |