[Python-ideas] random.choice on non-sequence

[Grant Jenks]

On Tue, Apr 12, 2016 at 2:40 PM, Rob Cliffe <rob.cliffe at btinternet.com> wrote:
>
> It surprised me a bit the first time I realised that random.choice did not
> work on a set.  (One expects "everything" to "just work" in Python! :-) )

As you point out in your proposed solution, the problem is `random.choice`
expects an index-able value. You can easily create an index-able set using
the sortedcontainers.SortedSet interface even if if the elements aren't
comparable. Simply use:

```python
from sortedcontainers import SortedSet

def zero(value):
    return 0

class IndexableSet(SortedSet):
    def __init__(self, *args, **kwargs):
        super(IndexableSet, self).__init__(*args, key=zero, **kwargs)

values = IndexableSet(range(100))

import random

random.choice(values)
```

`__contains__`, `__iter__`, `len`, `add`, `__getitem__` and `__delitem__` will
all be fast. But `discard` will take potentially linear time. So:

```
index = random.randrange(len(values))
value = values[index]
del values[index]
```

will be much faster than:

```
value = random.choice(values)
values.discard(value)
```

Otherwise `IndexableSet` will work as a drop-in replacement for
your `set` needs. Read more about the SortedContainers project at
http://www.grantjenks.com/docs/sortedcontainers/

Grant