lua-users home
lua-l archive

[Date Prev][Date Next][Thread Prev][Thread Next] [Date Index] [Thread Index]


"spir" writes:
 
> The problem is, how to toss a choice in a set of discrete values, each having a
> relative probability (represented by an integer, sometimes a %age).
[...]
> A simple solution is to make a "sampling set"
> {a,a, b,b,b, c}
> and randomly toss in there.
>
> However, this may be very costly due to the construction of the set-table.
[...]
> Another solution I thought at is to use a multiset, with cardinalities
> represents relative probabilities of codes:
> {{a,2}, {b,3}, {c,1}}
> Actually, if codes are plain ordinals, then it can just be:
> {2, 3, 1} -- sum = 6
> I'd just toss random(6), then iterate on cardinalities (summing on the way)
> until I reach a value >= toss result.
An obvious improvement for the first is to first divide the relative probabilities by a common divisor, if there is one.  That wouldn't help your example (since the gcd of 2, 3, 1 is 1), but it might if you have a larger range.  Instead of building a table with 10 copies of a, 20 of b, and 30 of c, just use { a, b, b, c, c, c }.
 
In your case, these values are supplied by the user, and users always do exactly what you don't want them to.  So you'd have to be able to deal with the worst case.  But it would use less memory if they tend to use nice round numbers.
 
If I've understood you properly, that worst case needs a table of only about 600 entries.  Is that right?  600 isn't much.  I'd just go ahead and use that, unless the table needs to be rebuilt very frequently.
 
Your second solution can be improved slightly by storing the accumulated sum, and storing it in another table.  So your example would be items = { a, b, c }  sums = { 2, 5, 6 }.  Then the search can stop when the rolled number is greater than the stored number (with no adding in the loop), and you avoid a table lookup.  Then the seach would be something like this:
 
-- linear search
local i = 1
while roll <= sums[i] do
    i = i + 1
end
useItem( items[i] )
 
That also allows the use of a binary search instead of a linear one.  If you have a large number of items, this will be faster.  But for small numbers, a linear search is is probably best.
 
-- binary search
local first = 1
local last = #sums
while first ~= last do
    local half = math.floor( (first+last)/2 )
    if roll <= sums[half] then
        first, last = first, half
    else
        first, last = half+1, last
    end
end
useItem( items[first] )