Quantcast

[issue7522] random.choice should accept a set as input

Previous Topic Next Topic
 
classic Classic list List threaded Threaded
9 messages Options
Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor

New submission from Leo <[hidden email]>:

The following code should just work:

import random
random.choice(set(range(5)))

instead the output is TypeError:

TypeError: 'set' object does not support indexing

The algorithm in random.choice requires a sequence, but the semantics of
choice do not, and should not, require a sequence.

The code should be changed to convert the input to a sequence instead.

Cheers,
Leo.

----------
components: Library (Lib)
messages: 96480
nosy: lleeoo
severity: normal
status: open
title: random.choice should accept a set as input
type: behavior
versions: Python 2.6

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%40nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor

Mark Dickinson <[hidden email]> added the comment:

This would be a new feature, so would have to wait for Python 2.7 / 3.2  
(2.6 is only receiving bugfixes).

----------
assignee:  -> rhettinger
nosy: +mark.dickinson, rhettinger
type: behavior -> feature request
versions: +Python 2.7, Python 3.2 -Python 2.6

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%40nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor
In reply to this post by STINNER Victor

Raymond Hettinger <[hidden email]> added the comment:

The underlying data structure for sets doesn't lend itself to an
efficient method of random selection.  It is best for the programmer to
explictly convert to a sequence and then make the random selection (that
way the conversion cost isn't hidden).

If you don't mind the inefficiency of an implicit conversion to a list,
you can use "random.sample(s, 1)[0]".  If only an arbitrary element is
needed, use "x=next(iter(s))" to non-destructively fetch the first element.

----------
resolution:  -> rejected
status: open -> closed

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%40nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor
In reply to this post by STINNER Victor

Leo <[hidden email]> added the comment:

Thanks for the suggestions "random.sample(s, 1)[0]" and
"x=next(iter(s))".

A counterpoint: isn't this a classic example of where polymorphism
enables a more elegant, simple, and clear (dare I say Pythonic)
approach? The complexity of allowing sets as inputs, even with a naive
implementation, is still O(n) even in the worst case vs. O(1) for
arrays. Isn't documenting that distinction good enough?

Thanks,
Leo.

----------

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%40nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor
In reply to this post by STINNER Victor

Thomas Dybdahl Ahle <[hidden email]> added the comment:

Why not just add support to the set container?
As far as I know, it is a binary search tree, so supporting random picking in O(logn) should be easy.

----------
nosy: +Thomas.Dybdahl.Ahle

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%40nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor
In reply to this post by STINNER Victor

Mark Dickinson <[hidden email]> added the comment:

> As far as I know, it is a binary search tree,

It's not:  it's based on a hash table.  It's essentially a dict with keys but no values.  An additional complication is that the hash table can be very sparsely filled, in the case of a large set that has had most of its elements deleted---there's no automatic shrinkage of the hash table in that case.  So repeated random selection until you find a filled hash table entry would be inefficient in that case.

----------

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%40nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor
In reply to this post by STINNER Victor

Thomas Dybdahl Ahle <[hidden email]> added the comment:

I'm sorry. I see the problem then.
Do you know, if there are any plans of adding a fast balanced binary search tree to pythons stdlib?

----------

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%40nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor
In reply to this post by STINNER Victor

Michele Mazzucchi <[hidden email]> added the comment:

Folks, I really think this should be addressed.

Python has beautiful data structure semantics, and this is a stain in them.

An implementation based on the current underlying hash table is quite simple, just pick random addresses until an active key is found. Even on sparse tables this is probabilistic O(1). Even with average load factor = 50%, only 1 extra attempt is needed; 2 with LF as low as 33%.

I'm happy to provide a patch if anyone defines the desired API in Include/setobject.h .

----------
nosy: +michelem

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%2B1322467933539-512619%40n6.nabble.com

Reply | Threaded
Open this post in threaded view
|  
Report Content as Inappropriate

[issue7522] random.choice should accept a set as input

STINNER Victor
In reply to this post by STINNER Victor

Mark Dickinson <[hidden email]> added the comment:

Michele, you might want to raise this on the python-dev or python-ideas mailing list---it'll get better exposure there than in this closed issue.

For completeness, see also the previous discussion in issue 936988.

----------

_______________________________________
Python tracker <[hidden email]>
<http://bugs.python.org/issue7522>
_______________________________________
_______________________________________________
Python-bugs-list mailing list
Unsubscribe: http://mail.python.org/mailman/options/python-bugs-list/lists%2B1322467933539-512619%40n6.nabble.com

Loading...