3
$\begingroup$

Preface: It's been a long time since I've been in school, and my terminology is probably all wrong. Apologies...

Summary: I have a data structure with probability ranges assigned to the elements, and I want to "roll the dice" and get the element at that spot. I'm wondering if there's a (good) way to do this in O(1) time?

Assume I've got a data structure like this, where the indices/keys represent ranges, and the values are what I want:

a = {
  [0..0.3) -> "foo",
  [0.3..0.4) -> "bar",
  [0.4..0.9) -> "baz",
  [0.9..1.0] -> "qux"
}

I want to retrieve a value from that array using a randomly generated number between 0 and 1. So, using that previous example, I do something like:

a[0.2] == "foo"
a[0.3] == "bar"
a[0.5565] == "baz"
a[0.8] == "baz"
...and so forth

I think I could store the data in a tree structure where I could walk to the correct element in O(log(n)) time, but I'm wondering if there's a clever way to do it in O(1) time.

I'm also curious if there is a specific name for this kind of data structure. It seems like someone would have played with this at some point.

As background, I'm toying with creating a Markov generator, and that requires storing the frequencies for all the words/token pairs. I'm guessing this is a solved problem already, and there are probably better solutions than what I'm proposing, but it seemed like an interesting problem and now I'm curious about the index-by-range problem all by itself, independent of the Markov aspect.

Improve this question
$\endgroup$
1
  • 2
    $\begingroup$ Reading between the lines, you don't actually want to index an array with ranges for keys, you actually want to know how to efficiently implement a loaded dice roll. If that's the case, this is a duplicate: stackoverflow.com/questions/5027757/… In particular, check out Vose's variant of the alias method, which seems to tick all the boxes. $\endgroup$
    – Pseudonym ♦
    Commented Nov 20, 2015 at 3:21

2 Answers 2

Reset to default
2
$\begingroup$

Perhaps what you're looking for is a Direct-adress Table

You can set up the keys as the ranges you've provided. Since the set of keys is quite small (4 intervals), a Direct-adress Table is a simple solution to your problem. It has the advantage of retrieving data in O(1)

The keys would hold a pointer to the data you want to retrieve.

For example, you can set a variable key1 as the interval [0..0.3). We generate a random number x, and get 0.1. Since 0.1 meets the conditions of the first key ( x >= 0 and x < 0.3), we can retrieve the data stored in key1 in O(1) time.

If you want more information about a Direct-adress Table or O(1) operations on dictionaries, I recommend Introduction to Algorithms, 3rd Edition, Chapter 11

Improve this answer
$\endgroup$
4
  • $\begingroup$ Can you provide a self-contained summary of what a direct-address table is? Is it a data structure? $\endgroup$
    – D.W. ♦
    Commented Nov 20, 2015 at 8:53
  • $\begingroup$ But how can we determine which interval 0.1 falls inside without searching through the different intervals until we find the one where our value falls? In other words, given the value 0.1 and the direct address table, how do we get O(1) access to the value we want? $\endgroup$
    – Micah
    Commented Nov 20, 2015 at 14:47
  • $\begingroup$ A Direct-adress table is a simpler form of a Hash Table. A hash table is an effective data structure for implementing dictionaries, also known as associative arrays (a value is associated with an unique key).Since you said you have an array-like structure, you can set up a key to hold the index of the data you want to retrieve, as long as you know what index it is. $\endgroup$
    – eegodinez
    Commented Nov 20, 2015 at 15:51
  • $\begingroup$ @Micah you can set up some conditions to check if your randomly genetared number falls in one of the intervals provided. Say we get 0.1, and since 0.1 falls into the conditions of the first interval, we access the data stored in key1. Say we are using an array A to store the data, and the variable key1 stores the index where its apropiate data is stored. To access it, we would use a direct search A[key1] to obtain the data in O(1) time. $\endgroup$
    – eegodinez
    Commented Nov 20, 2015 at 15:56
1
$\begingroup$

The best algorithm I know of is to build a binary search tree (where the keys are the endpoints of your ranges), as a pre-processing step. Then when you pick a randomly generated number $x \in [0,1]$, you can traverse the binary search tree to see which interval it is contained in.

The running time of this approach is essentially $O(\lg n)$, for a suitable definition of $n$.

I don't know of any way to achieve $O(1)$ time and don't expect that to be possible in general, though it might be possible in special cases. For example, if all ranges are of the form $[a_i/k,b_i/k)$ and where $k$ is the same for all ranges, then with preprocessing you can build an array of length $k$ that lets you do a $O(1)$-time lookup of the correct range. But this technique doesn't work for arbitrary ranges.

Improve this answer
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Not the answer you're looking for? Browse other questions tagged or ask your own question.