Yes, for the case where a set of items is equally weighted, and won't change, constant time performance is possible. If that difference in performance is measurably significant (% time in a call graph) in your application, then vectors provide the quickest solution. If the number of items is also known ahead of time, then an array may be used instead.

For uniformly weighted sampling with replacement, items can be stored in a vector or array rather than a hat, and then a random integer in the range [0..container.size()) can be used to access items. For uniformly weighted sampling without replacement, perform a random_shuffle on a vector(or array) of items, and then take as many as desired from one end.

Hats are, however, quite convenient; it might be useful to compare the results on a given (non-trivial) application, to see if hat::find_index() consumes a substantial amount of time.

It might be possible to add a uniform_get(), uniform_pull(), and uniform_put() function to the container, but those functions would invalidate a given instance for non-uniform use. The problem with doing this is that it becomes difficult to tell if a container is of "type" uniform or non_uniform. Some system is necessary to differentiate between these categories/classes/types, which should be recognizable by the compiler, but without adding complexity to the constructor / user interface.

-:|:-
AngleWyrm

[Edited by - AngleWyrm on October 17, 2004 7:04:29 PM]

Revision 1.58 is up, which has enhanced performance -- improved the search function's execution time by approximately 19%. Rather a bit of an improvement :)
-:|:-
AngleWyrm

[Edited by - AngleWyrm on October 20, 2004 5:31:43 PM]

Revision 1.59 is online, which has improved support for const_iterators.

I've been wondering about the complexity of the current O(log n) binary-tree type solution; is this time complexity inherent to the problem space, or is it the result of a suboptimal point of view? Can mathematics provide some better insight?

Let an experiment consist of a set S of k possible outcomes si, having associated probability weights P(si) such that:


Note in particular that P(si) > 0 for all si; an impossible outcome is not a member of the set of possible outcomes.
For reason of algorithmic optimization let us express P(si) as a numerator/denominator integer pair:



In equation (2), ci can be interpreted as the number of chances out of Sum(ci) total chances that outcome si will result from experiment S. This value ci can be defined as the raw chance weight of si with respect to probability, which can then be viewed as the normalized chance weight of si.

With these raw chance weights, we can now completely express the probability distribution of the k outcomes of experiment S with k+1 integers k, C={ c1, c2, …, ck-1, ck }, where the set C of raw chance weights ci constitute a partition of the integer m = Sum(ci) of width k.

Are there methods which can select the dimension, or the partition that do not require a running Sum() construct for each element?

[Edited by - AngleWyrm on November 5, 2004 4:53:48 AM]