   Re-inventing the Wheel, or Mediocre Solutions to Already Solved Problems?
Re-inventing the Wheel, or Mediocre Solutions to Already Solved Problems?While doing my strategy game Imperator Mundi and other projects I have repeatedly encountered the issue of how to select a random result froma set of possible outcomes, where the possible outcomes have different weights and are exclusive.Typically the number of outcomes and their weights are changing all the time.I have used a simple to implement solution that uses C++ multimap:class CProbableEvents{float TotalWeight;std::multimap<float, int> WeightEventMap;public:  CProbableEvents() : TotalWeight(0) {}  void AddEvent(float gProbability, int gIdentifier)  {TotalWeight+=gProbability;WeightEventMap.insert( std::make_pair<float,int>(TotalWeight,gIdentifier) );  }    int GetRandomEvent(int gValueToReturnIfNotFound=-1)  {    float tHit=TotalWeight*GetRandomValueFromZeroToOne();    std::multimap<float,int>::iterator tCheckI=WeightEventMap.lower_bound(tHit);    if( tCheckI!=WeightEventMap.end() )    { return tCheckI->second;    } else    { return gValueToReturnIfNotFound;    }  }};The above code needs a decent GetRandomValueFromZeroToOne() function,and can be used for example like this:CProbableEvents tCombatResult;tCombatResult.AddEvent( tDestructionVote, E_UNIT_IS_DESTROYED ); tCombatResult.AddEvent( tDamageVote, E_UNIT_IS_DAMAGED ); tCombatResult.AddEvent( tUnharmedVote, E_UNIT_IS_UNHARMED ); int tResult=tCombatResult.GetRandomEvent();if( tResult==E_UNIT_IS_DESTROYED ) RemoveUnit();else ApplyPhaseResults( tResult );// ...Comments:-Custom solutions should be used in places where one cannot afford to consume time and memory as this class does....-Dealing extreme weight values...-I have done more complex systems in the problem domain code itself,but it would be better to implement some of them in a reusable form also...-I suspect that my current GetRandomValueFromZeroToOne() is not very good...What type of solutions do you have to these issues?Suggestions?-Osmo Suvisaariwww.waspgames.com
  This looks like a pretty good solution to me. The only other solution I've thought of for this sort of problem is using a linear array or list instead of a map, and storing the probability of events along with the events in the array. Then given the random number between 0 and totalWeight, iterate down the array until the corresponding event is found (adding up the probabilities of each event as they are iterated over, until the cumulative probability is greater than the random number). This is slower for selecting an event, since it is O(n) while the map solution is O(log(n)), but it can be O(1) to add, remove, or change the probability of an event, while the map does those operations in O(log(n)) time. A map also has higher overhead than an array.As long as the number of events is small, it doesn't really matter that much.Extreme weights work the same as any other weights, unless you mean values that are so extreme that there isn't enough floating point accuracy. In that case the odds of an unlikely event happening where already extremely low anyway.Your selection of a random number between 0 and 1 is a separate problem. The usual solution is to use a good pseudorandom number generator to select a number in the range [0,MAX_RANDOM) and divide by MAX_RANDOM.To make things reusable, you could try to design the system to allow a hierarchy of events, and then add and remove entire groups of events in a hierarchical manner.   ;  You don't seem to have a way to remove outcomes or modify the weights of outcomes once they have been inserted. Depending on how dynamic your weights really are and how many outcomes there are (and of course, whether this REALLY uses up all that much CPU power and is therefore worth optimising), I think you can perform any update in log(n) time, where n=number of outcomes.It works something like this: you have a tree along the lines of:struct tree_node{    float total_weight;    tree *left, *right;    outcome *outcome;};Obviously this structure isn't really perfect because it includes data for both the tree nodes and leaves, but that's C++ for you. Then you can update the tree by walking from bottom to top altering the weight. Similarly you can add or remove events this way. Of course, to really make it work you'd have to use a red-black tree or something similar to guarantee log(n) behaviour, but you get the idea. The reason I'm only outlining this is it's not trivial to implement because C++ doesn't let you add additional data to the nodes of the trees it uses to implement std::set/map/multimap etc., so you have to do the whole thing by hand. In fact, it's a slightly curious situation because you know that your top-down traversal of the tree to find the outcome for a given random variable output you know the weighted probability at each node, and you can adjust your tree to improve the amortised time accordingly. That's a whole nother thing though. The thing is it's only really worth it if the number of updates to your probabilities/outcomes are on the same order as the number of queries, because if either massively outweighs the other a complete recalculation will actually be more efficient.Anyway, it's only worth it at all if you really need the CPU cycles. If you really do, good luck with that; it won't be fun to write.[/source]   ;  Actually, for the thing ZQJ describes, keeping the tree balanced isn't that hard. With normal binary trees balancing is difficult because the order of elements is important. For this probability tree, the order is irrelevant. The structure more closely resembles a heap, and it can be kept balanced in the same way as a binary heap (and it can also be stored in an array like a binary heap, so there is no need to maintain pointers to the children).Now I submit that with some clever implementation it should be possible to store the non-leaf nodes of the tree as an array of floats, and the leaf nodes as an array of ints. Or if you're sure about the sizes of data types they could all be stored in a single array (and this may simplify things a bit).Anyway, adding and removing elements would be just like a balanced binary heap, with elements to be removed swapped with the last element before removing, and the updates being fairly similiar (a little different, since with the probability tree a few changes need to be propagated all the way up the tree). Similiarly a newly added element is placed at the end of the array. These operations could also require moving around another element, since the leaves and non-leaves of the probability tree have very different purposes, unlike a heap's nodes.   ;  Thank you, good points.About modifiability:In some cases I have just re-created the data many times.Speed has not been an issue in this brute-force approach.However, a good way to modify the weights would be great.Using mostly STL containers and very few pointers, I have made a relatively small amount of bugs in this project:Now is time to summon the bugs, creating a custom tree with complex pointer logic... [cool] ;Quote:Original post by VorpyThis looks like a pretty good solution to me. The only other solution I've thought of for this sort of problem is using a linear array or list instead of a map, and storing the probability of events along with the events in the array. Then given the random number between 0 and totalWeight, iterate down the array until the corresponding event is found (adding up the probabilities of each event as they are iterated over, until the cumulative probability is greater than the random number). This is slower for selecting an event, since it is O(n) while the map solution is O(log(n)), but it can be O(1) to add, remove, or change the probability of an event, while the map does those operations in O(log(n)) time. A map also has higher overhead than an array.I would personally recommend using a linear array, in the way that Vorpy already suggested, the only thing I would have to add is that using a linear array can actually be O(log(n)) to find the event (the same as the map, and the same as the best-case for a binary tree) if you use bisection. Unfortunately you get O(n) performance for operations that modify the probabilities, but if that is rare it doesn't really matter.As in the original posted code for AddEvent you store the following pairs in the array: (cummulative weight, event ID). When it's time to pull up an event you do the following (sorry for the Pascal code):function GetRandomEvent(tHit: Float): Integer;var  L, H: Integer;  // the range of array indiced where our event might be  M: Integer;// temporary index (mid-point between L and H)begin  L := 1;   // set L to the start of the array  H := Length(WeightEventMap);  // set H to the end of the array  while (H-L)>1 do  // iterate till we have found our (one) event    begin M := (L+H) div 2;  // find the middle point between L and H if (WeightEventMap[M].Weight=tHit)  // are we extremely lucky (have we inadvertently stumbled accross the event that we are looking for)?   thenbegin  H := M;  // guess we are lucky, set H (the return value) to M,  Break;   // and break out of the loopend; if (WeightEventMap[M].Weight<tHit)  // compare the value at the mid-point (M) to the target value (tHit)   thenL := M   // raise the lower bound (our event must have its index higher than M)   elseH := M;  // lower the upper bound (our event must have its index lower than M)    end;  GetRandomEvent := WeightEventMap[H].EventID;  // return the first event that has Weight>=tHit (that event has index H after the above loop was executed)end;As you can see, the above code is relatively simple (simpler than the tree balancing code you would need to guarantee O(log(n)) performance of the binary tree anyway), and has minimal overhead (no complex data structures, and no classes), while performing better than (or atleast as good as) either the map or the tree. However:Quote:Original post by VorpyAs long as the number of events is small, it doesn't really matter that much.This is also very true. If your number of events is small then it really doesn't matter if you just use simple linear search (like in the original code), since the overhead of anything else can end up being much greater than the time to execute the linear search! Find out your requirements first.In spite of the above, if it were me I would still use bisection for completeness sake, since unlike most solutions bisection has virtually no overhead.   ;  OP: If you reject zero probabilities in AddEvent(), you don't need a multimap, just a plain old map - because every "cumulative weight" is a distinct value. I would recommend sticking with integer weighting values, though, to avoid the usual problems with FP arithmetic. I also object rather strongly to some of your naming conventions (lowercase g prefix for a *member function parameter*? what?)Oh, not to mention, you *can't* get a .end() result from lower_bound here (barring some multithreading bug, etc.), given a correct RNG. You're simply not going to generate a value equal to or greater than the last value in the map.EDIT: Oh, of course that is a problem if the map is empty ;) To fix that, you can simply require the first option to be added in the constructor.template <typename T>struct WeightedDie {  typedef std::map<int, T> mapping_t;  WeightedDie(int weight, const T& result) : TotalWeight(weight) {    if (weight == 0) { throw std::runtime_error("first event must be possible"); }    resultMapping[totalWeight] = result;  }  void addSide(int weight, const T& result) {    if (weight == 0) { return; }    // We can just use operator[] to insert here. But you should know that    // the whole reason for using std::make_pair (instead of the std::pair    // constructor) is to *avoid* typing the template parameters explicitly.    totalWeight += weight;    resultMapping[totalWeight] = result;  }    const T& roll() const {    int rnd = std::rand() % totalWeight; // for now...    mapping_t::iterator it = resultMapping.lower_bound(rnd);    assert (it != resultMapping.end());    return it->second;  }  private:  int totalWeight;  mapping_t resultMapping;};Quote:Original post by Devilogicif you use bisection. Unfortunately you get O(n) performance for operations that modify the probabilities, but if that is rare it doesn't really matter.As in the original posted code for AddEvent you store the following pairs in the array: (cummulative weight, event ID). When it's time to pull up an event you do the following (sorry for the Pascal code):*** Source Snippet Removed ***You don't have to do this yourself: the standard C++ library offers std::lower_bound(), which basically does the same thing for general sorted containers as the map lower_bound member function.   ;  So what methods have we come up with...Storing cumulative weights in a tree, O(logn) selection, recreate the whole tree in O(nlogn) time for most changes.Storing weights in an array, O(n) selection, O(1) changes, can be sorted in O(nlogn) time to improve average performance by putting more likely outcomes at the front of the array (improvement depends on how unbalanced the weights are)Storing cumulative weights in an array, O(logn) selection, O(n) changesCustom balanced binary heap-like thing that stores weights and cumulative weights, O(logn) selection, O(logn) changes, requires twice as much memory as the other array-based methods, more overheard for selection than cumulative weights in array methodAnd finally, one more method I've thought of: Create a table of outcomes and pick out a random entry. Outcomes are entered into the table a number of times proportional to their weight. Implemented with a vector or deque. O(1) selection. Update complexity depends on the ratios between the weights and the resolution of the table; weights must be rounded to the closest value representable by the table. For example, each entry might correspond to a probability of .25. An event with a weight of 1 would have 4 entries, and an event with a weight of .6 would probably have 2 entries. Using multiple tables with different resolutions in a hierarchical scheme may allow for better performance or more resolution while still providing O(1) performance, although with more overhead.Oh, one more possibility I just thought up: Combine the array based methods to create an adaptive data structure using one array that contains the weights and another array that contains cumulative weights, but only calculate the cumulative weights as needed (when traversing weight array) and then use them when possible. Probably has too much overhead cost to be useful in most circumstances, but asymptotically it never performs worse than the weights in array method, and if selection of events is frequent it tends towards the behavior of the cumulative weights method.   ;Quote:Original post by VorpySo what methods have we come up with...Storing cumulative weights in a tree, O(logn) selection, recreate the whole tree in O(nlogn) time for most changes.Storing weights in an array, O(n) selection, O(1) changes, can be sorted in O(nlogn) time to improve average performance by putting more likely outcomes at the front of the array (improvement depends on how unbalanced the weights are)Storing cumulative weights in an array, O(logn) selection, O(n) changesCustom balanced binary heap-like thing that stores weights and cumulative weights, O(logn) selection, O(logn) changes, requires twice as much memory as the other array-based methods, more overheard for selection than cumulative weights in array methodAnd finally, one more method I've thought of: Create a table of outcomes and pick out a random entry. Outcomes are entered into the table a number of times proportional to their weight. Implemented with a vector or deque. O(1) selection. Update complexity depends on the ratios between the weights and the resolution of the table; weights must be rounded to the closest value representable by the table. For example, each entry might correspond to a probability of .25. An event with a weight of 1 would have 4 entries, and an event with a weight of .6 would probably have 2 entries. Using multiple tables with different resolutions in a hierarchical scheme may allow for better performance or more resolution while still providing O(1) performance, although with more overhead.Oh, one more possibility I just thought up: Combine the array based methods to create an adaptive data structure using one array that contains the weights and another array that contains cumulative weights, but only calculate the cumulative weights as needed (when traversing weight array) and then use them when possible. Probably has too much overhead cost to be useful in most circumstances, but asymptotically it never performs worse than the weights in array method, and if selection of events is frequent it tends towards the behavior of the cumulative weights method.I suspect you're overthinking this. :) Probably, the cumulative-weights-in-array (ahem, vector) approach is most likely to be optimal. (When binary-searched, the "tree" is always perfectly "balanced", whereas schemes like red-black, AVL etc. allow the tree depth to be up to a constant multiple of the optimal value. Not to mention per-node space overhead, cache coherency etc. Also, the fact that subsequent nodes have to be modified *anyway* ruins the map's normal advantage of O(lg N) updates.)   