🔒 Locked

C++ hat random container

Started by AngleWyrm Aug 31, 2004 at 12:01 AM 53 replies 16.4k views

Original Post

Aug 31, 2004 at 12:01 AM

Hi, I've developed a handy STL-style container for storing and retrieving items randomly. Items can have different probabilities, and can either be removed from the set like cards from a deck, or come up again like rolling dice. hat.h hat container source code, revision 1.59 The C++ hat random container online documentation hat.DevPak package for those using dev-cpp. Installs hat.h in [dev-cpp]/include, and a bunch of example programs in [dev-cpp]/Examples/Hat. Some example uses (updated):

loaded_die.cpp example of random sampling with replacement of unequally weighted objects
advanced_dice.cpp roll a set of three dice using only one call to the random number generator
cards.cpp cards are drawn from a deck, returned to the deck, and drawn again.
multiple_distributions.cpp Use several different distributions to access a given set of items.
custom_generator.cpp Example of specifying a user-designed custom random number generator.
near_max.cpp Usually draw maximum valued item, but with some diminishing probability for further down the list.
monster_drops.cpp get a couple random treasures from a master list, depending on monster level and type.
fuzzy_logic.cpp It's 68 degrees fahrenheight in here; is it hot, fine, or cold?
game_theory.cpp NPC makes a choice using a mixed strategy, so that it won't be predictable.
bernoulli_process.cpp Simulate five trucks leave a warehouse, each with a 40% independent chance of being late.
random_actions.cpp Choose a course of action based on preference and availability.
stochastic_approximation.cpp AI learns to predict an unknown behavior pattern, with overall improving results, and scores it's performance.

Give it a go, and tell me what you think :) -:|:- AngleWyrm [Edited by - AngleWyrm on October 24, 2004 5:21:15 PM]

Fruny

Aug 31, 2004 at 12:04 AM

Thanks for sharing. Thread bookmarked.
I'll give feedback tomorrow (unless I forget [wink]).

snk_kid

Aug 31, 2004 at 3:29 AM

Very interesting, i have a couple of suggestions to improve it a bit.

1. in your template arguments for hat i would also add another type parameter an allocator type that defaults to standard allocator type that allows clients to choose non default allocators, you pass this to your vector & list type parameters.

2. your non type parameter the function pointer i would turn this into a type parameter and make your default random function into some kind of functor (functional object usually overloads the function call operator i.e "()").

3. Your missing a const_iterator type.

3. Small detail but important still, your missing some typedefs in your hat type & iterator type that are required for STL, also in your iterator types provide a typedef of which iterator_category it is.

4. I briefly glanced at the concept of hat but it looks like hat could be an adaptor type more than a first class constainer if thats the case consider whether or not if the vector of nodes or list of Ts could be replaced with other STL containers if it is then you could add another template type parameter that is a template template type paramter that has a default type but clients can try different containers to see if they get better results (this cost you nothing, power 2 static polymorphism!).

I think thats everything at the moment but if i think of anything else i'll let you know.

rakoon2

Aug 31, 2004 at 4:06 AM

Ouw nice! Thank you! :) I just tried it... works great! :)

I am going to use it for my random item drops( monsters drop items )

AngleWyrm

Aug 31, 2004 at 5:27 PM

Quote:
4. I briefly glanced at the concept of hat but it looks like hat could be an adaptor type more than a first class constainer if thats the case consider whether or not if the vector of nodes or list of Ts could be replaced with other STL containers if it is then you could add another template type parameter that is a template template type paramter that has a default type but clients can try different containers to see if they get better results (this cost you nothing, power 2 static polymorphism!).

The hat is different from available STL containers in both it's operational specification, and it's implementation; it isn't possible to modify the functionality of vectors or lists to acheive it.

Edit: It is a non-sequential associative container, keyed on probability weights. The keys (as well as the values) are not necessarily unique, and can change during run-time.

It's iterators remain valid after an insert/delete--a thing vectors cannot do. It also can look up an element in O(log n) time--a thing lists cannot do. And it can delete any element from it's set--a thing heaps cannot do. And these are the main operations of any container; insert, delete, and search.

Thank you for your observations on what is needed yet; I'm working on the iterator category and const_iterator for the next revision.

[Edited by - AngleWyrm on September 2, 2004 2:27:22 PM]

snk_kid

Aug 31, 2004 at 5:39 PM

Quote:
Original post by AngleWyrm
Thank you for your observations on what is needed yet; I'm working on the iterator category and const_iterator for the next revision.

No probs, what about 1 & 2 [smile] i could give a quick example of what i was talking about.

Fruny

Aug 31, 2004 at 5:43 PM

Have you considered integrating with boost::random (or even to submit your class to Boost -- they'll dissect it more carefully than we can [smile])?

What are the exception guarantees of your class? What happens during, say, a pull(), if the element's copy operation throws an exception?

snk_kid

Aug 31, 2004 at 5:54 PM

Quote:
Original post by Fruny
Have you considered integrating with boost::random

if you go for this, this would probably intail suggestion 2, changing your non-type parameter to a type parameter (the one that you have as function pointer currently).

AngleWyrm

Aug 31, 2004 at 6:09 PM

Quote:
Original post by rakoon2
Ouw nice! Thank you! :) I just tried it... works great! :)
I am going to use it for my random item drops( monsters drop items )

Welcome! Glad it's workin' for ya.

Quote:
Original post by Fruny
Have you considered integrating with boost::random (or even to submit your class to Boost -- they'll dissect it more carefully than we can [smile])?

Edit:Yes, I submitted it to the boost mailing list, but the only responses I got from those guys were two comments about my username, and no observations about the code. The second commenter "seconded" the first commenter, commitee meeting style. Complete waste of neurons.

I had thought of the boost::random library when I first designed the optional user-specified custom RNG. Except I haven't seen boost::random code that can perform this one simple feat:

// produce a random number from a range specified at run-timefor ( int range = 3; range < 10; range++ ){    // return random number in the range [0, range)    cout << random(range) << endl;}

(Edit: that glaring white background was killing me.)

Any example boost::random code would help.

-:|:-
AngleWyrm

[Edited by - AngleWyrm on September 2, 2004 3:09:11 AM]

AngleWyrm

Aug 31, 2004 at 7:21 PM

Quote:
Original post by snk_kid
No probs, what about 1 & 2 [smile] i could give a quick example of what i was talking about.

Could you give an example of #2, show what is meant by non-type vs type parameter, and how a functor operator() could be advantageous?

snk_kid

Sep 1, 2004 at 2:28 AM

Quote:
Original post by AngleWyrm
Could you give an example of #2, show what is meant by non-type vs type parameter

an example of a non-type template parameter from your hat containers would be:

template <class T, unsigned long (*random)(unsigned long) = std_rand>

talking about the function pointer random, doing this is inflexible, remember that templates are a compile time mechanism
it allows you to perform static polymorphism where as function pointer is a run-time feature it incurs one level of indirection overhead that isn't needed.

if you change it to a type parameter e.g.:

template < typename T, typename Random = std_rand>

then you can use almost anything functors & functions.

Quote:

and how a functor operator() could be advantageous?

its strange that you know STL and you haven't come across functors before, STL use functors alot and they even provide some, mainly in the header functional.

The first reason for the operator() is that when your code realise on that operator then not only can you use types that overload operator() but you can use functions as a type for template type parameter aswell.

the advantage of functors are they are inlineable, they can maintain state, they can be configured through constructors.

Here is really simplified example of a the function generate that first uses the function rand then another call using a functor:

#include <cmath>#include <iterator>#include <algorithm>#include <functional>#include <vector>#include <iostream>struct Random {   int operator()() const {        return ::rand();   }  };template< typename T, typename Iter>void print_elems(Iter beg, Iter end) {   std::copy(beg, end,             std::ostream_iterator<T>(std::cout, ", "));}   int main() {   std::vector<int> vec_of_ints(10);   //using a function rand   std::generate(vec_of_ints.begin(),                 vec_of_ints.end(),                 ::rand);   print_elems<int>(vec_of_ints.begin(), vec_of_ints.end());   //using a functor Random   std::generate(vec_of_ints.begin(),                 vec_of_ints.end(),                 Random());   std::cout << "\n\n";   print_elems<int>(vec_of_ints.begin(), vec_of_ints.end());   return 0;}

std::generate uses a type parameter for the Generator type and not a non-type parameter, you can use anything that supports the function call operator () that includes functions this is static polymorphism.

[Edited by - snk_kid on September 1, 2004 3:28:34 AM]

AngleWyrm

Sep 1, 2004 at 10:30 AM

std::rand() is called without arguments, and produces a result in the range [0, RAND_MAX), whereas what is required is a number in the range [0, range) where range is specified at run-time.

std::rand() % range

does not produce good results (Linear Congruential generators produce hyperplanes in higher dimensions, rather than filling the space randomly). So I have created a function adaptor that provides a good conversion of the range [0, RAND_MAX) to any scale within my usage domain for std::rand().

For user-supplied custom RNGs, it would be an improbable assumption to suggest that the construct random() % range is going to perform well, a demand not placed on std::rand(). Thus what is required is that a user-supplied RNG also provide the method of scaling.

It is my opinion that a custom RNG is not a usable implementation until it provides it's user with a method of specifying a range at run-time.

[Edited by - AngleWyrm on September 1, 2004 10:30:43 AM]

snk_kid

Sep 1, 2004 at 12:22 PM

Quote:
Original post by AngleWyrm
It is my opinion that a custom RNG is not a usable implementation until it provides it's user with a method of specifying a range at run-time.

i was just showing an example of functors it wasn't mean't to be used in your implementation in any kind of way. And yes you can still provide a range at run-time with a functor if you wonted to be it one time or everytime you call it, overloading operator() doesn't mean it must have no argumenets.

AngleWyrm

Sep 1, 2004 at 2:32 PM

Actually, I was thinking more of the boost::random library when I went on a rant back there ;) Their implementation seems to require a range object be constructed and then passed to the random number generator's constructor, which will then only roll that range for it's duration. Hope I'm wrong, but I haven't seen different.

Updated query functions such as empty(), get_weight(), size(), etc, to be const.

[Edited by - AngleWyrm on September 2, 2004 11:32:29 PM]

civguy

Sep 4, 2004 at 11:26 AM

First, the documentation looks excellent. Cool graphics and css. And the code and the examples are also easy to read.

But the lib itself could use some work. Now it seems to me that it can't use a random generator object that has it's own state. Relying on global state is sometimes dangerous or just wrong. You should make it easily integratable with boost's rngs like others have suggested. You can get dynamic range by doing uniform_int<>(low, high)(engine). Ok so it means constructing small objects every time, but that is also what uniform_int itself does so I doubt it's that slow relatively (test it).

Also it could be possible to have another strategy for the selection of items, that is a look-up-table. Let the user choose which selection strategy to use (and of course to create their own strategies)

AngleWyrm

Sep 4, 2004 at 9:01 PM

Thanks for the compliment, and the constructive criticisms.

Could you go into a little detail about alternate selection methods? pseudo-code or fictional functions/usage scenarios? Examples? They help me to see the problem from different perspectives. It recently seemed as if the current implementation might be too focused on it's original purpose, and that it could serve a wider scope of uses.

Also, gave boost::random another go (Boost::random_number_generator) but I haven't got randomness out of boost yet; anyone with experience using the boost::random library, please tell me how this should be written:

#include <iostream> // cout#include "boost/random.hpp"int main(){   // select generator   boost::minstd_rand rng; // minimum standard random number generator      rng.seed( time(NULL) ); // seeding an instance   // create a function object   boost::random_number_generator<boost::minstd_rand> random(rng);   // this produces the same number every time,   // possibly the first number after seeding?   for( int i = 1; i < 5; i++ ){      std::cout << random(100) << std::endl; // wanted [0..99]  }     }

[Edited by - AngleWyrm on September 5, 2004 10:01:13 AM]

AngleWyrm

Sep 5, 2004 at 12:40 AM

Version 1.50 is Up

Due to popular demand, there is a new interface for specifying custom random number generator objects (yep) at run-time. example usage:

class rng_functor { /* custom rng */ };       // defines operator()(range)rng_functor my_instance;                      // do initializationshat<string, rng_functor> names(my_instance);  // hat using custom rng

Also added some new example programs,
and updated commentary for clearer comprehension.

-:|:-
AngleWyrm

[Edited by - AngleWyrm on September 5, 2004 11:40:38 AM]

TimChan

Sep 5, 2004 at 10:23 AM

sounds good, let me try it:)

rakoon2

Sep 6, 2004 at 6:18 AM

i get:

multiple definition of

std_rand' 
first defined here
multiple definition of

std_rand'
first defined here
multiple definition of

std_rand' 
first defined here 
multiple definition of

std_rand'
first defined here
multiple definition of `std_rand'
first defined here
...
...
...

with the new version?? :/ ?

AngleWyrm

Sep 6, 2004 at 9:43 AM

Quote:
Original post by rakoon2
i get:

multiple definition of `std_rand'
first defined here
with the new version?? :/ ?

Version 1.51 is now posted, which fixes the multiple definitions of std_rand bug.

-:|:-
AngleWyrm

Topic Locked

This topic has been locked by a moderator. New replies are not allowed.