# Weighted choices

Is there a more efficient way to do the below without two for loops in actionscript 3? In java there is NavigableMap or something like that where dont need to loop.

var treasureItemsWeights:Object = { "1" : 5 , "2" : 20, "3" : 400, "4" : 60, "5" : 20,
"6" : 20 ,  "7" : 20 ,  "8" : 20 ,  "9" : 20} ;

function chooseTreasureItem():String
{
var total = 0;
for (var key:String in treasureItemsWeights)
{
total += treasureItemsWeights[key];
}
var num:Number = Math.floor(Math.random() * (total+1));
total = 0;
for (var key:String in treasureItemsWeights)
{
total += treasureItemsWeights[key];
if (num<=total)
{
return key;
}
}
return "";
}


### Treasure Item

The fact that you have a variable named treasureItemsWeights and that your function returns the key tells me that you might have other variables, such as treasureItemsValue or treasureItemsType and treasureItemsCount, treasureItemsPosition etc. If you do, this is a bad idea.

You should have a TreasureItem class with the properties weight, value, type and count (or whatever properties you need). Having a TreasureItem class would allow you to store all the information about a single TreasureItem together.

var treasureItems: Vector.<TreasureItem> = new <TreasureItem>[
new TreasureItem(1, 2, 3, 4, 5), // type, value, position... whatever.
new TreasureItem(2, 3, 4, 5, 6), // type, value, position... whatever.
new TreasureItem(3, 4, 5, 6, 7), // type, value, position... whatever.
];


### Efficiency

The best performance gain I can recommend would be to consider caching the total value that is calculated in the first loop, as I have a feeling that value will not change very often (if it will change at all).

### Choose Treasure Item - skewed randomness

Now that you have a TreasureItem class, you can return the TreasureItem directly, instead of returning its key.

Also, your Math.floor(Math.random() * (total+1)); is wrong. Imagine that you have the weights 2, 3, 4 which adds up to 9, then you are randomizing a number from 0 to 9 (inclusive), and then iterating and adding to total again and comparing with num <= total, now let's see the distribution:

Num -- item chosen
0 1 2 -- first item
3 4 5 -- second item
6 7 8 9 -- third item


So you see, your first item now has the same weight as the second item. This was not intended.

The correct way would be to use Math.floor(Math.random() * total); which will randomize a number from 0 to 8 (inclusive), and then iterating and adding to total again and comparing with num < total, now let's see the distribution:

Num -- item chosen
0 1 -- first item
2 3 4 -- second item
5 6 7 8 -- third item


That matches the weights exactly.

Here's what we end up with:

function chooseTreasureItem():String
{
var total = 0;
for (var item : TreasureItem in treasureItems)
{
total += item.weight;
}
var num: Number = Math.floor(Math.random() * total);
total = 0;
for (var item : TreasureItem in treasureItems)
{
total += item.weight;
if (num < total)
{
return item;
}
}
return null;
}

• Thanks, before i saw your answer i already changed to a class and cached the total, you are right about getting the num, which i will update. I guess there is no way then by using a hashtable type structure and getting constant time lookup and avoiding loops? – tsukimi Aug 29 '15 at 11:30
• @tsukimi How many treasure items do you have? It is theoretically possible to put it in a tree structure to get O(log n) lookup time, but I don't think it is worth it. – Simon Forsberg Aug 29 '15 at 12:28
• At the moment i only have around 30, i was just curious of a way to avoid for loops in as3 – tsukimi Aug 30 '15 at 1:03