[Patches] [ python-Patches-629637 ] Add a sample selection method to random.py

noreply@sourceforge.net noreply@sourceforge.net
Tue, 05 Nov 2002 09:34:35 -0800


Patches item #629637, was opened at 2002-10-28 03:03
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=629637&group_id=5470

Category: Library (Lib)
Group: Python 2.3
Status: Open
Resolution: None
Priority: 5
Submitted By: Raymond Hettinger (rhettinger)
Assigned to: Martin v. L÷wis (loewis)
Summary: Add a sample selection method to random.py

Initial Comment:
random.randset(n, k) returns a k length list of unique 
integers in the range [0,n).

Improves on a Cookbook submission by using the 
parameters to select between a shuffle algorithm and 
a dictionary algorithm.

I want to add this to the library because it is a simple, 
robust solution to a general selection problem and 
because it isn't obvious that two different algorithms 
are needed to balance speed/space trade-offs.

If approved, will add docs and a news item.

----------------------------------------------------------------------

>Comment By: Martin v. L÷wis (loewis)
Date: 2002-11-05 18:34

Message:
Logged In: YES 
user_id=21627

Thanks for the explanation. On to the implementation: How
did you arrive at the factor of 6 between a dictionary and a
list?

The documentation should mention the random optional argument.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2002-11-05 16:36

Message:
Logged In: YES 
user_id=80475

Like shuffle() and choose(), random sampling without 
replacement is one of the core principal use cases for 
random numbers.

Acceptance testing often requires a fixed number of non-
overlapping samples i.e.  Selecting 60 transactions out of 
a 1000 and finding zero errors yields a 95% confidence 
that the population has less than a 5% error rate.

Some simulations also need groups of non-overlapping 
samples i.e. a lottery result of six unique numbers 
selected from a range of 1 to 57.  An electronic raffle picks 
consecutive winners without allowing previous winners to 
be  reselected.

While sampling with replacement is trivial to implement 
with a list comprehension, sampling without replacement 
has a number of implementation nuances that makes it 
worthwhile to have a robust solution already implemented 
in the random library.




----------------------------------------------------------------------

Comment By: Martin v. L÷wis (loewis)
Date: 2002-11-05 09:27

Message:
Logged In: YES 
user_id=21627

Can you explain why this needs to be in the standard
library? I.e. what typical application would use it?

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2002-11-05 07:33

Message:
Logged In: YES 
user_id=80475

Martin, do you have time to give this patch a second 
review?

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2002-10-31 08:29

Message:
Logged In: YES 
user_id=80475

Added new version with local variable optimization and 
with the dictionary results returned in selection order.


----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2002-10-29 05:42

Message:
Logged In: YES 
user_id=80475

Renamed to random.sample(n,k) to show that it is used 
for sampling without replacement.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2002-10-29 05:42

Message:
Logged In: YES 
user_id=80475

Renamed to random.sample(n,k) to show that it is used 
for sampling without replacement.

----------------------------------------------------------------------

Comment By: Raymond Hettinger (rhettinger)
Date: 2002-10-28 13:54

Message:
Logged In: YES 
user_id=80475

Added full patch with news item and docs.

----------------------------------------------------------------------

You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=305470&aid=629637&group_id=5470