in reply to Biased random number selection

I just thought of one more potential optimization if you're going to use a linear search through the list of frequencies.

If your frequencies are very disparate (some values are much more likely to occur than others), then searching through the most likely results first would yield results faster, on average. To do this, you can sort the frequency list by decreasing frequency, and then search linearly through the list for your target value. In the frequency list you'd need to store n as well as frequency(n), because the index into the frequency list will no longer be equal to n once you sort the list.

Alan

Replies are listed 'Best First'.
RE: Re: Biased random number selection
by merlyn (Sage) on Jul 12, 2000 at 20:44 UTC
    If your frequencies are very disparate (some values are much more likely to occur than others), then searching through the most likely results first would yield results faster, on average. To do this, you can sort the frequency list by decreasing frequency, and then search linearly through the list for your target value.
    My gut says that the cost of sorting will far outweigh the cost of finding your desired item, unless you could cache the result of the sort so it's done once, not once per operation.

    My gut has been known to be wrong before though. {grin}

    -- Randal L. Schwartz, Perl hacker

[reply]

In Section Seekers of Perl Wisdom