Path: csiph.com!usenet.pasdenom.info!weretis.net!feeder1.news.weretis.net!feeder.erje.net!eu.feeder.erje.net!xlned.com!feeder5.xlned.com!newsfeed.xs4all.nl!newsfeed1a.news.xs4all.nl!xs4all!newsgate.cistron.nl!newsgate.news.xs4all.nl!post.news.xs4all.nl!not-for-mail
To: python-list@python.org
From: Terry Reedy <tjreedy@udel.edu>
Subject: Re: random.sample with large weighted sample-sets?
Date: Sun, 16 Feb 2014 14:47:56 -0500
References: <20140215224145.68c82eb4@bigbox.christie.dr> <ldpve4$tnk$1@ger.gmane.org> <20140216082250.7aecebb4@bigbox.christie.dr>
Mime-Version: 1.0
Content-Type: text/plain; charset=UTF-8; format=flowed
Content-Transfer-Encoding: 7bit
User-Agent: Mozilla/5.0 (Windows NT 6.1; WOW64; rv:24.0) Gecko/20100101 Thunderbird/24.3.0
In-Reply-To: <20140216082250.7aecebb4@bigbox.christie.dr>
Precedence: list
Newsgroups: comp.lang.python
Message-ID: <mailman.7070.1392580125.18130.python-list@python.org>
Lines: 79
NNTP-Posting-Host: 2001:888:2000:d::a6
Xref: csiph.com comp.lang.python:66564

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