random.sample with large weighted sample-sets?

Terry Reedy tjreedy at udel.edu
Sun Feb 16 20:47:56 CET 2014

```On 2/16/2014 9:22 AM, Tim Chase wrote:
> On 2014-02-16 04:12, Terry Reedy wrote:
>> On 2/15/2014 11:41 PM, Tim Chase wrote:
>>>     data = (
>>>       ("apple", 20),
>>>       ("orange", 50),
>>>       ("grape", 30),
>>>       )

>> If you actually start with date in this form, write the few lines
>> needed to produce the form below.
>>
>> import bisect
>> import random
>>
>> data = [
>>     (0, 'apple'),
>>     (20, 'orange'),
>>     (70, 'grape'),
>> ]
>>
>> for i in range(10):
>>       r = random.randrange(0, 100)
>>       i = bisect.bisect(data, (r, 'zzzzz')) - 1
>>       print(data[i][1])
>
> Trying to read what may be implicit assumptions in your code:

0) The frequencies are relative, not absolute, and the selection is with
replacement (== selection without replacement from an 'infinite' population)

> 1) your code calculates "100" as sum(item[0] for item in data)

yes

> 2) the data has to be sorted for bisect to work

cumulative sums are automatically sorted.

>
> 3) you meant to write "(10, 'apple')" rather than 0.

No (as Ned explained). There are 20 integers in [0, 20), so 20 chances
out of 100 to select an apple.

> 4) that "zzzzzz" is some arbitrary value that should come after any
> string that could appear in the data;

Right. Use "\U000FFFFF" if not using ascii only.

> perhaps using some custom "InfinityString" class where everything
> compared to it is always less than it.

Why bother when a good-enough 'top' string is available?
Up to you.

The issue can be avoided by transposing the n x 2 array into a 2 x n
array with separate subarrays of cumulative sums and objects.  Do the
bisect search in the subarray of cusums and use the returned index to
retrieve the object from the object array.

>
> Some long-running testing on this code seems to show that if two
> items have the same probability, bisect only appears to find the last
> one.  Tested with
>
>    data = [
>      (10, "apple"),
>      (20, "banana"), # I never get any bananas, even after thousands of iterations

because 20 - 20 == 0

>      (20, "grape"),
>      (50, "orange"),
>      ]

--
Terry Jan Reedy

```