[ python-Bugs-1460340 ] random.sample can raise KeyError

[SourceForge.net]

Bugs item #1460340, was opened at 2006-03-29 00:05
Message generated for change (Comment added) made by phr
You can respond by visiting: 
https://sourceforge.net/tracker/?func=detail&atid=105470&aid=1460340&group_id=5470

Please note that this message will contain a full copy of the comment thread,
including the initial issue submission, for this request,
not just the latest update.
Category: Python Library
Group: Python 2.3
Status: Closed
Resolution: Fixed
Priority: 5
Submitted By: paul rubin (phr)
Assigned to: Nobody/Anonymous (nobody)
Summary: random.sample can raise KeyError

Initial Comment:
I have only tested this in 2.3 and the relevant code in
random.py has changed in the current svn branch, but
from inspection it looks to me like the bug may still
be there.

If you initialize a dictionary as follows:

 a={}.fromkeys(range(10)+range(10,100,2)+range(100,110))

then

 random.sample(a,3)

raises KeyError most times that you call it.


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

>Comment By: paul rubin (phr)
Date: 2006-03-29 09:46

Message:
Logged In: YES 
user_id=72053

I don't think the fix at 43421 is quite right, but I can't
easily test it in my current setup.  Suppose

a = dict.fromkeys(range(99) + ['x'])
b = random.sample(a,1)

99% of the time, there's no KeyError and b gets set to [j]
where j is some random integer.

1% of the time, there's a KeyError, random.sample is called
recursively, and the recursive call returns [some integer j]
99% of the time, and returns ['x'] 1% of the time.

So in total, ['x'] gets returned .01% of the time instead of
1% of the time.

I think it's better to not set result[i]=population[j]
inside the loop.  Instead, just build up the selected set
until it has enough indices; then try to make a result list
using those indices, and if there's a KeyError, convert the
population to a list and use the same selection set to make
the results.

gbrandl also correctly points out that a dict is not a
sequence type, so maybe it's ok to just punt on dicts.  But
it's obvious from the code comments that somebody once
wanted dicts to work, and it's reasonable for people to want
sets to work.


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

Comment By: Raymond Hettinger (rhettinger)
Date: 2006-03-29 09:17

Message:
Logged In: YES 
user_id=80475

Checked-in a fix.
See revision 43420 and 43421.

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

Comment By: Georg Brandl (gbrandl)
Date: 2006-03-29 09:11

Message:
Logged In: YES 
user_id=849994

random.sample is documented to take a sequence as its first
argument. A dict is not a sequence type.

I think you want
random.sample(a.keys(), 3)
or, for large dicts,
random.sample(a.iterkeys(), 3)

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

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